1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binární vyhledávání]

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
>> Kdybych vám dal seznam jmen postav Disney v abecedním pořadí

5
00:00:09,000 --> 00:00:11,000
a zeptal se tě najít Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
jak byste jít asi dělá?

7
00:00:13,000 --> 00:00:15,000
Jeden zřejmý způsob, jak by bylo skenovat seznam od začátku

8
00:00:15,000 --> 00:00:18,000
a zkontrolujte, každé jméno aby zjistil, jestli je to Mickey.

9
00:00:18,000 --> 00:00:22,000
Ale jak budete číst Aladdin, Alice, Ariel, a tak dále,

10
00:00:22,000 --> 00:00:25,000
budete rychle uvědomit, že začíná v přední části seznamu nebyl dobrý nápad.

11
00:00:25,000 --> 00:00:29,000
Dobře, možná byste měli začít pracovat pozpátku od konce seznamu.

12
00:00:29,000 --> 00:00:33,000
Nyní budete číst Tarzana, steh, Sněhurka, a tak dále.

13
00:00:33,000 --> 00:00:36,000
Přesto, to nevypadá jako nejlepší způsob, jak jít na to.

14
00:00:36,000 --> 00:00:38,000
>> No, další způsob, jak byste mohli jít asi dělá, je pokusit zúžit

15
00:00:38,000 --> 00:00:41,000
seznam jmen, které budete muset podívat.

16
00:00:41,000 --> 00:00:43,000
Vzhledem k tomu, víte, že jsou v abecedním pořadí,

17
00:00:43,000 --> 00:00:45,000
vy jste mohli jen dívat na jména v polovině seznamu

18
00:00:45,000 --> 00:00:49,000
a zkontrolujte, zda Mickey Mouse je před nebo po tomto názvu.

19
00:00:49,000 --> 00:00:51,000
Při pohledu na poslední jméno v druhém sloupci

20
00:00:51,000 --> 00:00:54,000
byste si uvědomit, že M pro Mickey přichází poté, co J pro Jasmine,

21
00:00:54,000 --> 00:00:57,000
takže bys prostě ignorovat první polovinu seznamu.

22
00:00:57,000 --> 00:00:59,000
Pak jste nejspíš podíváte na horní části posledního sloupce

23
00:00:59,000 --> 00:01:02,000
a uvidíte, že to začne Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey je před Rapunzel, vypadá to, že může ignorovat poslední sloupec stejně.

25
00:01:06,000 --> 00:01:08,000
Pokračování vyhledávací strategie, budete rychle vidět, že Mickey

26
00:01:08,000 --> 00:01:11,000
je v první polovině zbývající seznamu jmen

27
00:01:11,000 --> 00:01:14,000
a konečně najít Mickey skrývá mezi Merlin a Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Co jste právě udělal, bylo v podstatě binární vyhledávání.

29
00:01:17,000 --> 00:01:22,000
Jak toto jméno napovídá, provede svoji Hledám strategii v binárním věci.

30
00:01:22,000 --> 00:01:24,000
Co to znamená?

31
00:01:24,000 --> 00:01:27,000
No, vzhledem seznam seřazena položek, binární vyhledávací algoritmus je binární rozhodnutí -

32
00:01:27,000 --> 00:01:33,000
doleva nebo doprava, větší nebo menší než, abecedně před nebo po - v každém bodě.

33
00:01:33,000 --> 00:01:35,000
Nyní, když máme název, který jde spolu s tímto vyhledávací algoritmus,

34
00:01:35,000 --> 00:01:38,000
Pojďme se podívat na další příklad, ale tentokrát se seznamem tříděných čísel.

35
00:01:38,000 --> 00:01:43,000
Řekněme, že hledáme číslo 144 v tomto seznamu seřazených čísel.

36
00:01:43,000 --> 00:01:46,000
Stejně jako předtím, najdeme číslo, které je ve středu -

37
00:01:46,000 --> 00:01:50,000
který je v tomto případě je 13 - a zjistit, zda 144 je větší nebo menší než 13 let.

38
00:01:50,000 --> 00:01:54,000
Vzhledem k tomu, že je to jasně větší než 13, můžeme ignorovat vše, co je 13 nebo méně

39
00:01:54,000 --> 00:01:57,000
a jen se soustředit na zbývající poloviny.

40
00:01:57,000 --> 00:01:59,000
Vzhledem k tomu, nyní máme dokonce počet položek vlevo,

41
00:01:59,000 --> 00:02:01,000
jsme prostě vybrat číslo, které je v blízkosti středu.

42
00:02:01,000 --> 00:02:03,000
V tomto případě jsme se rozhodli 55.

43
00:02:03,000 --> 00:02:06,000
Mohli jsme stejně snadno zvolit 89.

44
00:02:06,000 --> 00:02:11,000
Dobře. Opět, 144 je větší než 55, tak jdeme na pravé straně.

45
00:02:11,000 --> 00:02:14,000
Naštěstí pro nás, další střední číslo je 144,

46
00:02:14,000 --> 00:02:16,000
ten, kterého hledáme.

47
00:02:16,000 --> 00:02:21,000
Takže s cílem nalézt 144 pomocí binárního vyhledávání, jsme schopni najít jen ve 3 krocích.

48
00:02:21,000 --> 00:02:24,000
Pokud bychom použili lineární hledat zde, zabralo by mi to nám 12 kroků.

49
00:02:24,000 --> 00:02:28,000
Jako ve skutečnosti, protože tato metoda hledání poloviční počet položek

50
00:02:28,000 --> 00:02:31,000
má se podívat na na každém kroku, bude to najít položku je hledali

51
00:02:31,000 --> 00:02:35,000
asi v protokolu o počtu položek v seznamu.

52
00:02:35,000 --> 00:02:37,000
Teď, když jsme viděli 2 příklady, pojďme se podívat na

53
00:02:37,000 --> 00:02:41,000
některé pseudokód pro rekurzivní funkce, která implementuje binární vyhledávání.

54
00:02:41,000 --> 00:02:44,000
Od vrcholu, vidíme, že musíme najít funkci, která vezme 4 argumenty:

55
00:02:44,000 --> 00:02:47,000
klíč, pole, min, max a.

56
00:02:47,000 --> 00:02:51,000
Klíčem k úspěchu je číslo, které hledáme, tak 144 v předchozím příkladu.

57
00:02:51,000 --> 00:02:54,000
Pole je seznam čísel, která hledáme.

58
00:02:54,000 --> 00:02:57,000
Min a max jsou indexy minimální a maximální pozice

59
00:02:57,000 --> 00:02:59,000
že se v současné době hledá na.

60
00:02:59,000 --> 00:03:03,000
Takže, když se začne, bude min nulové a maximální bude maximální index pole.

61
00:03:03,000 --> 00:03:07,000
Jak jsme zúžit hledání dolů, budeme aktualizovat min a max

62
00:03:07,000 --> 00:03:10,000
být právě rozsah, který stále hledáme palců

63
00:03:10,000 --> 00:03:12,000
>> Pojďme přeskočit na zajímavé části první.

64
00:03:12,000 --> 00:03:14,000
První věc, kterou musíme udělat, je najít střed,

65
00:03:14,000 --> 00:03:19,000
index, který je na půli cesty mezi min a max na pole, které jsme stále zvažuje.

66
00:03:19,000 --> 00:03:22,000
Pak se podíváme na hodnotě pole v tomto místě středu dráhy

67
00:03:22,000 --> 00:03:25,000
a uvidíme, jestli číslo, které hledáme, je menší než daný klíč.

68
00:03:25,000 --> 00:03:27,000
Pokud je číslo v této pozici je méně,

69
00:03:27,000 --> 00:03:31,000
pak to znamená, že klíč je větší než všech čísel na levé straně této poloze.

70
00:03:31,000 --> 00:03:33,000
Takže můžeme volat binární vyhledávací funkce znovu,

71
00:03:33,000 --> 00:03:36,000
ale tentokrát aktualizaci min a max parametry číst pouze polovinu

72
00:03:36,000 --> 00:03:40,000
, který je větší než nebo rovna hodnotě jsme se podíval na.

73
00:03:40,000 --> 00:03:44,000
Na druhé straně, je-li klíč je menší, než je číslo v aktuálním středu pole,

74
00:03:44,000 --> 00:03:47,000
chceme jít doleva a ignorovat všechny čísla, která jsou větší.

75
00:03:47,000 --> 00:03:52,000
Opět, nazýváme binární vyhledávání, ale tentokrát s rozsahem min a max Aktualizováno

76
00:03:52,000 --> 00:03:54,000
zahrnout jen spodní polovina.

77
00:03:54,000 --> 00:03:57,000
Pokud je hodnota v aktuálním středu v poli není ani

78
00:03:57,000 --> 00:04:01,000
větší než ani menší než klíč, pak to musí být roven klíči.

79
00:04:01,000 --> 00:04:05,000
Tak, můžeme jednoduše vrátit aktuální midpoint index, a jsme hotovi.

80
00:04:05,000 --> 00:04:09,000
A konečně, tato kontrola je zde pro případ, že se počet

81
00:04:09,000 --> 00:04:11,000
není vlastně v poli čísel jsme hledají.

82
00:04:11,000 --> 00:04:14,000
Pokud je maximální index rozsahu, že se díváme na

83
00:04:14,000 --> 00:04:17,000
je stále nižší než minimum, to znamená, že jsme zašli příliš daleko.

84
00:04:17,000 --> 00:04:20,000
Vzhledem k tomu, počet není ve vstupním poli, jsme vrátí -1

85
00:04:20,000 --> 00:04:24,000
o tom, že nebylo nalezeno nic.

86
00:04:24,000 --> 00:04:26,000
>> Možná jste si všimli, že pro tento algoritmus pracovat,

87
00:04:26,000 --> 00:04:28,000
seznam čísel musí být seřazeny.

88
00:04:28,000 --> 00:04:31,000
Jinými slovy, můžeme najít pouze 144 pomocí binárního vyhledávání

89
00:04:31,000 --> 00:04:34,000
pokud jsou všechny čísla jsou seřazeny od nejnižší po nejvyšší.

90
00:04:34,000 --> 00:04:38,000
Pokud by tomu tak nebylo, nebyli bychom schopni vyloučit polovinu čísel na každém kroku.

91
00:04:38,000 --> 00:04:40,000
Takže máme 2 možnosti.

92
00:04:40,000 --> 00:04:43,000
Buď můžeme vzít netříděného seznamu a seřadit je před použitím binárního vyhledávání,

93
00:04:43,000 --> 00:04:48,000
nebo můžeme ujistit, že seznam čísel je řazen jak jsme přidat čísla k němu.

94
00:04:48,000 --> 00:04:50,000
Tak, místo toho třídění, právě když budeme muset hledat,

95
00:04:50,000 --> 00:04:53,000
proč ne držet seznam seřazen za všech okolností?

96
00:04:53,000 --> 00:04:57,000
>> Jeden způsob, jak udržet seznam čísel jsou seřazena současně umožňuje

97
00:04:57,000 --> 00:04:59,000
kdo přidat nebo přesunout čísla z tohoto seznamu

98
00:04:59,000 --> 00:05:02,000
je pomocí tzv. binární vyhledávací strom.

99
00:05:02,000 --> 00:05:05,000
Binární vyhledávací strom je datová struktura, která má 3 vlastnosti.

100
00:05:05,000 --> 00:05:09,000
Za prvé, levého podstromu každého uzlu obsahuje pouze hodnoty, které jsou menší než

101
00:05:09,000 --> 00:05:11,000
nebo se rovná uzlu hodnoty.

102
00:05:11,000 --> 00:05:15,000
Za druhé, právo podstrom uzlu obsahuje pouze hodnoty, které jsou větší než

103
00:05:15,000 --> 00:05:17,000
nebo rovná uzlu hodnoty.

104
00:05:17,000 --> 00:05:20,000
A konečně, jak levé a pravé podstromy všech uzlů

105
00:05:20,000 --> 00:05:23,000
jsou také binární vyhledávací stromy.

106
00:05:23,000 --> 00:05:26,000
Pojďme se podívat na příklad se stejnými čísly jsme používali dříve.

107
00:05:26,000 --> 00:05:30,000
Pro ty z vás, kteří ještě nikdy neviděl počítačové vědy strom před,

108
00:05:30,000 --> 00:05:34,000
dovolte mi začít tím, že řekne, že počítačová věda strom roste směrem dolů.

109
00:05:34,000 --> 00:05:36,000
Ano, na rozdíl od stromů, na kterou jste zvyklí,

110
00:05:36,000 --> 00:05:38,000
kořen stromu počítačové vědy je na vrcholu,

111
00:05:38,000 --> 00:05:41,000
a listy jsou na dně.

112
00:05:41,000 --> 00:05:45,000
Každý malý box se nazývá uzel, a uzly jsou navzájem spojeny hranami.

113
00:05:45,000 --> 00:05:48,000
Takže Kořen tohoto stromu je hodnota uzlu s hodnotou 13,

114
00:05:48,000 --> 00:05:52,000
která má 2 děti uzly s hodnotami 5 a 34.

115
00:05:52,000 --> 00:05:57,000
Podstrom je strom, který je tvořen jen tím, že při pohledu na odstavce celého stromu.

116
00:05:57,000 --> 00:06:03,000
>> Například, levý podstrom uzlu 3 je strom vytvořený uzly 0, 1, 2 a.

117
00:06:03,000 --> 00:06:06,000
Takže, pokud se vrátíme k vlastnostem stromu binární vyhledávání,

118
00:06:06,000 --> 00:06:09,000
vidíme, že každý uzel ve stromu odpovídá všem 3 vlastnosti, a to,

119
00:06:09,000 --> 00:06:15,000
vlevo subtree obsahuje pouze hodnoty, které jsou menší nebo rovna uzlu hodnoty;

120
00:06:15,000 --> 00:06:16,000
pravého podstromu všech uzlů

121
00:06:16,000 --> 00:06:19,000
obsahuje pouze hodnoty, které jsou větší než nebo rovno uzlu hodnoty, a

122
00:06:19,000 --> 00:06:25,000
jak levé a pravé podstromy všech uzlů jsou také stromy binární vyhledávání.

123
00:06:25,000 --> 00:06:28,000
Ačkoli tento strom vypadá jinak, je to platný binární vyhledávací strom

124
00:06:28,000 --> 00:06:30,000
pro stejnou sadu čísel.

125
00:06:30,000 --> 00:06:32,000
Jako ve skutečnosti, existuje mnoho možných způsobů, které můžete vytvořit

126
00:06:32,000 --> 00:06:35,000
platný binární vyhledávací strom z těchto čísel.

127
00:06:35,000 --> 00:06:38,000
No, vraťme se k první jsme vytvořili.

128
00:06:38,000 --> 00:06:40,000
Co tedy můžeme dělat s těmito stromy?

129
00:06:40,000 --> 00:06:44,000
No, můžeme velmi jednoduše najít minimální a maximální hodnoty.

130
00:06:44,000 --> 00:06:46,000
Minimální hodnoty lze nalézt vždycky vlevo

131
00:06:46,000 --> 00:06:48,000
dokud nejsou k dispozici žádné další uzly se můžete vydat.

132
00:06:48,000 --> 00:06:53,000
Naopak, najít maximální je prostě jen klesá doprava na každém čase.

133
00:06:54,000 --> 00:06:56,000
>> Hledání jiné číslo, které není minimální nebo maximální

134
00:06:56,000 --> 00:06:58,000
je stejně snadné.

135
00:06:58,000 --> 00:07:00,000
Řekněme, že hledáte pro číslo 89.

136
00:07:00,000 --> 00:07:03,000
Prostě jsme zkontrolovat hodnotu každého uzlu a jít doleva nebo doprava,

137
00:07:03,000 --> 00:07:06,000
v závislosti na tom, zda je uzel je hodnota menší nebo větší, než

138
00:07:06,000 --> 00:07:08,000
ten, kterého hledáme.

139
00:07:08,000 --> 00:07:11,000
Takže, počínaje u kořene 13, vidíme, že 89 je větší,

140
00:07:11,000 --> 00:07:13,000
a tak jdeme na pravé straně.

141
00:07:13,000 --> 00:07:16,000
Pak vidíme uzel pro 34, a znovu jsme se jít doprava.

142
00:07:16,000 --> 00:07:20,000
89 je ještě vyšší než 55, takže se i nadále bude na pravé straně.

143
00:07:20,000 --> 00:07:24,000
Pak jsme přišli s uzlem s hodnotou 144 a jít doleva.

144
00:07:24,000 --> 00:07:26,000
A ejhle, 89 je tady.

145
00:07:26,000 --> 00:07:31,000
>> Další věc, co můžeme udělat, je vytisknout všechna čísla provedením nezbytného traversal.

146
00:07:31,000 --> 00:07:35,000
Nezbytného traversal znamená tisknout vše v levém podstromu

147
00:07:35,000 --> 00:07:37,000
po němž následuje potisk na uzel sám

148
00:07:37,000 --> 00:07:40,000
a pak po němž následuje potisk všechno ven v pravého podstromu.

149
00:07:40,000 --> 00:07:43,000
Například, pojďme se náš oblíbený strom binárního vyhledávání

150
00:07:43,000 --> 00:07:46,000
a vytisknout čísla v seřazeném pořadí.

151
00:07:46,000 --> 00:07:49,000
Začneme u kořene 13, ale před tiskem 13 budeme muset vytisknout

152
00:07:49,000 --> 00:07:51,000
vše v levém podstromu.

153
00:07:51,000 --> 00:07:55,000
Takže jdeme na 5. Máme ještě jít hlouběji ve stromu, dokud nenajdeme nejvíce vlevo uzel,

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

155
00:07:57,000 --> 00:08:00,000
Po tisku nulové, jdeme zpátky do 1 a tisk, že ven.

156
00:08:00,000 --> 00:08:03,000
Pak jdeme na pravého podstromu, což je o 2, a vytiskněte, že ven.

157
00:08:03,000 --> 00:08:05,000
Teď, když už jsme to udělali s tím podstromu,

158
00:08:05,000 --> 00:08:07,000
se můžeme vrátit do 3 a vytisknout.

159
00:08:07,000 --> 00:08:11,000
Pokračování zálohovat, jsme vytisknout 5 a pak 8.

160
00:08:11,000 --> 00:08:13,000
Teď, když jsme dokončili celý levého podstromu,

161
00:08:13,000 --> 00:08:17,000
můžeme vytisknout 13 a začít pracovat na pravý podstrom.

162
00:08:17,000 --> 00:08:21,000
My hop až 34, ale před tiskem 34 budeme muset vytisknout jeho levého podstromu.

163
00:08:21,000 --> 00:08:27,000
Tak jsme vytisknout 21, pak jsme si vytisknout 34 a navštívit jeho pravého podstromu.

164
00:08:27,000 --> 00:08:31,000
Vzhledem k tomu, 55 nemá levého podstromu, jsme vytisknout a pokračovat na své právo podstromu.

165
00:08:31,000 --> 00:08:36,000
144 má levého podstromu, a tak jsme vytisknout 89, následuje 144,

166
00:08:36,000 --> 00:08:39,000
a nakonec nejvíce vpravo uzel z 233.

167
00:08:39,000 --> 00:08:44,000
Tady to máte, všechna čísla jsou vytištěny v pořadí od nejnižší po nejvyšší.

168
00:08:44,000 --> 00:08:47,000
>> Přidání něco stromu je relativně bezbolestná stejně.

169
00:08:47,000 --> 00:08:51,000
Vše, co musíme udělat, je ujistit, že budeme následovat 3 binární vlastnosti vyhledávacího stromu

170
00:08:51,000 --> 00:08:53,000
a pak vložit hodnotu tam, kde je prostor.

171
00:08:53,000 --> 00:08:55,000
Řekněme, že chcete vložit hodnotu 7.

172
00:08:55,000 --> 00:08:58,000
Vzhledem k tomu, 7 je menší než 13, jdeme vlevo.

173
00:08:58,000 --> 00:09:01,000
Ale to je větší než 5, takže traverz doprava.

174
00:09:01,000 --> 00:09:04,000
Vzhledem k tomu, že je to méně než 8 a 8 je koncový uzel, přidáme 7 do levého dítě 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Přidali jsme několik našich stromu binární vyhledávání.

176
00:09:09,000 --> 00:09:12,000
>> Pokud se nám podaří přidat věci, budeme lépe schopni odstranit věci stejně.

177
00:09:12,000 --> 00:09:14,000
Bohužel pro nás, mazání je trochu složitější -

178
00:09:14,000 --> 00:09:16,000
nic moc, ale jen trochu.

179
00:09:16,000 --> 00:09:18,000
K dispozici jsou 3 různé scénáře, které máme, aby zvážila

180
00:09:18,000 --> 00:09:21,000
při mazání prvků z binárních vyhledávacích stromů.

181
00:09:21,000 --> 00:09:24,000
Za prvé, Nejjednodušší případ je, že prvek je koncový uzel.

182
00:09:24,000 --> 00:09:27,000
V tomto případě, jsme jednoduše odstranit a pokračovat s naší obchodní činnosti.

183
00:09:27,000 --> 00:09:30,000
Řekněme, že chceme odstranit 7, které jsme právě přidali.

184
00:09:30,000 --> 00:09:34,000
No, prostě najít, odstranit, a to je vše.

185
00:09:35,000 --> 00:09:37,000
Další případ je v případě, že uzel má pouze 1 dítě.

186
00:09:37,000 --> 00:09:40,000
Zde můžeme smazat uzel, ale musíme nejprve ujistit,

187
00:09:40,000 --> 00:09:42,000
připojit podstromu, který je nyní ponecháno bez rodičů

188
00:09:42,000 --> 00:09:44,000
na rodiče uzlu jsme právě smazal.

189
00:09:44,000 --> 00:09:47,000
Řekněme, že chceme odstranit 3 z našeho stromu.

190
00:09:47,000 --> 00:09:50,000
Bereme podřízený prvek tohoto uzlu a připojit ji k nadřazené uzlu.

191
00:09:50,000 --> 00:09:54,000
V tomto případě, jsme nyní upevnění 1 do 5.

192
00:09:54,000 --> 00:09:57,000
Tato funkce je bez problémů, protože je známo, v závislosti na binární vyhledávací strom majetku,

193
00:09:57,000 --> 00:10:01,000
že všechno v levém podstromu 3 bylo méně než 5.

194
00:10:01,000 --> 00:10:05,000
Nyní, když je 3 je podstrom postaráno, můžeme jej odstranit.

195
00:10:05,000 --> 00:10:08,000
Třetí a poslední případ je nejsložitější.

196
00:10:08,000 --> 00:10:11,000
To je případ, kdy je uzel chceme odstranit má 2 děti.

197
00:10:11,000 --> 00:10:15,000
Aby k tomu, musíme nejprve najít uzel, který má příští největší hodnotu,

198
00:10:15,000 --> 00:10:18,000
swap dva, a potom odstraňte uzel v otázce.

199
00:10:18,000 --> 00:10:22,000
Všimněte si uzel, který má příští největší hodnota nemůže mít 2 děti sama

200
00:10:22,000 --> 00:10:26,000
protože jeho levý dítě bude lepší kandidát na příští největší.

201
00:10:26,000 --> 00:10:30,000
Proto odstranění uzlu s 2 dětmi činí prohození 2 uzly,

202
00:10:30,000 --> 00:10:33,000
a odstraněním je řešen 1 ze 2 uvedených pravidel.

203
00:10:33,000 --> 00:10:37,000
Například, řekněme, že chcete vymazat kořenový uzel, 13.

204
00:10:37,000 --> 00:10:39,000
První věc, kterou musíme udělat, je najdeme další největší hodnotu ve stromu

205
00:10:39,000 --> 00:10:41,000
která je v tomto případě, je 21.

206
00:10:41,000 --> 00:10:46,000
Pak jsme prohodit 2 uzly, takže 13 listů a 21 CENTRAL GROUP uzlu.

207
00:10:46,000 --> 00:10:49,000
Nyní můžeme jednoduše odstranit 13.

208
00:10:50,000 --> 00:10:53,000
>> Jak zmínil dříve, existuje mnoho možných způsobů, jak platný binární vyhledávací strom.

209
00:10:53,000 --> 00:10:56,000
Bohužel pro nás, některé jsou horší než ostatní.

210
00:10:56,000 --> 00:10:59,000
Například, co se stane, když budujeme binární vyhledávací strom

211
00:10:59,000 --> 00:11:01,000
z tříděného seznamu čísel?

212
00:11:01,000 --> 00:11:04,000
Všechna čísla a přidány doprava na každém kroku.

213
00:11:04,000 --> 00:11:06,000
Když chceme hledat číslo,

214
00:11:06,000 --> 00:11:08,000
nemáme jinou možnost, ale jen podívat na pravé straně na každém kroku.

215
00:11:08,000 --> 00:11:11,000
To není lepší než lineární hledání vůbec.

216
00:11:11,000 --> 00:11:13,000
I když nebudeme jejich pokrytí, je zde další, složitější,

217
00:11:13,000 --> 00:11:16,000
datové struktury, které se ujistili, že se tak nestane.

218
00:11:16,000 --> 00:11:18,000
Nicméně, jedna jednoduchá věc, že ​​by bylo možné vyhnout se

219
00:11:18,000 --> 00:11:21,000
jen na náhodně zamíchat vstupních hodnot.

220
00:11:21,000 --> 00:11:26,000
Je velmi nepravděpodobné, že by náhody je seřazena zamíchány seznam čísel.

221
00:11:26,000 --> 00:11:29,000
Pokud by tomu tak bylo, by kasina nezůstal v podnikání dlouho.

222
00:11:29,000 --> 00:11:31,000
>> Tady to máte.

223
00:11:31,000 --> 00:11:34,000
Nyní víte, o binární vyhledávání a stromy binární vyhledávání.

224
00:11:34,000 --> 00:11:36,000
Jsem Patrick Schmid, a to je CS50.

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

226
00:11:38,000 --> 00:11:43,000
Jeden zřejmý způsob, jak by bylo skenovat seznamu od ... [píp]

227
00:11:43,000 --> 00:11:46,000
... Počet kusů ... yep

228
00:11:46,000 --> 00:11:50,000
[Smích]

229
00:11:50,000 --> 00:11:55,000
... Přidat uzel 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! To bylo -