1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Duuma Serĉu]

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

3
00:00:04,000 --> 00:00:07,000
[Jen CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Se mi donis al vi liston de Disney karaktero nomojn en alfabeta ordo

5
00:00:09,000 --> 00:00:11,000
kaj demandis vin trovi Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
kiel vi irados tra faras tion?

7
00:00:13,000 --> 00:00:15,000
Unu evidenta maniero estus skani la listo de la komenco

8
00:00:15,000 --> 00:00:18,000
kaj kontrolu ĉiun nomon por vidi se ĝi estas Mickey.

9
00:00:18,000 --> 00:00:22,000
Sed kiel vi legas Aladino, Alicia, Ariel, kaj tiel plu,

10
00:00:22,000 --> 00:00:25,000
vi rapide rimarkas ke ekde la fronto de la listo ne estis bona ideo.

11
00:00:25,000 --> 00:00:29,000
Konsentite, eble vi devus komenci labori malantaŭen de la fino de la listo.

12
00:00:29,000 --> 00:00:33,000
Nun vi legis Tarzan, Stitch, Snow White, kaj tiel plu.

13
00:00:33,000 --> 00:00:36,000
Ankoraŭ, ĉi tio ne ŝajnas kiel la pli bona maniero por iri sur ĝi.

14
00:00:36,000 --> 00:00:38,000
>> Nu, alia vojo, kiun vi povus iri pri fari ĉi estas provi mallarĝigi malsupren

15
00:00:38,000 --> 00:00:41,000
la listo de nomoj kiuj vi devas rigardi.

16
00:00:41,000 --> 00:00:43,000
Ĉar vi scias, ke ili estas en alfabeta ordo,

17
00:00:43,000 --> 00:00:45,000
vi povus simple rigardu la nomojn en la mezo de la listo

18
00:00:45,000 --> 00:00:49,000
kaj kontrolu ĉu Mickey Mouse estas antaŭ aŭ post ĉi nomo.

19
00:00:49,000 --> 00:00:51,000
Rigardante la familinomo en la dua kolumno

20
00:00:51,000 --> 00:00:54,000
vi volas kompreni ke M por Mickey venas post J por Jasmine,

21
00:00:54,000 --> 00:00:57,000
tiel vi volas simple ignoru la unua duono de la listo.

22
00:00:57,000 --> 00:00:59,000
Tiam vi havus verŝajne rigardu la supron de la lasta kolumno

23
00:00:59,000 --> 00:01:02,000
kaj vidu, ke ĝi komencas kun Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey venas antaux Rapunzel; aspektas kiel ni povas ignori la lasta kolumno tiel.

25
00:01:06,000 --> 00:01:08,000
Daŭrigante la serĉo strategio, vi rapide vidas ke Mickey

26
00:01:08,000 --> 00:01:11,000
estas en la unua duono de la cetera listo de nomoj

27
00:01:11,000 --> 00:01:14,000
kaj fine trovos Mickey kaŝas inter Merlin kaj Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Kion vi ĵus faris estis esence duuma serĉo.

29
00:01:17,000 --> 00:01:22,000
Kiel ĉi nomo implicas, ĝi realigas lian traserĉado strategio en duuma afero.

30
00:01:22,000 --> 00:01:24,000
Kion tio signifas?

31
00:01:24,000 --> 00:01:27,000
Nu, donita listo de ordo erojn, la duuma serĉo algoritmo faras duuma decido -

32
00:01:27,000 --> 00:01:33,000
maldekstra aŭ dekstra, pli granda ol aŭ malpli ol, alfabete antaŭ aŭ post - je ĉiu punkto.

33
00:01:33,000 --> 00:01:35,000
Nun ke ni havas nomon kiu iras kune kun ĉi tiu serĉo algoritmo,

34
00:01:35,000 --> 00:01:38,000
ni rigardu alian ekzemplon, sed ĉi-foje kun listo de ordo numerojn.

35
00:01:38,000 --> 00:01:43,000
Diru ni serĉas la numeron 144 en la listo de ordo numerojn.

36
00:01:43,000 --> 00:01:46,000
Ĝuste kiel antaŭe, ni trovas la numero kiu estas en la mezo -

37
00:01:46,000 --> 00:01:50,000
kiu en ĉi tiu kazo estas 13 - kaj vidi se 144 estas pli granda ol aŭ malpli ol 13.

38
00:01:50,000 --> 00:01:54,000
Ekde ĝi estas klare pli granda ol 13, ni povas ignori cxion tio estas 13 aŭ malpli

39
00:01:54,000 --> 00:01:57,000
kaj nur koncentriĝi sur la ceteraj duono.

40
00:01:57,000 --> 00:01:59,000
Ĉar ni nun havas para kvanto de eroj restis,

41
00:01:59,000 --> 00:02:01,000
ni simple elektu numeron kiu estas proksima al la centro.

42
00:02:01,000 --> 00:02:03,000
En ĉi tiu kazo ni elekti 55.

43
00:02:03,000 --> 00:02:06,000
Ni povis esti nur tiel facile elektita 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Denove, 144 estas pli granda ol 55, do ni iru al la rajto.

45
00:02:11,000 --> 00:02:14,000
Feliĉe por ni, la sekva duona nombro estas 144,

46
00:02:14,000 --> 00:02:16,000
la ni serĉas.

47
00:02:16,000 --> 00:02:21,000
Do, por trovi 144 uzanta duuma serĉo, ni povis trovi ĝin en nur 3 paŝoj.

48
00:02:21,000 --> 00:02:24,000
Se ni estus uzinta lineara serĉo tie, ĝi estus prenita ni 12 paŝoj.

49
00:02:24,000 --> 00:02:28,000
Kiel Efektive, ekde ĉi serĉo metodo duonoj la nombro de artikoloj

50
00:02:28,000 --> 00:02:31,000
ĝi devas rigardi je ĉiu paŝo, ke trovos la eron ĝi serĉas

51
00:02:31,000 --> 00:02:35,000
en ĉirkaŭ la logo de la nombro de artikoloj en la listo.

52
00:02:35,000 --> 00:02:37,000
Nun kiam ni vidis 2 ekzemploj, ni rigardu

53
00:02:37,000 --> 00:02:41,000
iuj _pseudocode_ por rekursie funkcio kiu implementa duuma serĉo.

54
00:02:41,000 --> 00:02:44,000
Ekde la supro, ni vidas ke ni devas trovi funkcio kiu prenas 4 argumentoj:

55
00:02:44,000 --> 00:02:47,000
klavo, tabelo, min, kaj max.

56
00:02:47,000 --> 00:02:51,000
La ŝlosilo estas la numero kiu ni serĉas, do 144 en la antaŭa ekzemplo.

57
00:02:51,000 --> 00:02:54,000
Array estas la listo de nombroj kiun ni sercxas.

58
00:02:54,000 --> 00:02:57,000
Min kaj max estas la indeksoj de la minimuma kaj maksimuma pozicioj

59
00:02:57,000 --> 00:02:59,000
ke ni nuntempe rigardante.

60
00:02:59,000 --> 00:03:03,000
Do kiam ni komencas, min estos nulo kaj max estos la maksimuma indekso de la tabelo.

61
00:03:03,000 --> 00:03:07,000
Kiel ni malpligrandigi la serĉo sube, ni ĝisdatigi min kaj max

62
00:03:07,000 --> 00:03:10,000
esti nur la rango kiun ni daŭre serĉas in

63
00:03:10,000 --> 00:03:12,000
>> Ni salti al la interesa parto unua.

64
00:03:12,000 --> 00:03:14,000
La unua aĵo kiun ni faras estas trovi la mezpunkto,

65
00:03:14,000 --> 00:03:19,000
la indekso tio estas duonvoje inter la min kaj max de la tabelo, ke ni ankoraŭ konsiderante.

66
00:03:19,000 --> 00:03:22,000
Tiam ni rigardas la valoro de la tabelo en tiu mezpunkto situo

67
00:03:22,000 --> 00:03:25,000
kaj vidi se la numero kiun ni serĉas estas malpli ol tiu ŝlosilo.

68
00:03:25,000 --> 00:03:27,000
Se la nombro en tiu pozicio estas malpli,

69
00:03:27,000 --> 00:03:31,000
tiam signifas la ŝlosilo estas pli granda ol ĉiuj nombroj maldekstre de tiu pozicio.

70
00:03:31,000 --> 00:03:33,000
Do ni povas nomi duuma serĉo funkcio denove,

71
00:03:33,000 --> 00:03:36,000
sed ĉi tiu fojo ĝisdatigi la min kaj max parametroj por legi nur la duono

72
00:03:36,000 --> 00:03:40,000
kiu estas pli granda ol aŭ egala al la valoro ni nur rigardis.

73
00:03:40,000 --> 00:03:44,000
Aliflanke, se la ŝlosilo estas malpli ol la nombro en la nuna mezpunkto de la tabelo,

74
00:03:44,000 --> 00:03:47,000
ni volas iri al la maldekstra kaj ignori ĉiuj nombroj kiuj estas pli grandaj.

75
00:03:47,000 --> 00:03:52,000
Denove, ni nomas duuma serĉo sed ĉi-foje kun la gamo de min kaj max ĝisdatigita

76
00:03:52,000 --> 00:03:54,000
enmeti nur la suba duono.

77
00:03:54,000 --> 00:03:57,000
Se la valoro je la nuna mezpunkto en la tabelo estas nek

78
00:03:57,000 --> 00:04:01,000
pli granda ol nek pli malgranda ol la ŝlosilo, tiam devas esti egala al la ŝlosilo.

79
00:04:01,000 --> 00:04:05,000
Tiel, ni povas simple reveni la nuna mezpunkto indekso, kaj oni faris.

80
00:04:05,000 --> 00:04:09,000
Fine, tiu ĉeko jen por la kazo ke la numero

81
00:04:09,000 --> 00:04:11,000
ne estas vere en la tabelo de nombroj kiun ni sercxas.

82
00:04:11,000 --> 00:04:14,000
Se la maksimuma indekso de la gamo, ke ni serĉas

83
00:04:14,000 --> 00:04:17,000
estas iam malpli ol la minimumo, ke signifas, ke ni iris tro for.

84
00:04:17,000 --> 00:04:20,000
Ekde la nombro ne estis en la enigo tabelo, ni revenas -1

85
00:04:20,000 --> 00:04:24,000
por indiki, ke nenio estis trovita.

86
00:04:24,000 --> 00:04:26,000
>> Vi eble rimarkis, ke por ĉi tiu algoritmo por labori,

87
00:04:26,000 --> 00:04:28,000
la listo de nombroj devas esti ordo.

88
00:04:28,000 --> 00:04:31,000
En aliaj vortoj, ni nur povas trovi 144 uzanta duuma serĉo

89
00:04:31,000 --> 00:04:34,000
se ĉiuj nombroj estas ordigitaj de plej malalta al plej alta.

90
00:04:34,000 --> 00:04:38,000
Se ĉi tiu ne estis la kazo, ni ne povus ekskludi la duono de la nombroj en ĉiu paŝo.

91
00:04:38,000 --> 00:04:40,000
Do ni havas 2 eblojn.

92
00:04:40,000 --> 00:04:43,000
Ĉu ni povas preni unsorted listo kaj ordigi ĝin antaŭ uzante duuma serĉo,

93
00:04:43,000 --> 00:04:48,000
aŭ ni povas certigi, ke la listo de nombroj estas ordo, kiel ni aldonu nombroj al ĝi.

94
00:04:48,000 --> 00:04:50,000
Tiel, anstataŭ ordigi ĝuste kiam ni devas esplori,

95
00:04:50,000 --> 00:04:53,000
kial ne subteni la listo ordo ĉiutempe?

96
00:04:53,000 --> 00:04:57,000
>> Unu maniero teni liston de nombroj ordo samtempe permesi

97
00:04:57,000 --> 00:04:59,000
unu por aldoni aŭ movi nombroj de ĉi tiu listo

98
00:04:59,000 --> 00:05:02,000
estas per uzo iun nomita duuma serĉarbo.

99
00:05:02,000 --> 00:05:05,000
A duuma serĉarbo estas datumstrukturo kiu havas 3 propraĵoj.

100
00:05:05,000 --> 00:05:09,000
Unue, la maldekstra subarbo de ajna nodo enhavas nur valoroj kiuj estas malpli ol

101
00:05:09,000 --> 00:05:11,000
aŭ egala al la nodo valoron.

102
00:05:11,000 --> 00:05:15,000
Due, la dekstra subárbol de nodo nur enhavas valorojn kiuj estas pli granda ol

103
00:05:15,000 --> 00:05:17,000
aŭ egala al la nodo valoron.

104
00:05:17,000 --> 00:05:20,000
Kaj, fine, tiel la maldekstra kaj dekstra subárboles de ĉiuj nodoj

105
00:05:20,000 --> 00:05:23,000
Ankaŭ estas duuma serĉo arboj.

106
00:05:23,000 --> 00:05:26,000
Ni rigardu ekzemplon kun la samaj numeroj ni uzis antaŭe.

107
00:05:26,000 --> 00:05:30,000
Por tiuj el vi, kiuj neniam vidis komputika arbo antaŭe,

108
00:05:30,000 --> 00:05:34,000
lasu min komenci per diras al vi ke komputika arbo kreskas suben.

109
00:05:34,000 --> 00:05:36,000
Jes, kontraste arboj vi kutimas,

110
00:05:36,000 --> 00:05:38,000
la radiko de komputika arbo estas ĉe la supro,

111
00:05:38,000 --> 00:05:41,000
kaj la folioj estas en la fundo.

112
00:05:41,000 --> 00:05:45,000
Ĉiu malgranda skatolo estas nomita nodo, kaj la nodoj estas konektitaj inter aliaj per randoj.

113
00:05:45,000 --> 00:05:48,000
Do la radiko de la arbo estas nodo valoron kun la valoro 13,

114
00:05:48,000 --> 00:05:52,000
kiu havas 2 infanoj nodoj kun la valoroj 5 kaj 34.

115
00:05:52,000 --> 00:05:57,000
Al subárbol estas la arbo kiu estas formita nur rigardas subsekcio de la tuta arbo.

116
00:05:57,000 --> 00:06:03,000
>> Ekzemple, la maldekstra subarbo de la nodo 3 estas la arbo kreita de la nodoj 0, 1, kaj 2.

117
00:06:03,000 --> 00:06:06,000
Do, se ni reiru al la propraĵoj de duuma serĉo arbo,

118
00:06:06,000 --> 00:06:09,000
ni vidas ke ĉiu nodo en la arbo sekvas ĉiuj 3 propraĵoj, nome,

119
00:06:09,000 --> 00:06:15,000
la maldekstra subarbo nur enhavas valorojn kiuj estas malpli ol aŭ egala al la nodo valoron;

120
00:06:15,000 --> 00:06:16,000
Dekstre subárbol de ĉiuj nodoj

121
00:06:16,000 --> 00:06:19,000
nur enhavas valorojn kiuj estas pli granda ol aŭ egala al la nodo valoron, kaj

122
00:06:19,000 --> 00:06:25,000
ambaŭ maldekstra kaj dekstra subárboles de ĉiuj nodoj ankaŭ estas duuma serĉo arboj.

123
00:06:25,000 --> 00:06:28,000
Kvankam ĉi tiu arbo aspektas malsamaj, tio estas valida duuma serĉarbo

124
00:06:28,000 --> 00:06:30,000
por la sama aro de nombroj.

125
00:06:30,000 --> 00:06:32,000
Kiel Efektive, estas multaj eblaj manieroj kiuj vi povas krei

126
00:06:32,000 --> 00:06:35,000
valida duuma serĉarbo el tiuj numeroj.

127
00:06:35,000 --> 00:06:38,000
Nu, ni reiru al la unua ni kreis.

128
00:06:38,000 --> 00:06:40,000
Do kion ni povas fari kun tiuj arboj?

129
00:06:40,000 --> 00:06:44,000
Nu, ni povas tre simple trovi la minimuma kaj maksimuma valoro.

130
00:06:44,000 --> 00:06:46,000
La minimuma valoroj povas troviĝi per ĉiam tuj la maldekstra

131
00:06:46,000 --> 00:06:48,000
ĝis estas ne pli nodoj viziti.

132
00:06:48,000 --> 00:06:53,000
Male, por trovi la maksimuma oni simple nur iras malsupren al la rajto je ĉiu tempo.

133
00:06:54,000 --> 00:06:56,000
>> Finding ajna alia nombro kiu ne estas la minimumo aŭ la maksimuma

134
00:06:56,000 --> 00:06:58,000
estas tiel facila.

135
00:06:58,000 --> 00:07:00,000
Diru ni serĉas la numeron 89.

136
00:07:00,000 --> 00:07:03,000
Ni simple kontrolu la valoron de ĉiu nodo kaj iru sur la maldekstra aŭ dekstra,

137
00:07:03,000 --> 00:07:06,000
dependanta sur ĉu la nodo valoro estas malpli ol aŭ pli granda ol

138
00:07:06,000 --> 00:07:08,000
la ni serĉas.

139
00:07:08,000 --> 00:07:11,000
Do, ekde la radiko de 13, ni vidas ke 89 estas pli granda,

140
00:07:11,000 --> 00:07:13,000
kaj tiel ni iros al la rajto.

141
00:07:13,000 --> 00:07:16,000
Tiam ni vidu la nodo por 34, kaj ni denove iros al dekstre.

142
00:07:16,000 --> 00:07:20,000
89 estas ankoraŭ pli granda ol 55, do ni daŭre tuj dekstre.

143
00:07:20,000 --> 00:07:24,000
Ni tiam venu kun nodo kun la valoro de 144 kaj iru al la maldekstra.

144
00:07:24,000 --> 00:07:26,000
Jen kaj jen, 89 estas prava.

145
00:07:26,000 --> 00:07:31,000
>> Alia afero kiun ni povas fari estas presi ĉiuj nombroj per plenumante la inorder traversal.

146
00:07:31,000 --> 00:07:35,000
An inorder traversal signifas presi ĉio el la maldekstra subarbo

147
00:07:35,000 --> 00:07:37,000
sekvata de presi la nodo mem

148
00:07:37,000 --> 00:07:40,000
kaj tiam sekvis per presi ĉio el la dekstra subárbol.

149
00:07:40,000 --> 00:07:43,000
Ekzemple, ni prenu nian preferataj duuma serĉarbo

150
00:07:43,000 --> 00:07:46,000
kaj presi la nombroj en ordo ordo.

151
00:07:46,000 --> 00:07:49,000
Ni komencu ĉe la radiko de 13, sed antaŭ presado 13 ni devas presi

152
00:07:49,000 --> 00:07:51,000
ĉiu en la maldekstra subarbo.

153
00:07:51,000 --> 00:07:55,000
Do ni iru al 5. Ni ankoraŭ devas iri profunden malsupre en la arbo ĝis ni trovos la maldekstra plej nodo,

154
00:07:55,000 --> 00:07:57,000
kiu estas nulo.

155
00:07:57,000 --> 00:08:00,000
Post impreso nulo, ni reiru al la 1 kaj presi ke eksteren.

156
00:08:00,000 --> 00:08:03,000
Tiam ni iros al la dekstra subárbol, kiu estas 2, kaj presi ke eksteren.

157
00:08:03,000 --> 00:08:05,000
Nun ke ni faris kun tiu subárbol,

158
00:08:05,000 --> 00:08:07,000
ni povas reiri al la 3 kaj presi ĝin.

159
00:08:07,000 --> 00:08:11,000
Daŭrigante back up, ni presas la 5 kaj tiam la 8.

160
00:08:11,000 --> 00:08:13,000
Nun kiam ni finis la tutan lasis subárbol,

161
00:08:13,000 --> 00:08:17,000
ni povas presi la 13 kaj komenci labori sur la dekstra subárbol.

162
00:08:17,000 --> 00:08:21,000
Ni hop suben al 34, sed antaŭ presado 34 ni devas presi lian maldekstran subárbol.

163
00:08:21,000 --> 00:08:27,000
Do ni presi 21, tiam ni preni presi 34 kaj vizitu lian dekstran subárbol.

164
00:08:27,000 --> 00:08:31,000
Ekde 55 ne havas maldekstran subárbol, ni presas ĝin kaj daŭrigi liajn rajtojn subárbol.

165
00:08:31,000 --> 00:08:36,000
144 havas maldekstra subarbo, kaj tiel ni presi la 89, sekvita de la 144,

166
00:08:36,000 --> 00:08:39,000
kaj fine la dekstra plej nodo de 233.

167
00:08:39,000 --> 00:08:44,000
Tie vi havas ĝin; ĉiuj nombroj estas presita el en ordo de plej malalta al plej alta.

168
00:08:44,000 --> 00:08:47,000
>> Aldoni ion al la arbo estas relative indolora tiel.

169
00:08:47,000 --> 00:08:51,000
Ĉiuj ni devas fari estas certiĝi, ke ni sekvu 3 duuma serĉarbo propraĵoj

170
00:08:51,000 --> 00:08:53,000
kaj poste enmeti la valoro kie estas spaco.

171
00:08:53,000 --> 00:08:55,000
Supozu ke ni volas enmeti la valoron de 7.

172
00:08:55,000 --> 00:08:58,000
Ekde 7 estas malpli ol 13, ni iru al la maldekstra.

173
00:08:58,000 --> 00:09:01,000
Sed estas pli granda ol 5, do ni trairi al dekstre.

174
00:09:01,000 --> 00:09:04,000
Ekde ĝi estas malpli ol 8 kaj 8 estas nodo folio, ni aldonos 7 al la maldekstra infano de 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Ni aldonis kelkajn al nia duuma serĉarbo.

176
00:09:09,000 --> 00:09:12,000
>> Se ni povas aldoni aĵojn, ni pli bone povos forviŝi tion ankaŭ.

177
00:09:12,000 --> 00:09:14,000
Bedaŭrinde por ni, viŝante estas iomete pli komplika -

178
00:09:14,000 --> 00:09:16,000
ne tre, sed nur iomete.

179
00:09:16,000 --> 00:09:18,000
Estas 3 diversaj scenaroj, ke ni devas konsideri

180
00:09:18,000 --> 00:09:21,000
kiam viŝante elementojn de duumaj arboj de serĉo.

181
00:09:21,000 --> 00:09:24,000
Unue, la plej facila afero estas, ke la ero estas nodo folio.

182
00:09:24,000 --> 00:09:27,000
En ĉi tiu kazo, ni simple forigi ĝin kaj daŭrigi kun nia afero.

183
00:09:27,000 --> 00:09:30,000
Ke ni volas forviŝi la 7 por ke ni ĵus aldonis.

184
00:09:30,000 --> 00:09:34,000
Nu, ni simple trovi ĝin, eltiri ĝin, kaj tio estas ĝi.

185
00:09:35,000 --> 00:09:37,000
La sekva kazo estas se la nodo havas nur 1 infano.

186
00:09:37,000 --> 00:09:40,000
Ĉi tie ni povas forigi la nodon, sed ni devas unue certigi

187
00:09:40,000 --> 00:09:42,000
por kunligi la subárbol kiu nun forlasis parentless

188
00:09:42,000 --> 00:09:44,000
al la patro de la nodo ni simple forigita.

189
00:09:44,000 --> 00:09:47,000
Ke ni volas forviŝi 3 de niaj arbo.

190
00:09:47,000 --> 00:09:50,000
Ni prenu la knabeton elemento de tiu nodo kaj aligu ĝin al la patro de la nodo.

191
00:09:50,000 --> 00:09:54,000
En ĉi tiu kazo, ni nun alfiksanta la 1 al la 5.

192
00:09:54,000 --> 00:09:57,000
Tiu funkcias sen problemo ĉar ni scias, laŭ la duuma serĉarbo proprieto,

193
00:09:57,000 --> 00:10:01,000
ke ĉiu en la maldekstra subarbo de 3 estis malpli ol 5.

194
00:10:01,000 --> 00:10:05,000
Nun ke 3 estas subárbol atentas, ni povas forigi ĝin.

195
00:10:05,000 --> 00:10:08,000
La tria kaj lasta kazo estas la plej kompleksa.

196
00:10:08,000 --> 00:10:11,000
Ĉi tiu estas la kazo kiam la nodo ni volas forigi havas 2 infanojn.

197
00:10:11,000 --> 00:10:15,000
Por fari tion, ni unue devas trovi la nodo kiu havas la sekva plej granda valoro,

198
00:10:15,000 --> 00:10:18,000
interŝanĝi la du, kaj poste forigi la nodon en demando.

199
00:10:18,000 --> 00:10:22,000
Rimarki la nodo kiu havas la sekva plej granda valoro ne povas havi 2 idoj mem

200
00:10:22,000 --> 00:10:26,000
ekde ĝia maldekstra infano estus bona kandidato por la venonta pli granda.

201
00:10:26,000 --> 00:10:30,000
Sekve, viŝante nodo kun 2 infanoj kvantoj por interŝanĝi de 2 verticoj,

202
00:10:30,000 --> 00:10:33,000
kaj poste forigi estas manipulita per 1 el la 2 menciita reguloj.

203
00:10:33,000 --> 00:10:37,000
Ekzemple, ni diras, ke ni volas forigi la radika vertico, 13.

204
00:10:37,000 --> 00:10:39,000
La unua aĵo kiun ni faras estas ni trovas la venonta plej granda valoro en la arbo

205
00:10:39,000 --> 00:10:41,000
kiu, en ĉi tiu kazo, estas 21.

206
00:10:41,000 --> 00:10:46,000
Ni tiam interŝanĝi la 2 nodoj, farante 13 folio kaj 21 la centra grupo nodo.

207
00:10:46,000 --> 00:10:49,000
Nun ni povas simple forigi 13.

208
00:10:50,000 --> 00:10:53,000
>> Kiel aludis al pli frua, estas multaj eblaj manieroj fari validan duuma serĉarbo.

209
00:10:53,000 --> 00:10:56,000
Bedaŭrinde por ni, iuj estas pli malbona ol aliaj.

210
00:10:56,000 --> 00:10:59,000
Ekzemple, kio okazas kiam ni konstruos duuma serĉarbo

211
00:10:59,000 --> 00:11:01,000
de ordo listo de nombroj?

212
00:11:01,000 --> 00:11:04,000
Ĉiuj nombroj estas nur aldonis al la rajto je ĉiu paŝo.

213
00:11:04,000 --> 00:11:06,000
Kiam ni volas serĉi numeron,

214
00:11:06,000 --> 00:11:08,000
ni ne havas elekton, sed nur rigardi la rajton je ĉiu paŝo.

215
00:11:08,000 --> 00:11:11,000
Ĉi tiu ne estas pli bona ol lineara serĉo por nenio.

216
00:11:11,000 --> 00:11:13,000
Kvankam ni ne kovru ilin ĉi tie, estas aliaj, pli kompleksa,

217
00:11:13,000 --> 00:11:16,000
datumstrukturoj ke certigi ke ĉi tio ne okazos.

218
00:11:16,000 --> 00:11:18,000
Tamen, unu simpla afero kiu povas esti farita por eviti ĉi estas

219
00:11:18,000 --> 00:11:21,000
justaj hazarde barajar la enigo valoroj.

220
00:11:21,000 --> 00:11:26,000
Estas tre malverŝajne ke per hazarda hazardo barajan listo de nombroj estas ordo.

221
00:11:26,000 --> 00:11:29,000
Se ĉi tiu estis la kazo, kazinoj ne resti en negoco por longe.

222
00:11:29,000 --> 00:11:31,000
>> Tie vi havas ĝin.

223
00:11:31,000 --> 00:11:34,000
Vi nun scias pri duuma serĉo kaj duuma serĉo arboj.

224
00:11:34,000 --> 00:11:36,000
Mi estas Patrick Schmid, kaj ĉi tiu estas CS50.

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

226
00:11:38,000 --> 00:11:43,000
Unu evidenta maniero estus skani la listo de ... [pepi]

227
00:11:43,000 --> 00:11:46,000
... La nombro de artikoloj ... yep

228
00:11:46,000 --> 00:11:50,000
[Ridas]

229
00:11:50,000 --> 00:11:55,000
... Afiŝi nodo de 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Tio estis -