1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary Search]

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

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

4
00:00:07,000 --> 00:00:09,000
>> Če sem ti dal seznam imen Disney znakov v abecednem vrstnem redu

5
00:00:09,000 --> 00:00:11,000
in vas prosili, da bi našli Miki Miška,

6
00:00:11,000 --> 00:00:13,000
Kako bi šel o tem?

7
00:00:13,000 --> 00:00:15,000
Eden od očitnih načinov bi bil za skeniranje seznam od začetka

8
00:00:15,000 --> 00:00:18,000
in preverite vsako ime, da vidim, če je Mickey.

9
00:00:18,000 --> 00:00:22,000
Ampak kot ste prebrali Aladdin, Alice, Ariel, in tako naprej,

10
00:00:22,000 --> 00:00:25,000
boste hitro ugotovili, da se začne na sprednji strani seznama ni bila dobra ideja.

11
00:00:25,000 --> 00:00:29,000
Ok, morda bi morali začeti delati nazaj od konca seznama.

12
00:00:29,000 --> 00:00:33,000
Zdaj ste prebrali Tarzan, Stitch, Sneguljčica, in tako naprej.

13
00:00:33,000 --> 00:00:36,000
Kljub temu pa to ne zdi najboljši način, da gredo o tem.

14
00:00:36,000 --> 00:00:38,000
>> No, še en način, da bi lahko šel o tem je, da poskusite zožiti

15
00:00:38,000 --> 00:00:41,000
seznam imen, ki jih boste morali pogledati.

16
00:00:41,000 --> 00:00:43,000
Ker veš, da so v abecednem vrstnem redu,

17
00:00:43,000 --> 00:00:45,000
si lahko samo pogled na imena v sredini seznama

18
00:00:45,000 --> 00:00:49,000
in preverite, če Mickey Mouse je pred ali po tem imenom.

19
00:00:49,000 --> 00:00:51,000
Če pogledamo zadnje ime v drugem stolpcu

20
00:00:51,000 --> 00:00:54,000
boš zavedaš, da je M za Mickey prihaja po J za Jasmine,

21
00:00:54,000 --> 00:00:57,000
Tako bi preprosto prezreti prvo polovico seznama.

22
00:00:57,000 --> 00:00:59,000
Potem bi verjetno pogled na vrhu zadnjega stolpca

23
00:00:59,000 --> 00:01:02,000
in glej, da se začne z Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey je pred Rapunzel, izgleda, lahko odmislimo zadnji stolpec, kot dobro.

25
00:01:06,000 --> 00:01:08,000
Nadaljevanje strategija iskanja, boste hitro videli, da Mickey

26
00:01:08,000 --> 00:01:11,000
je v prvi polovici preostalega seznama imen

27
00:01:11,000 --> 00:01:14,000
in na koncu je bil Mickey skriva med Merlin in Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Kaj si naredil, je bilo v bistvu binarno iskanje.

29
00:01:17,000 --> 00:01:22,000
Ker je to že samo ime pove, da opravlja svojo strategijo iskanjem v binarni zadeve.

30
00:01:22,000 --> 00:01:24,000
Kaj to pomeni?

31
00:01:24,000 --> 00:01:27,000
No, glede na seznam razvrščenih postavk, binarno iskanje algoritem naredi binarno odločitev -

32
00:01:27,000 --> 00:01:33,000
levo ali desno, je večja ali manjša od pred ali po abecedi - na vsaki točki.

33
00:01:33,000 --> 00:01:35,000
Zdaj, ko imamo ime, ki gre skupaj s to iskalni algoritem,

34
00:01:35,000 --> 00:01:38,000
Oglejmo si še en primer, tokrat s seznamom razvrščenih številk.

35
00:01:38,000 --> 00:01:43,000
Povejte iščemo številko 144 v tem seznamu razvrščena številk.

36
00:01:43,000 --> 00:01:46,000
Tako kot prej, smo našli številko, ki je na sredini -

37
00:01:46,000 --> 00:01:50,000
, ki je v tem primeru 13 - in videli, če je večja od 144 ali manj kot 13 let.

38
00:01:50,000 --> 00:01:54,000
Ker je očitno večji od 13, lahko odmislimo vse, kar je 13 ali manj

39
00:01:54,000 --> 00:01:57,000
in osredotočiti samo na preostalo polovico.

40
00:01:57,000 --> 00:01:59,000
Ker imamo zdaj celo število kosov levo,

41
00:01:59,000 --> 00:02:01,000
smo preprosto izberete številko, ki je blizu sredini.

42
00:02:01,000 --> 00:02:03,000
V tem primeru bomo izbrali 55.

43
00:02:03,000 --> 00:02:06,000
Lahko bi prav tako lahko izbrali 89.

44
00:02:06,000 --> 00:02:11,000
Ok. Again, 144 je več kot 55, tako da gremo na desno.

45
00:02:11,000 --> 00:02:14,000
K sreči za nas, naslednji srednji številka 144,

46
00:02:14,000 --> 00:02:16,000
tisti, ki ga iščemo.

47
00:02:16,000 --> 00:02:21,000
Torej, da bi našli 144 z binarno iskanje, bomo lahko našli v samo 3 korakih.

48
00:02:21,000 --> 00:02:24,000
Če bi smo uporabili linearno iskanje tukaj, bi nas sprejela 12 ukrepov.

49
00:02:24,000 --> 00:02:28,000
Kot Dejstvo je, saj je to način iskanja prepolovi število postavk

50
00:02:28,000 --> 00:02:31,000
ima pogled na na vsakem koraku, bo našel predmet, se išče

51
00:02:31,000 --> 00:02:35,000
v približno dnevnik števila elementov na seznamu.

52
00:02:35,000 --> 00:02:37,000
Zdaj, ko smo videli 2 primere, pa si oglejte

53
00:02:37,000 --> 00:02:41,000
nekateri psevdokod za rekurzivna funkcija, ki izvaja binarno iskanje.

54
00:02:41,000 --> 00:02:44,000
Začnite na vrhu, smo videli, da smo morali najti funkcijo, ki traja 4 argumente:

55
00:02:44,000 --> 00:02:47,000
ključ, matrika, min in max.

56
00:02:47,000 --> 00:02:51,000
Ključno je število, ki ga iščemo, tako 144 v prejšnjem primeru.

57
00:02:51,000 --> 00:02:54,000
Array je seznam številk, ki jih iščejo.

58
00:02:54,000 --> 00:02:57,000
Min in max so indeksi najnižje in najvišje položaje

59
00:02:57,000 --> 00:02:59,000
da smo trenutno iščejo.

60
00:02:59,000 --> 00:03:03,000
Torej, ko smo začeli, bo najmanj enaka nič in max bo največji indeks matrike.

61
00:03:03,000 --> 00:03:07,000
Kot smo zožite iskanje navzdol, bomo posodobiti min in max

62
00:03:07,000 --> 00:03:10,000
da je samo območje, ki se še vedno išče noter

63
00:03:10,000 --> 00:03:12,000
>> Naj preskočite na zanimiv del prve.

64
00:03:12,000 --> 00:03:14,000
Prva stvar, ki mi je najti srednjo vrednost,

65
00:03:14,000 --> 00:03:19,000
indeks, ki se nahaja na pol poti med min in max polja, ki se še vedno razmišlja.

66
00:03:19,000 --> 00:03:22,000
Potem pogledamo vrednosti matrike na tej lokaciji središčem

67
00:03:22,000 --> 00:03:25,000
in videli, če je število, ki ga iščemo, je manjša od te tipke.

68
00:03:25,000 --> 00:03:27,000
Če je število na tem položaju je manj,

69
00:03:27,000 --> 00:03:31,000
potem to pomeni, da je ključ večji od vseh številk levo od tega položaja.

70
00:03:31,000 --> 00:03:33,000
Torej lahko rečemo, binarno iskalno funkcijo ponovno

71
00:03:33,000 --> 00:03:36,000
vendar tokrat posodabljanje min in max parametre, da se glasi le polovico

72
00:03:36,000 --> 00:03:40,000
, ki je večja od ali enaka vrednosti sva pogledala.

73
00:03:40,000 --> 00:03:44,000
Po drugi strani pa, če je ključ manjše od števila v sedanji sredini matrike,

74
00:03:44,000 --> 00:03:47,000
želimo iti v levo in ignorirati vse številke, ki so večje.

75
00:03:47,000 --> 00:03:52,000
Spet pravimo binarno iskanje vendar tokrat z razponom min in max Popravljeno

76
00:03:52,000 --> 00:03:54,000
vključiti samo spodnjo polovico.

77
00:03:54,000 --> 00:03:57,000
Če je vrednost v trenutni sredini v polju ni niti

78
00:03:57,000 --> 00:04:01,000
večja kot niti manjši od ključa, potem mora biti enak ključ.

79
00:04:01,000 --> 00:04:05,000
Tako lahko enostavno vrne trenutno kazalo srednjo vrednost, in smo končali.

80
00:04:05,000 --> 00:04:09,000
Končno, to preverjanje tu za primer, da se je število

81
00:04:09,000 --> 00:04:11,000
dejansko ni v niz številk iščemo.

82
00:04:11,000 --> 00:04:14,000
Če se najvišji indeks območju, ki ga iščemo

83
00:04:14,000 --> 00:04:17,000
je vedno manj od minimuma, kar pomeni, da smo šli predaleč.

84
00:04:17,000 --> 00:04:20,000
Ker se število ni v vnosno polje, vrnemo -1

85
00:04:20,000 --> 00:04:24,000
, ki označuje, da nič ni bilo videti.

86
00:04:24,000 --> 00:04:26,000
>> Morda ste opazili, da se za ta algoritem za delo,

87
00:04:26,000 --> 00:04:28,000
seznam številk, je treba razvrstiti.

88
00:04:28,000 --> 00:04:31,000
Z drugimi besedami, smo lahko našli le 144 dvojiškem iskanje

89
00:04:31,000 --> 00:04:34,000
če so vse številke naročil od najnižje do najvišje.

90
00:04:34,000 --> 00:04:38,000
Če ne bi bilo tako, ne bi mogli izključiti polovico števil na vsakem koraku.

91
00:04:38,000 --> 00:04:40,000
Torej imamo 2 možnosti.

92
00:04:40,000 --> 00:04:43,000
Ali lahko vzamemo neurejen seznam in ga rešiti pred dvojiškem iskanje

93
00:04:43,000 --> 00:04:48,000
ali pa bomo poskrbeli, da se seznam številk, razvrščenih kot smo Dodajanje številk na njej.

94
00:04:48,000 --> 00:04:50,000
Torej, namesto razvrščanja šele takrat, ko bomo morali iskati,

95
00:04:50,000 --> 00:04:53,000
zakaj ne hranijo seznam razporejen po vseh časov?

96
00:04:53,000 --> 00:04:57,000
>> Eden od načinov, da seznam številk, razvrščenih hkrati pa omogoča

97
00:04:57,000 --> 00:04:59,000
1 dodati ali premakniti številke s tega seznama

98
00:04:59,000 --> 00:05:02,000
je z uporabo nekaj, kar ti binarno iskalno drevo.

99
00:05:02,000 --> 00:05:05,000
Dvojiško iskalno drevo je podatkovna struktura, ki ima 3 lastnosti.

100
00:05:05,000 --> 00:05:09,000
Prvič, levo poddrevo vsakega vozlišča vsebuje samo vrednosti, ki so manjše od

101
00:05:09,000 --> 00:05:11,000
ali enaka vrednosti vozlišča.

102
00:05:11,000 --> 00:05:15,000
Drugič, desno poddrevo za vozlišče vsebuje le vrednosti, ki so večje od

103
00:05:15,000 --> 00:05:17,000
ali enaka vrednosti vozlišča.

104
00:05:17,000 --> 00:05:20,000
In končno, tako levi in ​​desni subtrees vseh vozlišč

105
00:05:20,000 --> 00:05:23,000
tudi dvojiška iskalna drevesa.

106
00:05:23,000 --> 00:05:26,000
Oglejmo si primer z enakimi številkami smo uporabili prej.

107
00:05:26,000 --> 00:05:30,000
Za tiste, ki še nikoli niso videli računalništvo drevo pred

108
00:05:30,000 --> 00:05:34,000
Naj začnem z vam pove, da računalništvo drevo raste navzdol.

109
00:05:34,000 --> 00:05:36,000
Ja, za razliko od dreves ste vajeni,

110
00:05:36,000 --> 00:05:38,000
koren drevesa računalništva na vrhu,

111
00:05:38,000 --> 00:05:41,000
in listi so na dnu.

112
00:05:41,000 --> 00:05:45,000
Vsak malo polje se imenuje vozlišče in vozlišča so med seboj povezani z robovi.

113
00:05:45,000 --> 00:05:48,000
Torej je koren tega drevesa je vozlišče vrednost z vrednostjo 13,

114
00:05:48,000 --> 00:05:52,000
ki ima 2 otroka vozlišč z vrednostmi 5 in 34.

115
00:05:52,000 --> 00:05:57,000
Poddrevo je drevo, ki je nastala samo jih je videti na pododdelku celotnega drevesa.

116
00:05:57,000 --> 00:06:03,000
>> Na primer, levo poddrevo od vozlišča 3 je drevo, ki ga ustvarjajo vozlišča 0, 1, 2 in.

117
00:06:03,000 --> 00:06:06,000
Torej, če se vrnemo na lastnosti drevo binarno iskanje,

118
00:06:06,000 --> 00:06:09,000
vidimo, da je vsako vozlišče v drevesu, skladna z vsemi lastnostmi, in sicer 3,

119
00:06:09,000 --> 00:06:15,000
levo poddrevo vsebuje samo vrednosti, ki so manjše ali enake vrednosti vozlišča;

120
00:06:15,000 --> 00:06:16,000
pravica poddrevo vseh vozlišč

121
00:06:16,000 --> 00:06:19,000
vsebuje samo vrednosti, ki so večje ali enake vrednosti vozlišča in

122
00:06:19,000 --> 00:06:25,000
tako levi in ​​desni subtrees vseh vozlišč so tudi iskalna drevesa binarni.

123
00:06:25,000 --> 00:06:28,000
Čeprav je to drevo je drugačno, je to veljavno binarno iskalno drevo

124
00:06:28,000 --> 00:06:30,000
Za enak nabor številk.

125
00:06:30,000 --> 00:06:32,000
Kot Dejstvo je, da obstaja več možnih načinov, ki jih lahko ustvarite

126
00:06:32,000 --> 00:06:35,000
veljavno binarno iskalno drevo iz teh številk.

127
00:06:35,000 --> 00:06:38,000
No, gremo nazaj na prvi tisti, ki smo jo ustvarili.

128
00:06:38,000 --> 00:06:40,000
Torej, kaj lahko naredimo s temi drevesi?

129
00:06:40,000 --> 00:06:44,000
No, bomo lahko zelo enostavno najti minimalne in maksimalne vrednosti.

130
00:06:44,000 --> 00:06:46,000
Najnižje vrednosti, je na voljo vedno dogaja na levi

131
00:06:46,000 --> 00:06:48,000
dokler ni več vozlišč za obisk.

132
00:06:48,000 --> 00:06:53,000
Po drugi strani pa, da bi našli največjo 1 preprosto samo pade na desno na vsakem trenutku.

133
00:06:54,000 --> 00:06:56,000
>> Iskanje katero koli drugo vrsto, ki ni najnižja ali najvišja

134
00:06:56,000 --> 00:06:58,000
je prav tako enostavno.

135
00:06:58,000 --> 00:07:00,000
Povejte iščemo številko 89.

136
00:07:00,000 --> 00:07:03,000
Mi enostavno preveri vrednost vsakega vozlišča in pojdite na levo ali desno,

137
00:07:03,000 --> 00:07:06,000
glede na to, ali je v vozlišču je vrednost manjša ali večja od

138
00:07:06,000 --> 00:07:08,000
tisti, ki ga iščemo.

139
00:07:08,000 --> 00:07:11,000
Torej, z začetkom ob korenu 13, vidimo, da je 89 več,

140
00:07:11,000 --> 00:07:13,000
in tako gremo v desno.

141
00:07:13,000 --> 00:07:16,000
Potem bomo videli vozlišča za 34, in spet gremo na desno.

142
00:07:16,000 --> 00:07:20,000
89 je še vedno več kot 55 let, zato smo nadaljevali bomo na desni strani.

143
00:07:20,000 --> 00:07:24,000
Nato smo prišli do vozlišča z vrednostjo 144 in pojdite na levo.

144
00:07:24,000 --> 00:07:26,000
Glej, glej, 89 je tam.

145
00:07:26,000 --> 00:07:31,000
>> Druga stvar, kar lahko naredimo, je izpisal vse številke z izvedbo mora biti zato, prečkanje.

146
00:07:31,000 --> 00:07:35,000
Mora biti zato, prečkanje pomeni, da natisnete vse, kar je v levo poddrevo

147
00:07:35,000 --> 00:07:37,000
sledi tiskanje vozlišča se

148
00:07:37,000 --> 00:07:40,000
in potem sledi tiskanje, vse v pravi poddrevo.

149
00:07:40,000 --> 00:07:43,000
Na primer, vzemimo naše najljubše drevo binarno iskanje

150
00:07:43,000 --> 00:07:46,000
in tiskanje številk v vrstnem redu razvrščeni.

151
00:07:46,000 --> 00:07:49,000
Začnemo pri korenu 13, vendar pred tiskanjem 13 moramo natisniti

152
00:07:49,000 --> 00:07:51,000
vse v levo poddrevo.

153
00:07:51,000 --> 00:07:55,000
Torej gremo v 5. Še vedno moramo iti globlje navzdol na drevesu, dokler ne najdemo na levi najbolj vozlišče,

154
00:07:55,000 --> 00:07:57,000
ki je enaka nič.

155
00:07:57,000 --> 00:08:00,000
Po tiskanju nič, gremo nazaj do 1 in natisniti to.

156
00:08:00,000 --> 00:08:03,000
Potem gremo v desno poddrevo, kar je 2 in natisniti to.

157
00:08:03,000 --> 00:08:05,000
Zdaj, ko smo opravili s tem poddrevo,

158
00:08:05,000 --> 00:08:07,000
bomo lahko vrnili do 3 in jo natisnite.

159
00:08:07,000 --> 00:08:11,000
Nadaljevanje nazaj, smo natisnili 5 in nato 8.

160
00:08:11,000 --> 00:08:13,000
Zdaj, ko smo zaključili celotno levo poddrevo,

161
00:08:13,000 --> 00:08:17,000
lahko natisnete 13 in začeli delati na desno poddrevo.

162
00:08:17,000 --> 00:08:21,000
Mi hop do 34, vendar pred tiskanjem 34 moramo natisniti svojo levo poddrevo.

163
00:08:21,000 --> 00:08:27,000
Tako smo natisniti 21, nato pa pridemo do natisniti 34 in obiščite njegovo desno poddrevo.

164
00:08:27,000 --> 00:08:31,000
Od 55 nima levo poddrevo, jo natisnite in nadaljujemo z njegovo desno poddrevo.

165
00:08:31,000 --> 00:08:36,000
144 ima levo poddrevo, zato smo izpisal 89, čemur sledi 144,

166
00:08:36,000 --> 00:08:39,000
in na koncu desno najbolj vozlišče 233.

167
00:08:39,000 --> 00:08:44,000
Tam ga imate, vse številke so natisnjene v vrstnem redu od najnižje do najvišje.

168
00:08:44,000 --> 00:08:47,000
>> Dodajanje nekaj drevesa je relativno neboleč, kot dobro.

169
00:08:47,000 --> 00:08:51,000
Vse kar moramo storiti je, da poskrbite, da sledimo 3 dvojiške lastnosti drevesnih iskanja

170
00:08:51,000 --> 00:08:53,000
in nato vstavite vrednosti, kjer je prostor.

171
00:08:53,000 --> 00:08:55,000
Recimo, želite vstaviti vrednost 7.

172
00:08:55,000 --> 00:08:58,000
Ker je 7 manj kot 13, gremo v levo.

173
00:08:58,000 --> 00:09:01,000
Ampak to je več kot 5, tako da prečkajo desno.

174
00:09:01,000 --> 00:09:04,000
Ker je manj kot 8 in 8 je vozlišče list, dodamo 7 do 8 levi otroka.

175
00:09:04,000 --> 00:09:09,000
Voila! Dodali smo nekaj za naše drevo binarno iskanje.

176
00:09:09,000 --> 00:09:12,000
>> Če bomo dodali stvari, bolje boste mogli izbrisati stvari, kot dobro.

177
00:09:12,000 --> 00:09:14,000
Na žalost za nas, brisanje je malce bolj zapleteno -

178
00:09:14,000 --> 00:09:16,000
Ni veliko, ampak samo malo.

179
00:09:16,000 --> 00:09:18,000
Obstajajo 3 različne scenarije, ki jih moramo upoštevati

180
00:09:18,000 --> 00:09:21,000
Pri brisanju elementov iz binarnih dreves iskanja.

181
00:09:21,000 --> 00:09:24,000
Prvič, najlažji primer je, da je element listov vozlišča.

182
00:09:24,000 --> 00:09:27,000
V tem primeru smo preprosto izbrisati in iti naprej s naše poslovanje.

183
00:09:27,000 --> 00:09:30,000
Povejte nam želite izbrisati 7, ki smo jo pravkar dodali.

184
00:09:30,000 --> 00:09:34,000
No, mi preprosto zdi, da ga odstranite, in to je to.

185
00:09:35,000 --> 00:09:37,000
Naslednji primer je, če je vozlišče ima samo 1 otroka.

186
00:09:37,000 --> 00:09:40,000
Tu lahko izbrišete vozlišče, vendar moramo najprej zagotoviti,

187
00:09:40,000 --> 00:09:42,000
povezati poddrevo, ki je zdaj ostalo parentless

188
00:09:42,000 --> 00:09:44,000
na matično vozlišča sva se črta.

189
00:09:44,000 --> 00:09:47,000
Povejte nam želite izbrisati 3 od našega drevesa.

190
00:09:47,000 --> 00:09:50,000
Mi lahko otrok element tega vozla in jo pritrdite na matično vozlišča.

191
00:09:50,000 --> 00:09:54,000
V tem primeru smo zdaj pritrditev 1 do 5.

192
00:09:54,000 --> 00:09:57,000
Ta deluje brez problema, saj vemo, v skladu z binarno iskalno drevo premoženja,

193
00:09:57,000 --> 00:10:01,000
da je vse v levo poddrevo od 3 manj kot 5.

194
00:10:01,000 --> 00:10:05,000
Zdaj, ko se je poddrevo 3 poskrbljeno, lahko izbrišete.

195
00:10:05,000 --> 00:10:08,000
Tretji in zadnji primer je najbolj zapleten.

196
00:10:08,000 --> 00:10:11,000
To je v primeru, ko je vozlišče želimo izbrisati ima 2 otroka.

197
00:10:11,000 --> 00:10:15,000
Da bi to storili, moramo najprej najti vozlišče, ki ima naslednjo največjo vrednost,

198
00:10:15,000 --> 00:10:18,000
swap 2, in nato izbrišite vozlišče vprašanje.

199
00:10:18,000 --> 00:10:22,000
Obvestilo vozlišče, ki ima naslednjo največjo vrednost, ne more imeti 2 otroka sama

200
00:10:22,000 --> 00:10:26,000
saj bi njena leva otrok je bolje kandidat za naslednjo, večjo.

201
00:10:26,000 --> 00:10:30,000
Zato brisanje vozlišče z 2 otrokoma znaša menjava za 2 vozlišč,

202
00:10:30,000 --> 00:10:33,000
, nato pa se črta ravna 1 od 2 zgoraj navedenimi pravili.

203
00:10:33,000 --> 00:10:37,000
Na primer, recimo, da želimo izbrisati root vozlišča, 13.

204
00:10:37,000 --> 00:10:39,000
Prva stvar, ki mi je, da smo našli naslednje največjo vrednost v drevesu

205
00:10:39,000 --> 00:10:41,000
, ki v tem primeru je 21.

206
00:10:41,000 --> 00:10:46,000
Nato smo preklopili 2 vozlišč, kar 13 listov in 21 centralna skupina vozlišča.

207
00:10:46,000 --> 00:10:49,000
Sedaj lahko preprosto izbrisati 13.

208
00:10:50,000 --> 00:10:53,000
>> Kot namiguje že prej, obstaja več možnih načinov, da bi veljavno binarno drevo iskanje.

209
00:10:53,000 --> 00:10:56,000
Na žalost za nas, nekateri so slabši od drugih.

210
00:10:56,000 --> 00:10:59,000
Na primer, kaj se zgodi, ko gradimo binarno iskalno drevo

211
00:10:59,000 --> 00:11:01,000
izločen iz seznama številk?

212
00:11:01,000 --> 00:11:04,000
Vse številke so pravkar dodali na desno na vsakem koraku.

213
00:11:04,000 --> 00:11:06,000
Ko smo želeli poiskati nekaj,

214
00:11:06,000 --> 00:11:08,000
nimamo druge izbire, ampak le, da pogled na desno na vsakem koraku.

215
00:11:08,000 --> 00:11:11,000
To ni bolje kot linearni iskanje na vse.

216
00:11:11,000 --> 00:11:13,000
Čeprav ne bomo jih pokrijemo tu obstajajo druge, bolj zapletene,

217
00:11:13,000 --> 00:11:16,000
podatkovne strukture, da se prepričajte, da se to ne zgodi.

218
00:11:16,000 --> 00:11:18,000
Vendar pa je ena preprosta stvar, ki jo lahko storimo, da bi se temu izognili, je

219
00:11:18,000 --> 00:11:21,000
na samo naključno shuffle vhodnih vrednosti.

220
00:11:21,000 --> 00:11:26,000
To je zelo malo verjetno, da jih Naključje je razvrščen premešan seznam številk.

221
00:11:26,000 --> 00:11:29,000
Če bi bilo to res, igralnice, ne bi ostala v poslu dolgo.

222
00:11:29,000 --> 00:11:31,000
>> Tam ga imate.

223
00:11:31,000 --> 00:11:34,000
Zdaj vem binarno iskanje in iskalna drevesa binarnih.

224
00:11:34,000 --> 00:11:36,000
Jaz sem Patrick Schmid, in to je CS50.

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

226
00:11:38,000 --> 00:11:43,000
Eden od očiten način bi bil, da skeniranje seznam od ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Število točk ... ja

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

229
00:11:50,000 --> 00:11:55,000
Objavite ... vozlišča 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Bravo! To je bilo -