1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binarni Traži]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Sveučilište Harvard]

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

4
00:00:07,000 --> 00:00:09,000
>> Ako sam ti dao popis Disney karaktera imena po abecednom redu

5
00:00:09,000 --> 00:00:11,000
i vas traži da pronađete Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
kako će vam ići oko radiš?

7
00:00:13,000 --> 00:00:15,000
Jedan očigledan način bi se skenirati popis od početka

8
00:00:15,000 --> 00:00:18,000
i provjeriti svaki naziv za vidjeti ako je Mickey.

9
00:00:18,000 --> 00:00:22,000
Ali, kao što ste pročitali Aladdin, Alice, Ariel, i tako dalje,

10
00:00:22,000 --> 00:00:25,000
brzo ćete shvatiti da s početkom u prednjem dijelu popisa nije bio dobra ideja.

11
00:00:25,000 --> 00:00:29,000
Dobro, možda bi trebao početi raditi unatrag od kraja popisa.

12
00:00:29,000 --> 00:00:33,000
Sada ste pročitali Tarzan, Stitch, Snjeguljica, i tako dalje.

13
00:00:33,000 --> 00:00:36,000
Ipak, to ne čini kao najbolji način da ide o tome.

14
00:00:36,000 --> 00:00:38,000
>> Pa, još jedan način da bi mogao ići o događaj ovaj je pokušati suziti

15
00:00:38,000 --> 00:00:41,000
popis imena koje morate pogledati.

16
00:00:41,000 --> 00:00:43,000
Budući da znate da su abecednim redom,

17
00:00:43,000 --> 00:00:45,000
mogli bi samo pogledate imena u sredini popisa

18
00:00:45,000 --> 00:00:49,000
i provjerite je li Mickey Mouse je prije ili poslije tog imena.

19
00:00:49,000 --> 00:00:51,000
Gledajući prezimena u drugom stupcu

20
00:00:51,000 --> 00:00:54,000
želite shvatiti da M za Mickey dolazi nakon J za Jasmine,

21
00:00:54,000 --> 00:00:57,000
tako da jednostavno bih ignorirati prvu polovicu popisa.

22
00:00:57,000 --> 00:00:59,000
Onda ste vjerojatno bih pogledati na vrhu posljednjeg stupca

23
00:00:59,000 --> 00:01:02,000
i vidjeti da je to počinje s Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey dolazi prije Rapunzel, izgleda možemo zanemariti posljednji stupac kao dobro.

25
00:01:06,000 --> 00:01:08,000
Nastavljajući pretraživanje strategije, brzo ćete vidjeti da je Mickey

26
00:01:08,000 --> 00:01:11,000
je u prvoj polovici preostalog popis imena

27
00:01:11,000 --> 00:01:14,000
i napokon pronaći Mickey skriva između Merlina i Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Što ste upravo učinio je u osnovi binarni pretraživanje.

29
00:01:17,000 --> 00:01:22,000
Kao što to i ime kaže, obavlja svoju strategiju u potrazi u binarnom materije.

30
00:01:22,000 --> 00:01:24,000
Što to znači?

31
00:01:24,000 --> 00:01:27,000
Pa, s obzirom na popis razvrstanih predmeta, algoritam binarno pretraživanje čini binarnu odluku -

32
00:01:27,000 --> 00:01:33,000
lijevo ili desno, veći ili manji od, po abecednom redu prije ili poslije - u svakoj točki.

33
00:01:33,000 --> 00:01:35,000
Sada kada imamo ime koje ide uz ovaj pretraživanje algoritam,

34
00:01:35,000 --> 00:01:38,000
Pogledajmo još jedan primjer, ali ovaj put s popisom sortirani brojeva.

35
00:01:38,000 --> 00:01:43,000
Recimo da su u potrazi za brojem 144 u ovom popisu razvrstanih brojeva.

36
00:01:43,000 --> 00:01:46,000
Baš kao i prije, naći ćemo broj koji je u sredini -

37
00:01:46,000 --> 00:01:50,000
koja je u ovom slučaju je 13 - i vidjeti ako je veća od 144 ili manje od 13 godina.

38
00:01:50,000 --> 00:01:54,000
Budući da je očito veći od 13, što možemo ignorirati sve što je 13 ili manje

39
00:01:54,000 --> 00:01:57,000
i samo se koncentrirati na preostale polovine.

40
00:01:57,000 --> 00:01:59,000
Budući da sada imamo čak i broj predmeta lijevo,

41
00:01:59,000 --> 00:02:01,000
mi jednostavno izabrati broj koji je blizu sredine.

42
00:02:01,000 --> 00:02:03,000
U tom slučaju ćemo izabrati 55.

43
00:02:03,000 --> 00:02:06,000
Mogli smo jednako lako izabrao 89.

44
00:02:06,000 --> 00:02:11,000
Ok. Opet, 144 je veći od 55, pa idemo desno.

45
00:02:11,000 --> 00:02:14,000
Srećom za nas, sljedeći srednji broj je 144,

46
00:02:14,000 --> 00:02:16,000
jedan tražimo.

47
00:02:16,000 --> 00:02:21,000
Dakle, kako bi se pronašli 144 pomoću binarnog pretraživanja, mi smo u mogućnosti da ga pronaći u samo tri koraka.

48
00:02:21,000 --> 00:02:24,000
Ako bismo imati koristi linearnu potragu ovdje, to bi trebalo da nam 12 koraka.

49
00:02:24,000 --> 00:02:28,000
Kao što je zapravo, jer to traži način poluvremena broj predmeta

50
00:02:28,000 --> 00:02:31,000
ima da pogledate na svakom koraku, da će se naći stavku je u potrazi za

51
00:02:31,000 --> 00:02:35,000
u zapisniku o broja stavki na popisu.

52
00:02:35,000 --> 00:02:37,000
Sada kad smo vidjeli dva primjera, neka je pogledati

53
00:02:37,000 --> 00:02:41,000
neki pseudocode za rekurzivni funkciju koja implementira binarno pretraživanje.

54
00:02:41,000 --> 00:02:44,000
Počevši na vrhu, vidimo da moramo pronaći funkciju koja uzima četiri argumente:

55
00:02:44,000 --> 00:02:47,000
ključ, polje, min, a max.

56
00:02:47,000 --> 00:02:51,000
Ključ je broj koji smo u potrazi za, tako 144 u prethodnom primjeru.

57
00:02:51,000 --> 00:02:54,000
Array je popis brojeva koji smo u potrazi.

58
00:02:54,000 --> 00:02:57,000
Min i Max su indeksi minimalne i maksimalne pozicije

59
00:02:57,000 --> 00:02:59,000
da smo trenutno gleda.

60
00:02:59,000 --> 00:03:03,000
Dakle, kada smo započeli, min će biti nula i max će biti maksimalno indeks niza.

61
00:03:03,000 --> 00:03:07,000
Kao što smo suzili pretraživanje dolje, mi ćemo ažurirati min i max

62
00:03:07,000 --> 00:03:10,000
biti samo Raspon da smo još uvijek u potrazi u.

63
00:03:10,000 --> 00:03:12,000
>> Ajmo preskočiti do zanimljivog dijela prvi.

64
00:03:12,000 --> 00:03:14,000
Prva stvar koju smo učiniti je pronaći tačku,

65
00:03:14,000 --> 00:03:19,000
indeks koji je na pola puta između min i max u nizu da smo još uvijek razmišlja.

66
00:03:19,000 --> 00:03:22,000
Onda mi gledamo na vrijednosti polja u tom srednjem mjestu

67
00:03:22,000 --> 00:03:25,000
i vidjeti ako je broj da smo u potrazi za manje od tog ključa.

68
00:03:25,000 --> 00:03:27,000
Ako je broj na toj poziciji je manje,

69
00:03:27,000 --> 00:03:31,000
onda to znači da je ključ veći od svih brojeva s lijeve toj poziciji.

70
00:03:31,000 --> 00:03:33,000
Tako možemo nazvati binarni funkciju pretragu opet,

71
00:03:33,000 --> 00:03:36,000
ali ovaj put ažuriranje najmanju i najveću parametre čitati samo polovicu

72
00:03:36,000 --> 00:03:40,000
koja je veća od ili jednaka vrijednosti smo samo gledali.

73
00:03:40,000 --> 00:03:44,000
S druge strane, ako je ključ je manji od broja na danu sredinu polja,

74
00:03:44,000 --> 00:03:47,000
želimo ići lijevo i ignorirati sve brojeve koji su veći.

75
00:03:47,000 --> 00:03:52,000
Opet, mi zovemo binarno pretraživanje, ali ovaj put s rasponom min i max Updated

76
00:03:52,000 --> 00:03:54,000
uključiti samo donju polovicu.

77
00:03:54,000 --> 00:03:57,000
Ako je vrijednost u trenutnom srednjem u polju nije ni

78
00:03:57,000 --> 00:04:01,000
veći od niti manji od ključa, onda mora biti jednak za ključ.

79
00:04:01,000 --> 00:04:05,000
Dakle, možemo jednostavno vratiti trenutni indeks srednjeg, a mi smo gotovi.

80
00:04:05,000 --> 00:04:09,000
Konačno, ovaj potvrdni ovdje za slučaj da je broj

81
00:04:09,000 --> 00:04:11,000
nije zapravo u niz brojeva smo u potrazi.

82
00:04:11,000 --> 00:04:14,000
Ako je najveći indeks u rasponu da smo u potrazi za

83
00:04:14,000 --> 00:04:17,000
je sve manje od minimuma, to znači da smo otišli predaleko.

84
00:04:17,000 --> 00:04:20,000
Budući da je broj nije bio u ulaznom polju, vraćamo -1

85
00:04:20,000 --> 00:04:24,000
ukazati da se ništa nije pronađeno.

86
00:04:24,000 --> 00:04:26,000
>> Možda ste primijetili da je za ovaj algoritam za rad,

87
00:04:26,000 --> 00:04:28,000
popis brojeva mora biti riješeno.

88
00:04:28,000 --> 00:04:31,000
Drugim riječima, možemo samo naći 144 pomoću binarnog pretraživanja

89
00:04:31,000 --> 00:04:34,000
ako su svi brojevi naručio od najniže do najviše.

90
00:04:34,000 --> 00:04:38,000
Ako to nije slučaj, ne bismo bili u mogućnosti da se isključi pola brojeva na svakom koraku.

91
00:04:38,000 --> 00:04:40,000
Dakle, imamo dvije opcije.

92
00:04:40,000 --> 00:04:43,000
Ili možemo uzeti Unsorted popis i sortirati prije korištenja binarnog pretraživanja,

93
00:04:43,000 --> 00:04:48,000
ili možemo biti sigurni da je popis brojeva sortira kao što smo dodali brojeve na njega.

94
00:04:48,000 --> 00:04:50,000
Dakle, umjesto sortiranje samo kada moramo tražiti,

95
00:04:50,000 --> 00:04:53,000
zašto ne bi popis sortiran u svim vremenima?

96
00:04:53,000 --> 00:04:57,000
>> Jedan od načina da bi popis brojeva sortirani istovremeno omogućujući

97
00:04:57,000 --> 00:04:59,000
jedan dodati ili premjestiti brojeva s ovog popisa

98
00:04:59,000 --> 00:05:02,000
je pomoću nešto što se zove binarno stablo pretraživanja.

99
00:05:02,000 --> 00:05:05,000
Stablo binarno pretraživanje struktura podataka koja ima tri svojstva.

100
00:05:05,000 --> 00:05:09,000
Prvo, lijevo podstablo bilo čvoru sadrži samo vrijednosti koje su manje od

101
00:05:09,000 --> 00:05:11,000
ili jednaka čvora vrijednosti.

102
00:05:11,000 --> 00:05:15,000
Drugo, pravo podstablo od čvora sadrži samo vrijednosti koje su veće od

103
00:05:15,000 --> 00:05:17,000
ili jednaka čvora vrijednosti.

104
00:05:17,000 --> 00:05:20,000
I, konačno, obje lijeve i desne subtrees svih čvorova

105
00:05:20,000 --> 00:05:23,000
su također binarna stabla pretraživanja.

106
00:05:23,000 --> 00:05:26,000
Pogledajmo primjer s istim brojevima koje smo ranije.

107
00:05:26,000 --> 00:05:30,000
Za one od vas koji nikada nisu vidjeli stablo informatika prije,

108
00:05:30,000 --> 00:05:34,000
Dopustite mi da vam reći da je stablo informatika raste prema dolje.

109
00:05:34,000 --> 00:05:36,000
Da, za razliku od stabala ste navikli,

110
00:05:36,000 --> 00:05:38,000
korijen od stabla informatike je na vrhu,

111
00:05:38,000 --> 00:05:41,000
a listovi su na dnu.

112
00:05:41,000 --> 00:05:45,000
Svaki kutijica se zove čvor, a čvorovi su međusobno povezani po rubovima.

113
00:05:45,000 --> 00:05:48,000
Tako je korijen tog stabla je čvor vrijednost s vrijednošću 13,

114
00:05:48,000 --> 00:05:52,000
koja ima 2 djece čvorova sa vrijednostima 5 i 34.

115
00:05:52,000 --> 00:05:57,000
Podstablo je stablo koje se formiraju samo gleda na pododjeljku cijelog stabla.

116
00:05:57,000 --> 00:06:03,000
>> Na primjer, lijevo podstablo od čvora 3 je stablo stvorili čvorovi 0, 1, 2 i.

117
00:06:03,000 --> 00:06:06,000
Dakle, ako se vratimo na svojstva drveta binarnog pretraživanja,

118
00:06:06,000 --> 00:06:09,000
vidimo da je svaki čvor u stablu odgovara na sva tri svojstva, naime,

119
00:06:09,000 --> 00:06:15,000
lijevo podstablo sadrži samo vrijednosti koje su manje od ili jednaka čvora vrijednosti;

120
00:06:15,000 --> 00:06:16,000
pravo podstablo svih čvorova

121
00:06:16,000 --> 00:06:19,000
sadrži samo vrijednosti koje su veće od ili jednaka čvora vrijednosti, a

122
00:06:19,000 --> 00:06:25,000
i lijevi i desni subtrees svih čvorova su također binarna stabla pretraživanja.

123
00:06:25,000 --> 00:06:28,000
Iako je to stablo izgleda drugačije, to je valjan binarno pretraživanje stablo

124
00:06:28,000 --> 00:06:30,000
za isti skup brojeva.

125
00:06:30,000 --> 00:06:32,000
Kao Zapravo, postoji mnogo mogućih načina na koje možete napraviti

126
00:06:32,000 --> 00:06:35,000
vrijedi binarno pretraživanje stablo od tih brojeva.

127
00:06:35,000 --> 00:06:38,000
Pa, vratimo se na prvom smo stvorili.

128
00:06:38,000 --> 00:06:40,000
Dakle, ono što možemo učiniti s tih stabala?

129
00:06:40,000 --> 00:06:44,000
Pa, možemo vrlo jednostavno pronaći minimalne i maksimalne vrijednosti.

130
00:06:44,000 --> 00:06:46,000
Minimalne vrijednosti mogu se naći uvijek ide na lijevo

131
00:06:46,000 --> 00:06:48,000
dok više ne postoje čvorovi za posjetiti.

132
00:06:48,000 --> 00:06:53,000
Isto tako, kako bi pronašli najveću jedan jednostavno samo ide dolje s desne strane na svaki put.

133
00:06:54,000 --> 00:06:56,000
>> Pronalaženje bilo koji drugi broj koji nije minimalna ili maksimalna

134
00:06:56,000 --> 00:06:58,000
je jednako lako.

135
00:06:58,000 --> 00:07:00,000
Reci mi smo u potrazi za brojem 89.

136
00:07:00,000 --> 00:07:03,000
Mi jednostavno provjeriti vrijednost svakog čvora i ići lijevo ili desno,

137
00:07:03,000 --> 00:07:06,000
ovisno o tome je li čvor je vrijednost manja ili veća od

138
00:07:06,000 --> 00:07:08,000
jedan tražimo.

139
00:07:08,000 --> 00:07:11,000
Dakle, s početkom u korijenu 13, vidimo da 89 je veća,

140
00:07:11,000 --> 00:07:13,000
i tako idemo desno.

141
00:07:13,000 --> 00:07:16,000
Onda ćemo vidjeti čvor za 34, i opet idemo desno.

142
00:07:16,000 --> 00:07:20,000
89 je još uvijek veći od 55, tako da smo i dalje ide na desno.

143
00:07:20,000 --> 00:07:24,000
Mi smo tada dolazi do čvora s vrijednosti 144 i idite na lijevo.

144
00:07:24,000 --> 00:07:26,000
Evo i gle, 89 je tamo.

145
00:07:26,000 --> 00:07:31,000
>> Još jedna stvar koja mi se može učiniti je ispisati sve brojeve obavljanje inorder obuhvaćanje.

146
00:07:31,000 --> 00:07:35,000
Inorder obuhvaćanje znači ispisati sve u lijevo podstablo

147
00:07:35,000 --> 00:07:37,000
slijedi ispis čvora sama

148
00:07:37,000 --> 00:07:40,000
i onda slijedi tiskanje sve u pravo podstablo.

149
00:07:40,000 --> 00:07:43,000
Na primjer, uzmimo naše najdraže stablo binarnog pretraživanja

150
00:07:43,000 --> 00:07:46,000
i ispisati brojeve u sortiraju bi.

151
00:07:46,000 --> 00:07:49,000
Krećemo u korijenu 13, ali prije ispisa 13 moramo ispisati

152
00:07:49,000 --> 00:07:51,000
sve u lijevo podstablo.

153
00:07:51,000 --> 00:07:55,000
Tako smo ići na pet. Mi još uvijek moramo ići dublje u drvo dok ne pronađete lijevo-najviše čvor,

154
00:07:55,000 --> 00:07:57,000
koja je nula.

155
00:07:57,000 --> 00:08:00,000
Nakon ispisa nula, idemo natrag do jednog i ispisati da van.

156
00:08:00,000 --> 00:08:03,000
Onda idemo desno podstablo, koji je dvije i ispisati da van.

157
00:08:03,000 --> 00:08:05,000
Sada kada smo gotovi s tim podstablo,

158
00:08:05,000 --> 00:08:07,000
možemo se vratiti do tri i isprintati.

159
00:08:07,000 --> 00:08:11,000
Nastavljajući natrag gore, mi ispisati pet, a zatim osam.

160
00:08:11,000 --> 00:08:13,000
Sada kada smo završili cijeli lijevo podstablo,

161
00:08:13,000 --> 00:08:17,000
možemo ispisati 13 i početi raditi na pravo podstablo.

162
00:08:17,000 --> 00:08:21,000
Mi hop do 34, ali prije ispisa 34 moramo ispisati njegovo lijevo podstablo.

163
00:08:21,000 --> 00:08:27,000
Tako smo ispisali 21, tada ćemo doći do isprintati 34 i posjetiti svoje pravo podstablo.

164
00:08:27,000 --> 00:08:31,000
Od 55 nema lijevo podstablo, mi smo ga ispisali i dalje na njeno pravo podstablo.

165
00:08:31,000 --> 00:08:36,000
144 ima lijevo podstablo, pa mi isprintati 89, nakon čega slijedi 144,

166
00:08:36,000 --> 00:08:39,000
i na kraju desnom tipkom većina čvor 233.

167
00:08:39,000 --> 00:08:44,000
Ima ga imate, svi brojevi se ispisuju u redoslijedu od najniže do najviše.

168
00:08:44,000 --> 00:08:47,000
>> Dodavanje nešto na stablo je relativno bezbolno, kao dobro.

169
00:08:47,000 --> 00:08:51,000
Sve što morate učiniti je napraviti sigurni da ćemo slijediti tri binarna svojstva pretraživanja stablo

170
00:08:51,000 --> 00:08:53,000
, a zatim umetnite vrijednost tamo gdje je prostor.

171
00:08:53,000 --> 00:08:55,000
Recimo da želite umetnuti vrijednost sedam.

172
00:08:55,000 --> 00:08:58,000
Od sedam manje od 13, idemo lijevo.

173
00:08:58,000 --> 00:09:01,000
No, to je veća od 5, pa smo prošli na desno.

174
00:09:01,000 --> 00:09:04,000
Budući da je manje od 8 i 8 je čvor nultog stupnja, dodali smo 7 na lijevoj dijete osam.

175
00:09:04,000 --> 00:09:09,000
Voila! Dodali smo nekoliko našem stablu binarnog pretraživanja.

176
00:09:09,000 --> 00:09:12,000
>> Ako možemo dodati stvari, možemo bolje moći izbrisati stvari kao dobro.

177
00:09:12,000 --> 00:09:14,000
Nažalost za nas, brisanje je malo kompliciranije -

178
00:09:14,000 --> 00:09:16,000
nije puno, ali samo malo.

179
00:09:16,000 --> 00:09:18,000
Postoje tri različite scenarije da moramo uzeti u obzir

180
00:09:18,000 --> 00:09:21,000
kada brišete elemente iz binarnih stabala pretraživanja.

181
00:09:21,000 --> 00:09:24,000
Prvo, najlakše je slučaj da je element čvor nultog stupnja.

182
00:09:24,000 --> 00:09:27,000
U ovom slučaju, mi jednostavno ga izbrisati i ići na s našeg poslovanja.

183
00:09:27,000 --> 00:09:30,000
Recimo da želimo izbrisati sedam koje smo upravo dodali.

184
00:09:30,000 --> 00:09:34,000
Pa, mi jednostavno ga pronaći, uklonite ga, i to je to.

185
00:09:35,000 --> 00:09:37,000
Sljedeći slučaj je ako čvor ima samo jednog djeteta.

186
00:09:37,000 --> 00:09:40,000
Ovdje možemo izbrisati čvor, ali prvo moramo osigurati

187
00:09:40,000 --> 00:09:42,000
povezati podstablo da je sada lijevo roditelja

188
00:09:42,000 --> 00:09:44,000
do roditelja čvora smo upravo izbrisao.

189
00:09:44,000 --> 00:09:47,000
Recimo da želimo izbrisati 3 od našeg drveta.

190
00:09:47,000 --> 00:09:50,000
Mi uzeti dijete element tog čvora te ga priključiti na roditelja čvora.

191
00:09:50,000 --> 00:09:54,000
U ovom slučaju, mi smo sada pridaje 1 do 5.

192
00:09:54,000 --> 00:09:57,000
To radi bez problema, jer znamo, prema stabla binarnom pretraživanje nekretnina,

193
00:09:57,000 --> 00:10:01,000
da je sve u lijevo podstablo od 3 je manje od pet.

194
00:10:01,000 --> 00:10:05,000
Sada je tri podstablo se brine, možemo ga izbrisati.

195
00:10:05,000 --> 00:10:08,000
Treći i posljednji slučaj je najsloženiji.

196
00:10:08,000 --> 00:10:11,000
To je slučaj kada je čvor želimo izbrisati ima dvoje djece.

197
00:10:11,000 --> 00:10:15,000
Da bi to učinili, prvo moramo pronaći čvor koji ima sljedeću najveću vrijednost,

198
00:10:15,000 --> 00:10:18,000
swap dvije, a zatim izbrisati čvor u pitanju.

199
00:10:18,000 --> 00:10:22,000
Obavijest čvor koji ima sljedeća najveća vrijednost ne može imati dva djeci se

200
00:10:22,000 --> 00:10:26,000
jer je njegova lijeva dijete će biti bolji kandidat za sljedeći najveći.

201
00:10:26,000 --> 00:10:30,000
Stoga, brisanje čvora sa 2 djece iznosi zamjene od dvije čvorova,

202
00:10:30,000 --> 00:10:33,000
a zatim brisanje barata jednom od dva navedena pravila.

203
00:10:33,000 --> 00:10:37,000
Na primjer, recimo da želimo izbrisati root čvor, 13.

204
00:10:37,000 --> 00:10:39,000
Prva stvar koju radimo je da smo pronašli sljedeću najveću vrijednost u stablu

205
00:10:39,000 --> 00:10:41,000
koji, u ovom slučaju, je 21.

206
00:10:41,000 --> 00:10:46,000
Mi smo tada zamijenili dva čvorova, što 13 listova i 21 središnja skupina čvorova.

207
00:10:46,000 --> 00:10:49,000
Sada možemo jednostavno izbrisati 13.

208
00:10:50,000 --> 00:10:53,000
>> Kao aludirao na ranije, postoji mnogo mogućih načina da zaradite valjanu stablo binarnog pretraživanja.

209
00:10:53,000 --> 00:10:56,000
Nažalost za nas, neki su gori od drugih.

210
00:10:56,000 --> 00:10:59,000
Na primjer, ono što se događa kada se izgraditi binarno pretraživanje stablo

211
00:10:59,000 --> 00:11:01,000
iz sortirani popis brojeva?

212
00:11:01,000 --> 00:11:04,000
Svi brojevi se dodaje samo na desno na svakom koraku.

213
00:11:04,000 --> 00:11:06,000
Kada želimo tražiti broj,

214
00:11:06,000 --> 00:11:08,000
nemamo izbora, ali samo da pogledate desno na svakom koraku.

215
00:11:08,000 --> 00:11:11,000
Ovo nije bolje nego linearno pretraživanje na sve.

216
00:11:11,000 --> 00:11:13,000
Iako nećemo pokriti ih ovdje, tu su i drugi, složeniji,

217
00:11:13,000 --> 00:11:16,000
strukture podataka da bi bili sigurni da se to ne desi.

218
00:11:16,000 --> 00:11:18,000
Međutim, jedna jednostavna stvar koja se može učiniti kako bi se izbjeglo ovo je

219
00:11:18,000 --> 00:11:21,000
na samo slučajno dvoličnost ulaznih vrijednosti.

220
00:11:21,000 --> 00:11:26,000
To je vrlo vjerojatno da Slučajnost miješaju popis brojeva sortira.

221
00:11:26,000 --> 00:11:29,000
Ako je to slučaj, kockarnice neće ostati u poslovanju za dugo.

222
00:11:29,000 --> 00:11:31,000
>> Ima li ga imati.

223
00:11:31,000 --> 00:11:34,000
Vi sada znate o binarnom traženje i binarnih pretraživanja drveće.

224
00:11:34,000 --> 00:11:36,000
Ja sam Patrick Schmid, a ovo je CS50.

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

226
00:11:38,000 --> 00:11:43,000
Jedan očigledan način bi se skenirati popis od ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Broj predmeta ... yep

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

229
00:11:50,000 --> 00:11:55,000
... Postavljati čvor 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Jupi! To je bio -