1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Cuardaigh Dénártha]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Ollscoil Harvard]

3
00:00:04,000 --> 00:00:07,000
Is é [seo CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Má thug mé tú le liosta ainmneacha carachtar Disney in ord aibítre

5
00:00:09,000 --> 00:00:11,000
agus d'iarr tú a fháil Mickey Luiche,

6
00:00:11,000 --> 00:00:13,000
conas a théann faoi é seo a dhéanamh?

7
00:00:13,000 --> 00:00:15,000
Slí amháin soiléir a bheith a scanadh ar an liosta ó thús

8
00:00:15,000 --> 00:00:18,000
agus seiceáil gach ainm a fheiceáil má tá sé Mickey.

9
00:00:18,000 --> 00:00:22,000
Ach mar a léann tú Aladdin, Alice, Ariel, agus mar sin de,

10
00:00:22,000 --> 00:00:25,000
go mbainfidh tú realize tapa nach tosú ag an tosaigh an liosta a bhí ag smaoineamh maith.

11
00:00:25,000 --> 00:00:29,000
Maith go leor, b'fhéidir ba chóir duit tosú ag obair ar gcúl ó dheireadh an liosta.

12
00:00:29,000 --> 00:00:33,000
Anois, léigh tú Tarzan, Stitch, Snow White, agus mar sin de.

13
00:00:33,000 --> 00:00:36,000
Fós, ní hionann sin is cosúil mhaith an bealach is fearr chun dul faoi.

14
00:00:36,000 --> 00:00:38,000
>> Bhuel, tá ar bhealach eile gur féidir leat dul faoi é seo a dhéanamh chun iarracht a caol síos

15
00:00:38,000 --> 00:00:41,000
liosta ainmneacha na go bhfuil tú chun breathnú ar.

16
00:00:41,000 --> 00:00:43,000
Ós rud é a fhios agat go bhfuil siad in ord aibítre,

17
00:00:43,000 --> 00:00:45,000
d'fhéadfaí tú ach breathnú ar na hainmneacha i lár an liosta

18
00:00:45,000 --> 00:00:49,000
agus seiceáil má tá Mickey Mouse roimh nó tar éis an ainm seo.

19
00:00:49,000 --> 00:00:51,000
Ag Breathnú ar an t-ainm deireanach sa dara colún

20
00:00:51,000 --> 00:00:54,000
gur mhaith leat a thuiscint go M haghaidh Mickey thagann i ndiaidh J le haghaidh Jasmine,

21
00:00:54,000 --> 00:00:57,000
ionas gur mhaith leat neamhaird a dhéanamh ach an chéad leath den liosta.

22
00:00:57,000 --> 00:00:59,000
Ansin gur mhaith leat breathnú is dócha ag barr an cholún deireanach

23
00:00:59,000 --> 00:01:02,000
agus a fheiceáil go dtosaíonn sé le Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey thagann roimh Rapunzel; Breathnaíonn an nós féidir linn neamhaird a dhéanamh den cholún deireanach chomh maith.

25
00:01:06,000 --> 00:01:08,000
Ag leanúint leis an straitéis cuardaigh, feicfidh tú go tapa go Mickey

26
00:01:08,000 --> 00:01:11,000
Is é sa chéad leath de liosta eile na n-ainmneacha

27
00:01:11,000 --> 00:01:14,000
agus a fháil ar deireadh Mickey bhfolach idir Merlin agus Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Bhí Cad a rinne tú díreach search bunúsach dénártha.

29
00:01:17,000 --> 00:01:22,000
Mar Ciallaíonn an t-ainm, a chomhlíonann sé a straitéis a chuardach i ní dénártha.

30
00:01:22,000 --> 00:01:24,000
Cad a chiallaíonn sé seo?

31
00:01:24,000 --> 00:01:27,000
Bhuel, tugtar liosta de na míreanna sórtáilte, cuireann an algartam cuardaigh dénártha cinneadh dénártha -

32
00:01:27,000 --> 00:01:33,000
chlé nó ceart, níos mó ná nó níos lú ná, in ord aibítre roimh nó tar éis - ag gach pointe.

33
00:01:33,000 --> 00:01:35,000
Anois go bhfuil muid ainm a théann in éineacht leis an algartam cuardaigh,

34
00:01:35,000 --> 00:01:38,000
ligean ar breathnú ar shampla eile, ach an uair seo le liosta de uimhreacha curtha in eagar.

35
00:01:38,000 --> 00:01:43,000
Abair táimid ag lorg an uimhir 144 sa liosta d'uimhreacha in eagar.

36
00:01:43,000 --> 00:01:46,000
Díreach mar a bhíodh, feicimid an uimhir sin i lár -

37
00:01:46,000 --> 00:01:50,000
atá sa chás seo 13 - agus a fheiceáil má tá níos mó ná 144 nó níos lú ná 13.

38
00:01:50,000 --> 00:01:54,000
Ós rud é go bhfuil sé soiléir níos mó ná 13, is féidir linn neamhaird a dhéanamh gach rud go bhfuil 13 nó níos lú

39
00:01:54,000 --> 00:01:57,000
agus díriú ach ar an leath eile.

40
00:01:57,000 --> 00:01:59,000
Ós rud é go bhfuil muid anois ar líon na n-ítimí ar chlé, fiú,

41
00:01:59,000 --> 00:02:01,000
táimid a roghnú ach roinnt atá in aice leis an lár.

42
00:02:01,000 --> 00:02:03,000
Sa chás seo roghnaigh muid 55.

43
00:02:03,000 --> 00:02:06,000
D'fhéadfadh muid a bheith chomh héasca céanna roghnaithe 89.

44
00:02:06,000 --> 00:02:11,000
Maith go leor. Arís, tá 144 níos mó ná 55, mar sin againn dul go dtí an ceart.

45
00:02:11,000 --> 00:02:14,000
Fortunately dúinn, is é an uimhir lár chéad 144,

46
00:02:14,000 --> 00:02:16,000
an ceann táimid ag lorg.

47
00:02:16,000 --> 00:02:21,000
Mar sin, chun teacht ar 144 ag baint úsáide as cuardaigh dénártha, tá muid in ann a aimsiú i ach 3 céimeanna.

48
00:02:21,000 --> 00:02:24,000
Má ba mhaith linn a úsáid cuardaigh líneach anseo, bheadh ​​sé tar éis dúinn 12 céimeanna.

49
00:02:24,000 --> 00:02:28,000
Mar ábhar na fírinne, ós rud é leatha an modh cuardaigh líon na míreanna

50
00:02:28,000 --> 00:02:31,000
tá sé chun breathnú ar ag gach céim, beidh sé teacht ar an mír go bhfuil sé ag lorg

51
00:02:31,000 --> 00:02:35,000
i thart ar an logáil isteach ar líon na míreanna ar an liosta.

52
00:02:35,000 --> 00:02:37,000
Anois go atá feicthe againn 2 samplaí, a ligean ar ghlacadh le breathnú ar

53
00:02:37,000 --> 00:02:41,000
roinnt pseudocode maidir le feidhm athchúrsach go gcuireann cuardaigh dénártha.

54
00:02:41,000 --> 00:02:44,000
Ag tosú ag an mbarr, a fheicimid go bhfuil muid a aimsiú feidhm a thógann 4 hargóintí:

55
00:02:44,000 --> 00:02:47,000
eochair, eagar, min, agus uas.

56
00:02:47,000 --> 00:02:51,000
Is í an eochair an líon go bhfuil muid ag lorg, mar sin 144 sa sampla roimhe seo.

57
00:02:51,000 --> 00:02:54,000
Is é Eagar liosta na huimhreacha go bhfuil muid ag cuardach.

58
00:02:54,000 --> 00:02:57,000
Tá Min agus uas na hinnéacsanna de na poist íosta agus uasta

59
00:02:57,000 --> 00:02:59,000
go bhfuil muid ag lorg faoi láthair ag.

60
00:02:59,000 --> 00:03:03,000
Mar sin, nuair a thosaíonn muid, beidh min nialas agus beidh uas bheidh an t-innéacs is mó ar an eagar.

61
00:03:03,000 --> 00:03:07,000
Mar againn caol an chuardaigh síos, beidh muid thabhairt cothrom le dáta min agus uas

62
00:03:07,000 --> 00:03:10,000
a bheith go díreach ar an réimse go bhfuil muid ag lorg fós ag isteach

63
00:03:10,000 --> 00:03:12,000
>> A ligean ar skip to an chuid suimiúil ar dtús.

64
00:03:12,000 --> 00:03:14,000
Is é an chéad rud a dhéanann muid ag teacht ar an lárphointe,

65
00:03:14,000 --> 00:03:19,000
an t-innéacs go bhfuil leath bealaigh idir an min agus uas ar an réimse go bhfuil muid ag smaoineamh go fóill.

66
00:03:19,000 --> 00:03:22,000
Ansin muid ag breathnú ar luach an eagar ag an suíomh lárphointe

67
00:03:22,000 --> 00:03:25,000
agus a fheiceáil má tá an uimhir go bhfuil muid ag lorg ar feadh níos lú ná an eochair.

68
00:03:25,000 --> 00:03:27,000
Má tá an líon ag an suíomh níos lú,

69
00:03:27,000 --> 00:03:31,000
ansin ciallaíonn sé go bhfuil an eochair níos mó ná na huimhreacha ar an taobh clé an phoist sin.

70
00:03:31,000 --> 00:03:33,000
Mar sin, is féidir linn a glaoch fheidhm cuardaigh dénártha arís,

71
00:03:33,000 --> 00:03:36,000
ach an uair seo cothrom le dáta an min agus paraiméadair max a léamh ach an leath

72
00:03:36,000 --> 00:03:40,000
is é sin níos mó ná nó cothrom le luach fhéach muid díreach ar.

73
00:03:40,000 --> 00:03:44,000
Ar an láimh eile, má tá an eochair níos lú ná an uimhir ag an lárphointe reatha an eagar,

74
00:03:44,000 --> 00:03:47,000
ba mhaith linn dul ar chlé agus na huimhreacha go bhfuil níos mó neamhaird a dhéanamh.

75
00:03:47,000 --> 00:03:52,000
Arís, tugaimid cuardaigh dhénártha ach an uair seo leis an réimse de min agus uas Nuashonraithe

76
00:03:52,000 --> 00:03:54,000
a chur san áireamh ach an leath níos ísle.

77
00:03:54,000 --> 00:03:57,000
Má tá an luach ag an lárphointe reatha sa réimse nach

78
00:03:57,000 --> 00:04:01,000
níos mó ná ná níos lú ná an eochair, ansin caithfidh sé a bheith comhionann leis an eochair.

79
00:04:01,000 --> 00:04:05,000
Dá bhrí sin, is féidir linn ar ais ach an t-innéacs lárphointe atá ann faoi láthair, agus táimid ag déanamh.

80
00:04:05,000 --> 00:04:09,000
Ar deireadh, tá an seic anseo le haghaidh an cás go bhfuil an líon

81
00:04:09,000 --> 00:04:11,000
nach bhfuil i ndáiríre i sraith de uimhreacha muid ag cuardach.

82
00:04:11,000 --> 00:04:14,000
Más rud é an t-innéacs is mó ar an raon go bhfuil muid ag lorg

83
00:04:14,000 --> 00:04:17,000
Tá riamh níos lú ná an t-íosmhéid, ciallaíonn sé sin go againn imithe i bhfad ró.

84
00:04:17,000 --> 00:04:20,000
Ós rud é nach raibh an uimhir sa sraith ionchur, ar ais dúinn -1

85
00:04:20,000 --> 00:04:24,000
Fuarthas go raibh a chur in iúl go bhfuil aon rud.

86
00:04:24,000 --> 00:04:26,000
>> Féadfaidh tú faoi deara gur le haghaidh an algartam a bheith ag obair,

87
00:04:26,000 --> 00:04:28,000
Tá an liosta d'uimhreacha a shórtáil.

88
00:04:28,000 --> 00:04:31,000
I bhfocail eile, is féidir linn a fháil ach 144 ag baint úsáide as cuardaigh dénártha

89
00:04:31,000 --> 00:04:34,000
má chomhlíontar na huimhreacha ordú ó ísle is airde.

90
00:04:34,000 --> 00:04:38,000
Más rud é nach raibh seo an cás, ní bheadh ​​muid in ann a eisiamh leath de na huimhreacha ag gach céim.

91
00:04:38,000 --> 00:04:40,000
Mar sin, ní mór dúinn 2 rogha.

92
00:04:40,000 --> 00:04:43,000
Amháin nó is féidir linn a ghlacadh liosta neamhshórtáilte agus é a shórtáil roimh úsáid a bhaint as cuardaigh dhénártha,

93
00:04:43,000 --> 00:04:48,000
nó is féidir linn a dhéanamh cinnte go bhfuil an liosta d'uimhreacha curtha in eagar agus muid ag uimhreacha a chur air.

94
00:04:48,000 --> 00:04:50,000
Dá bhrí sin, in ionad a shórtáil ach nuair atá againn chun cuardach a dhéanamh,

95
00:04:50,000 --> 00:04:53,000
cén fáth nach a choinneáil ar an liosta a shórtáil i gcónaí?

96
00:04:53,000 --> 00:04:57,000
>> Bhealach amháin a choimeád liosta d'uimhreacha curtha in eagar a ligean ag an am céanna

97
00:04:57,000 --> 00:04:59,000
amháin a chur leis nó bogadh uimhreacha ón liosta seo

98
00:04:59,000 --> 00:05:02,000
Is trí úsáid a bhaint as rud ar a dtugtar crann cuardaigh dénártha.

99
00:05:02,000 --> 00:05:05,000
Is éard is crann cuardaigh dénártha struchtúr sonraí go bhfuil 3 airíonna.

100
00:05:05,000 --> 00:05:09,000
Gcéad dul síos, tá subtree chlé ar aon nód luachanna amháin go bhfuil níos lú ná

101
00:05:09,000 --> 00:05:11,000
nó is comhionann leis an nód luach.

102
00:05:11,000 --> 00:05:15,000
Dara, tá subtree ceart nód amháin luachanna atá níos mó ná

103
00:05:15,000 --> 00:05:17,000
nó is comhionann leis an nód luach.

104
00:05:17,000 --> 00:05:20,000
Agus, ar deireadh, idir na subtrees chlé agus ar dheis gach nód

105
00:05:20,000 --> 00:05:23,000
Tá crainn cuardaigh dénártha.

106
00:05:23,000 --> 00:05:26,000
Ligean ar breathnú ar shampla leis an líon céanna a úsáid againn níos luaithe.

107
00:05:26,000 --> 00:05:30,000
Mar sin de tú riamh a bhfuil le feiceáil crann eolaíocht ríomhaireachta roimh,

108
00:05:30,000 --> 00:05:34,000
in iúl dom tosú ag rá leat go bhfuil a fhásann crann eolaíocht ríomhaireachta síos.

109
00:05:34,000 --> 00:05:36,000
Sea, murab ionann agus crainn tú i dtaithí ar,

110
00:05:36,000 --> 00:05:38,000
Is é an fhréamh an chrainn eolaíocht ríomhaireachta ag an mbarr,

111
00:05:38,000 --> 00:05:41,000
agus tá na duilleoga ag bun an leathanaigh.

112
00:05:41,000 --> 00:05:45,000
Tá gach bosca beag ar a dtugtar nód, agus na nóid ceangailte le chéile, trí imill.

113
00:05:45,000 --> 00:05:48,000
Dá bhrí sin tá an fhréamh an crann luach nód le luach 13,

114
00:05:48,000 --> 00:05:52,000
a bhfuil 2 nóid leanaí leis na luachanna 5 agus 34.

115
00:05:52,000 --> 00:05:57,000
Tá subtree an crann go bhfuil déanta ach ag féachaint ar fho-alt de na crainn ar fad.

116
00:05:57,000 --> 00:06:03,000
>> Mar shampla, is é an subtree clé den 3 nód an crann cruthaithe ag an nóid 0, 1, agus 2.

117
00:06:03,000 --> 00:06:06,000
Mar sin, má théann muid ar ais go dtí na hairíonna de crann cuardaigh dénártha,

118
00:06:06,000 --> 00:06:09,000
feicimid go gcloíonn gach nód i an chrainn go dtí na 3 maoin, is é sin,

119
00:06:09,000 --> 00:06:15,000
an subtree chlé bhfuil ach na luachanna atá níos lú ná nó cothrom leis an nód ar luach;

120
00:06:15,000 --> 00:06:16,000
an subtree ceart gach nód

121
00:06:16,000 --> 00:06:19,000
ach tá na luachanna atá níos mó ná nó cothrom leis an nód luach; agus

122
00:06:19,000 --> 00:06:25,000
Tá subtrees araon chlé agus ar dheis gach nód freisin crainn cuardaigh dénártha.

123
00:06:25,000 --> 00:06:28,000
Cé go Breathnaíonn an crann éagsúla, tá sé seo le crann cuardaigh bailí dhénártha

124
00:06:28,000 --> 00:06:30,000
an tsraith chéanna uimhreacha.

125
00:06:30,000 --> 00:06:32,000
Mar ábhar na fírinne, tá bealaí is féidir go leor gur féidir leat a chruthú

126
00:06:32,000 --> 00:06:35,000
crann cuardaigh bailí dhénártha ó na huimhreacha seo.

127
00:06:35,000 --> 00:06:38,000
Bhuel, a ligean ar dul ar ais chuig an chéad cheann cruthaithe againn.

128
00:06:38,000 --> 00:06:40,000
Mar sin, cad is féidir linn a dhéanamh leis na crainn?

129
00:06:40,000 --> 00:06:44,000
Bhuel, is féidir linn an-simplí a fháil ar na luachanna íosta agus uasta.

130
00:06:44,000 --> 00:06:46,000
Is féidir na luachanna íosta a fháil ag dul i gcónaí ar an taobh clé

131
00:06:46,000 --> 00:06:48,000
go dtí go bhfuil nóid níos mó chun cuairt a thabhairt.

132
00:06:48,000 --> 00:06:53,000
Os a choinne sin, chun teacht ar an gceann is mó a théann ach amháin síos go dtí an ceart ag gach uair.

133
00:06:54,000 --> 00:06:56,000
>> Ag Lorg aon uimhir eile nach bhfuil an t-íosmhéid nó an uasmhéid

134
00:06:56,000 --> 00:06:58,000
Is é díreach chomh furasta.

135
00:06:58,000 --> 00:07:00,000
Abair táimid ag lorg an uimhir 89.

136
00:07:00,000 --> 00:07:03,000
Táimid ag seiceáil ach an luach gach nód agus téigh go dtí an taobh clé nó ceart,

137
00:07:03,000 --> 00:07:06,000
ag brath ar cibé an bhfuil an nód ar luach níos lú ná nó níos mó ná

138
00:07:06,000 --> 00:07:08,000
an ceann táimid ag lorg.

139
00:07:08,000 --> 00:07:11,000
Mar sin, ag tosú ar an fhréamh 13, linn a fheiceáil go bhfuil 89 níos mó,

140
00:07:11,000 --> 00:07:13,000
agus mar sin táimid ag dul go dtí an ceart.

141
00:07:13,000 --> 00:07:16,000
Ansin linn a fheiceáil an nód le haghaidh 34, agus arís muid ag dul go dtí an ceart.

142
00:07:16,000 --> 00:07:20,000
89 tá sé fós níos mó ná 55, mar sin againn leanúint ag dul go dtí an ceart.

143
00:07:20,000 --> 00:07:24,000
Táimid ag teacht ansin suas le nód le luach 144 agus téigh go dtí an taobh clé.

144
00:07:24,000 --> 00:07:26,000
Lo agus behold, 89 tá ceart ann.

145
00:07:26,000 --> 00:07:31,000
>> Tá rud eile gur féidir linn a dhéanamh phriontáil amach na huimhreacha ag comhlíonadh an traversal inorder.

146
00:07:31,000 --> 00:07:35,000
An traversal inorder ciallaíonn rud a phriontáil amach sa subtree chlé

147
00:07:35,000 --> 00:07:37,000
le leanúint ag priontáil an nód féin

148
00:07:37,000 --> 00:07:40,000
agus leanúint ansin le priontáil gach rud amach sa subtree ceart.

149
00:07:40,000 --> 00:07:43,000
Mar shampla, a ligean ar chur ar ár crann cuardaigh is fearr leat dhénártha

150
00:07:43,000 --> 00:07:46,000
agus a phriontáil amach na huimhreacha in ord sórtáilte.

151
00:07:46,000 --> 00:07:49,000
Tús a chur againn ar an fhréamh 13, ach roimh priontáil 13 ní mór dúinn a phriontáil amach

152
00:07:49,000 --> 00:07:51,000
gach rud sa subtree chlé.

153
00:07:51,000 --> 00:07:55,000
Mar sin, táimid ag dul go dtí 5. Tá fós ag dul níos doimhne síos sa crann go dtí go bhfaighidh muid an nód clé an chuid is mó,

154
00:07:55,000 --> 00:07:57,000
atá nialas.

155
00:07:57,000 --> 00:08:00,000
Tar éis an priontáil náid, théann muid ar ais suas go dtí an 1 agus a phriontáil sin amach.

156
00:08:00,000 --> 00:08:03,000
Ansin againn dul go dtí an subtree ceart, a bhfuil 2, agus go amach a phriontáil.

157
00:08:03,000 --> 00:08:05,000
Anois go bhfuil muid ag déanamh leis an subtree,

158
00:08:05,000 --> 00:08:07,000
is féidir linn dul ar ais suas go dtí an 3 agus í a phriontáil amach.

159
00:08:07,000 --> 00:08:11,000
Leanúint ar ais ar bun, a phriontáil againn ar an 5 agus ansin an 8.

160
00:08:11,000 --> 00:08:13,000
Anois go bhfuil muid i gcrích an iomlán d'fhág subtree,

161
00:08:13,000 --> 00:08:17,000
is féidir linn a phriontáil amach 13 agus tosú ag obair ar an subtree ceart.

162
00:08:17,000 --> 00:08:21,000
Hap againn síos go dtí 34, ach roimh priontáil 34 ní mór dúinn a phriontáil amach a subtree chlé.

163
00:08:21,000 --> 00:08:27,000
Mar sin, linn a phriontáil amach 21; ansin a fháil againn a phriontáil amach 34 agus a subtree cheart cuairt a thabhairt.

164
00:08:27,000 --> 00:08:31,000
Ós rud é go bhfuil 55 aon subtree chlé, ní mór dúinn é a phriontáil amach agus a lean ar aghaidh go dtí a subtree ceart.

165
00:08:31,000 --> 00:08:36,000
144 Tá subtree chlé, agus mar sin linn a phriontáil amach an 89, le leanúint ag an 144,

166
00:08:36,000 --> 00:08:39,000
agus ar deireadh an nód ceart-chuid is mó de 233.

167
00:08:39,000 --> 00:08:44,000
Tá tú é; na huimhreacha go léir i gcló amach in ord ó ísle is airde.

168
00:08:44,000 --> 00:08:47,000
>> Nuair a chuirfear rud éigin chun an crann is réasúnta painless chomh maith.

169
00:08:47,000 --> 00:08:51,000
Gach ní mór dúinn a dhéanamh ná a chinntiú go leanaimid 3 airíonna dhénártha crann cuardaigh

170
00:08:51,000 --> 00:08:53,000
agus cuir isteach ansin an luacha sa chás go bhfuil spás.

171
00:08:53,000 --> 00:08:55,000
Ligean le rá ba mhaith linn a chur isteach ar an luach de 7.

172
00:08:55,000 --> 00:08:58,000
Ós rud é go 7 níos lú ná 13, ní mór dúinn dul go dtí an taobh clé.

173
00:08:58,000 --> 00:09:01,000
Ach tá sé níos mó ná 5, mar sin againn trasna na láimhe deise.

174
00:09:01,000 --> 00:09:04,000
Ós rud é go bhfuil sé níos lú ná mar atá 8 agus 8 nód duille, cuir muid 7 leis an leanbh taobh clé de 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Táimid tar éis Chuir roinnt dár crann cuardaigh dénártha.

176
00:09:09,000 --> 00:09:12,000
>> Más féidir linn rudaí a chur, ní mór dúinn a bheith níos fearr in ann rudaí a scriosadh chomh maith.

177
00:09:12,000 --> 00:09:14,000
Ar an drochuair dúinn, is é a scriosadh le beagán níos casta -

178
00:09:14,000 --> 00:09:16,000
nach bhfuil i bhfad, ach amháin le beagán.

179
00:09:16,000 --> 00:09:18,000
Tá 3 cásanna difriúla atá againn a mheas

180
00:09:18,000 --> 00:09:21,000
nuair eilimintí scriosadh ó chrainn cuardaigh dénártha.

181
00:09:21,000 --> 00:09:24,000
An chéad, is é an cás éasca go bhfuil gné nód duille.

182
00:09:24,000 --> 00:09:27,000
Sa chás seo, táimid ag scriosadh ach é agus dul ar aghaidh leis an ár ngnó.

183
00:09:27,000 --> 00:09:30,000
Abair ba mhaith linn a scriosadh le linn na 7 gur chuir muid díreach.

184
00:09:30,000 --> 00:09:34,000
Bhuel, linn a fháil ach é, é a bhaint di, agus go bhfuil sé.

185
00:09:35,000 --> 00:09:37,000
Is é an chéad chás eile má tá an nód ach 1 leanbh ann.

186
00:09:37,000 --> 00:09:40,000
Anseo, is féidir linn a scriosadh an nód, ach ní mór dúinn an chéad a dhéanamh cinnte go

187
00:09:40,000 --> 00:09:42,000
a cheangal ar an subtree go bhfuil fágtha anois parentless

188
00:09:42,000 --> 00:09:44,000
le tuismitheoir an nód a scriosadh againn ach.

189
00:09:44,000 --> 00:09:47,000
Abair ba mhaith linn a scriosadh 3 as ár crann.

190
00:09:47,000 --> 00:09:50,000
Glacann muid an eilimint leanbh an nód agus é ag gabháil leis an tuismitheoir an nód.

191
00:09:50,000 --> 00:09:54,000
Sa chás seo, tá muid ag gabháil anois 1 a ghabhann 5.

192
00:09:54,000 --> 00:09:57,000
Oibríonn sé seo gan fadhb mar a fhios againn, de réir an dénártha maoine cuardaigh crann,

193
00:09:57,000 --> 00:10:01,000
go raibh gach rud sa subtree na láimhe clé den 3 níos lú ná 5.

194
00:10:01,000 --> 00:10:05,000
Anois go bhfuil 3 ar subtree a glacadh de chúram, is féidir linn a scriosadh é.

195
00:10:05,000 --> 00:10:08,000
Is é an tríú cás agus deiridh na cinn is casta.

196
00:10:08,000 --> 00:10:11,000
Is é seo an cás nuair a bhíonn an nód ba mhaith linn a scriosadh 2 leanbh.

197
00:10:11,000 --> 00:10:15,000
D'fhonn é seo a dhéanamh, ní mór dúinn an chéad a fháil ar an nód go bhfuil an luach is mó,

198
00:10:15,000 --> 00:10:18,000
babhtála an dá, agus ansin an nód atá i gceist a scriosadh.

199
00:10:18,000 --> 00:10:22,000
Fógra an nód go bhfuil nach féidir an luach eile is mó a bheith 2 leanbh féin

200
00:10:22,000 --> 00:10:26,000
ós rud é go mbeadh ar a leanbh chlé iarrthóir níos fearr do na is mó atá romhainn.

201
00:10:26,000 --> 00:10:30,000
Dá bhrí sin, méideanna a scriosadh nód le 2 leanbh a swapping de 2 nóid,

202
00:10:30,000 --> 00:10:33,000
agus ansin a scriosadh láimhseáil ag 1 de 2 rialacha thuasluaite.

203
00:10:33,000 --> 00:10:37,000
Mar shampla, a rá a ligean ar mhaith linn a scriosadh an nód fréimhe, 13.

204
00:10:37,000 --> 00:10:39,000
Is é an chéad rud a dhéanann muid linn teacht ar an luach eile is mó sa crann

205
00:10:39,000 --> 00:10:41,000
atá, sa chás seo, is é 21.

206
00:10:41,000 --> 00:10:46,000
Táimid ag babhtála ansin an 2 nóid, a dhéanamh 13 le duille agus 21 an nód ghrúpa lárnach.

207
00:10:46,000 --> 00:10:49,000
Anois is féidir linn a scriosadh ach 13.

208
00:10:50,000 --> 00:10:53,000
>> Mar a léiríodh níos luaithe, tá bealaí is féidir go leor a dhéanamh crann cuardaigh bailí dénártha.

209
00:10:53,000 --> 00:10:56,000
Ar an drochuair dúinn, tá roinnt níos measa ná a chéile.

210
00:10:56,000 --> 00:10:59,000
Mar shampla, cad a tharlaíonn nuair a thógáil againn crann cuardaigh dénártha

211
00:10:59,000 --> 00:11:01,000
ó liosta sórtáilte, uimhreacha?

212
00:11:01,000 --> 00:11:04,000
Na huimhreacha a leanas ach an ceart ag gach céim.

213
00:11:04,000 --> 00:11:06,000
Nuair a ba mhaith linn a chuardach le haghaidh roinnt,

214
00:11:06,000 --> 00:11:08,000
ní mór dúinn aon rogha ach amháin chun breathnú ar an ceart ag gach céim.

215
00:11:08,000 --> 00:11:11,000
Ní hé seo níos fearr ná cuardach líneach ar chor ar bith.

216
00:11:11,000 --> 00:11:13,000
Cé nach mbeidh muid iad a chlúdach anseo, tá eile, níos casta,

217
00:11:13,000 --> 00:11:16,000
struchtúir sonraí a chinntiú nach dtarlaíonn sé seo.

218
00:11:16,000 --> 00:11:18,000
Mar sin féin, tá rud amháin simplí féidir a dhéanamh chun seo a sheachaint

219
00:11:18,000 --> 00:11:21,000
go dtí díreach Suaitheadh ​​randamach na luachanna ionchuir.

220
00:11:21,000 --> 00:11:26,000
Tá sé an-dócha go bhfuil de sheans randamach liosta shuffled de uimhreacha curtha in eagar.

221
00:11:26,000 --> 00:11:29,000
Má bhí seo an cás, ní bheadh ​​casinos fanacht sa ghnó le fada.

222
00:11:29,000 --> 00:11:31,000
>> Tá tú é.

223
00:11:31,000 --> 00:11:34,000
Tá a fhios agat anois faoi chuardach dhénártha agus crainn cuardaigh dénártha.

224
00:11:34,000 --> 00:11:36,000
Tá mé Patrick Schmid, agus tá sé seo CS50.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
Slí amháin soiléir a bheith a scanadh ar an liosta ó ... [bíp]

227
00:11:43,000 --> 00:11:46,000
... Líon na míreanna ... yep

228
00:11:46,000 --> 00:11:50,000
[Gáirí]

229
00:11:50,000 --> 00:11:55,000
... Post nód de 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Go raibh -