1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binárne vyhľadávanie]

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
>> Keby som vám dal zoznam mien postáv Disney v abecednom poradí

5
00:00:09,000 --> 00:00:11,000
a spýtal sa ťa nájsť Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
ako by ste ísť asi robí?

7
00:00:13,000 --> 00:00:15,000
Jeden zrejmý spôsob, ako by bolo skenovať zoznam od začiatku

8
00:00:15,000 --> 00:00:18,000
a skontrolujte, každé meno aby zistil, či je to Mickey.

9
00:00:18,000 --> 00:00:22,000
Ale ako budete čítať Aladdin, Alice, Ariel, a tak ďalej,

10
00:00:22,000 --> 00:00:25,000
budete rýchlo uvedomiť, že začína v prednej časti zoznamu nebol dobrý nápad.

11
00:00:25,000 --> 00:00:29,000
Dobre, možno by ste mali začať pracovať pospiatky od konca zoznamu.

12
00:00:29,000 --> 00:00:33,000
Teraz budete čítať Tarzana, steh, Snehulienka, a tak ďalej.

13
00:00:33,000 --> 00:00:36,000
Napriek tomu, to nevyzerá ako najlepší spôsob, ako ísť na to.

14
00:00:36,000 --> 00:00:38,000
>> No, ďalší spôsob, ako by ste mohli ísť asi robí, je pokúsiť zúžiť

15
00:00:38,000 --> 00:00:41,000
zoznam mien, ktoré budete musieť pozrieť.

16
00:00:41,000 --> 00:00:43,000
Vzhľadom k tomu, viete, že sú v abecednom poradí,

17
00:00:43,000 --> 00:00:45,000
vy ste mohli len pozerať na mená v polovici zoznamu

18
00:00:45,000 --> 00:00:49,000
a skontrolujte, či Mickey Mouse je pred alebo po tomto názve.

19
00:00:49,000 --> 00:00:51,000
Pri pohľade na posledné meno v druhom stĺpci

20
00:00:51,000 --> 00:00:54,000
by ste si uvedomiť, že M pre Mickey prichádza potom, čo J pre Jasmine,

21
00:00:54,000 --> 00:00:57,000
takže by si jednoducho ignorovať prvú polovicu zoznamu.

22
00:00:57,000 --> 00:00:59,000
Potom ste asi pozriete na hornej časti posledného stĺpca

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 pred Rapunzel, vyzerá to, že môže ignorovať posledný stĺpec rovnako.

25
00:01:06,000 --> 00:01:08,000
Pokračovanie vyhľadávacie stratégie, budete rýchlo vidieť, že Mickey

26
00:01:08,000 --> 00:01:11,000
je v prvej polovici zostávajúce zoznamu mien

27
00:01:11,000 --> 00:01:14,000
a konečne nájsť Mickey skrýva medzi Merlin a Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Čo ste práve urobil, bolo v podstate binárne vyhľadávanie.

29
00:01:17,000 --> 00:01:22,000
Ako toto meno napovedá, vykoná svoju Hľadám stratégiu v binárnom veci.

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

31
00:01:24,000 --> 00:01:27,000
No, vzhľadom zoznam zoradené položiek, binárny vyhľadávací algoritmus je binárne rozhodnutie -

32
00:01:27,000 --> 00:01:33,000
doľava alebo doprava, väčšie alebo menšie ako, abecedne pred alebo po - v každom bode.

33
00:01:33,000 --> 00:01:35,000
Teraz, keď máme názov, ktorý ide spolu s týmto vyhľadávací algoritmus,

34
00:01:35,000 --> 00:01:38,000
Poďme sa pozrieť na ďalší príklad, ale tentoraz so zoznamom triedených čísel.

35
00:01:38,000 --> 00:01:43,000
Povedzme, že hľadáme číslo 144 v tomto zozname zoradených čísel.

36
00:01:43,000 --> 00:01:46,000
Rovnako ako predtým, nájdeme číslo, ktoré je v strede -

37
00:01:46,000 --> 00:01:50,000
ktorý je v tomto prípade je 13 - a zistiť, či 144 je väčší alebo menší ako 13 rokov.

38
00:01:50,000 --> 00:01:54,000
Vzhľadom k tomu, že je to jasne väčší ako 13, môžeme ignorovať všetko, čo je 13 alebo menej

39
00:01:54,000 --> 00:01:57,000
a len sa sústrediť na zostávajúce polovice.

40
00:01:57,000 --> 00:01:59,000
Vzhľadom k tomu, teraz máme dokonca počet položiek vľavo,

41
00:01:59,000 --> 00:02:01,000
sme jednoducho vybrať číslo, ktoré je v blízkosti stredu.

42
00:02:01,000 --> 00:02:03,000
V tomto prípade sme sa rozhodli 55.

43
00:02:03,000 --> 00:02:06,000
Mohli sme rovnako ľahko zvoliť 89.

44
00:02:06,000 --> 00:02:11,000
Dobre. Opäť, 144 je väčší ako 55, takže choďte doprava.

45
00:02:11,000 --> 00:02:14,000
Našťastie pre nás, ďalšie stredné číslo je 144,

46
00:02:14,000 --> 00:02:16,000
ten, ktorého hľadáme.

47
00:02:16,000 --> 00:02:21,000
Takže s cieľom nájsť 144 pomocou binárneho vyhľadávania, sme schopní nájsť len v 3 krokoch.

48
00:02:21,000 --> 00:02:24,000
Ak by sme použili lineárne hľadať tu, zabralo by mi to nám 12 krokov.

49
00:02:24,000 --> 00:02:28,000
Ako v skutočnosti, pretože táto metóda hľadania polovičná počet položiek

50
00:02:28,000 --> 00:02:31,000
má sa pozrieť na na každom kroku, bude to nájsť položku je hľadali

51
00:02:31,000 --> 00:02:35,000
asi v protokole o počte položiek v zozname.

52
00:02:35,000 --> 00:02:37,000
Teraz, keď sme videli 2 príklady, poďme sa pozrieť na

53
00:02:37,000 --> 00:02:41,000
niektoré pseudokód pre rekurzívne funkcie, ktorá implementuje binárne vyhľadávanie.

54
00:02:41,000 --> 00:02:44,000
Od vrcholu, vidíme, že musíme nájsť funkciu, ktorá vezme 4 argumenty:

55
00:02:44,000 --> 00:02:47,000
kľúč, pole, min, max a

56
00:02:47,000 --> 00:02:51,000
Kľúčom je číslo, ktoré hľadáme, tak 144 v predchádzajúcom príklade.

57
00:02:51,000 --> 00:02:54,000
Pole je zoznam čísel, ktoré hľadáme.

58
00:02:54,000 --> 00:02:57,000
Min a max sú indexy minimálne a maximálne pozície

59
00:02:57,000 --> 00:02:59,000
že sa v súčasnej dobe hľadá na.

60
00:02:59,000 --> 00:03:03,000
Takže, keď sa začne, bude min nulové a maximálnu bude maximálny index poľa.

61
00:03:03,000 --> 00:03:07,000
Ako sme zúžiť hľadanie dole, budeme aktualizovať min a max

62
00:03:07,000 --> 00:03:10,000
byť práve rozsah, ktorý stále hľadáme palcov

63
00:03:10,000 --> 00:03:12,000
>> Poďme preskočiť na zaujímavé časti prvej.

64
00:03:12,000 --> 00:03:14,000
Prvá vec, ktorú musíme urobiť, je nájsť stred,

65
00:03:14,000 --> 00:03:19,000
index, ktorý je na polceste medzi min a max na pole, ktoré sme stále zvažuje.

66
00:03:19,000 --> 00:03:22,000
Potom sa pozrieme na hodnote poľa v tomto mieste strede dráhy

67
00:03:22,000 --> 00:03:25,000
a zistiť, či číslo, ktoré hľadáme, je menšia ako daný kľúč.

68
00:03:25,000 --> 00:03:27,000
Ak je číslo v tejto pozícii je menej,

69
00:03:27,000 --> 00:03:31,000
potom to znamená, že kľúč je väčšia než všetkých čísel naľavo tejto polohe.

70
00:03:31,000 --> 00:03:33,000
Takže môžeme volať binárne vyhľadávacie funkcie znovu,

71
00:03:33,000 --> 00:03:36,000
ale tentoraz aktualizáciu min a max parametre čítať iba polovicu

72
00:03:36,000 --> 00:03:40,000
, Ktorý je väčší alebo rovná hodnote sme sa pozrel na.

73
00:03:40,000 --> 00:03:44,000
Na druhej strane, ak je kľúč je menší, než je číslo v aktuálnom stredu poľa,

74
00:03:44,000 --> 00:03:47,000
chceme ísť doľava a ignorovať všetky čísla, ktoré sú väčšie.

75
00:03:47,000 --> 00:03:52,000
Opäť, nazývame binárne vyhľadávanie, ale tentoraz s rozsahom min a max Aktualizované

76
00:03:52,000 --> 00:03:54,000
zahrnúť len spodná polovica.

77
00:03:54,000 --> 00:03:57,000
Ak je hodnota v aktuálnom stredu v poli nie je ani

78
00:03:57,000 --> 00:04:01,000
väčší ako ani menšie ako kľúč, potom to musí byť rovný kľúčmi.

79
00:04:01,000 --> 00:04:05,000
Tak, môžeme jednoducho vrátiť aktuálne midpoint index, a sme hotoví.

80
00:04:05,000 --> 00:04:09,000
A konečne, táto kontrola je tu pre prípad, že sa počet

81
00:04:09,000 --> 00:04:11,000
nie je vlastne v poli čísel sme hľadajú.

82
00:04:11,000 --> 00:04:14,000
Ak je maximálny index rozsahu, že sa pozeráme na

83
00:04:14,000 --> 00:04:17,000
je stále nižšia než minimum, to znamená, že sme zašli príliš ďaleko.

84
00:04:17,000 --> 00:04:20,000
Vzhľadom k tomu, počet nie je vo vstupnom poli, sme vráti -1

85
00:04:20,000 --> 00:04:24,000
o tom, že sa nenašlo nič.

86
00:04:24,000 --> 00:04:26,000
>> Možno ste si všimli, že pre tento algoritmus pracovať,

87
00:04:26,000 --> 00:04:28,000
zoznam čísel musí byť zoradené.

88
00:04:28,000 --> 00:04:31,000
Inými slovami, môžeme nájsť iba 144 pomocou binárneho vyhľadávania

89
00:04:31,000 --> 00:04:34,000
ak sú všetky čísla sú zoradené od najnižšej po najvyššiu.

90
00:04:34,000 --> 00:04:38,000
Ak by tomu tak nebolo, neboli by sme schopní vylúčiť polovicu čísel na každom 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 vziať netriedeného zoznamu a zoradiť ich pred použitím binárneho vyhľadávania,

93
00:04:43,000 --> 00:04:48,000
alebo môžeme uistiť, že zoznam čísel je radený ako sme pridať čísla k nemu.

94
00:04:48,000 --> 00:04:50,000
Tak, namiesto toho triedenie, práve keď budeme musieť hľadať,

95
00:04:50,000 --> 00:04:53,000
prečo nie držať zoznam zoradený za všetkých okolností?

96
00:04:53,000 --> 00:04:57,000
>> Jeden spôsob, ako udržať zoznam čísel sú zoradené súčasne umožňuje

97
00:04:57,000 --> 00:04:59,000
kto pridať alebo presunúť čísla z tohto zoznamu

98
00:04:59,000 --> 00:05:02,000
je pomocou tzv binárny vyhľadávací strom.

99
00:05:02,000 --> 00:05:05,000
Binárne vyhľadávacie strom je dátová štruktúra, ktorá má 3 vlastnosti.

100
00:05:05,000 --> 00:05:09,000
Po prvé, ľavého podstromu každého uzla obsahuje iba hodnoty, ktoré sú menšie ako

101
00:05:09,000 --> 00:05:11,000
alebo sa rovná uzla hodnoty.

102
00:05:11,000 --> 00:05:15,000
Po druhé, právo podstrom uzla obsahuje iba hodnoty, ktoré sú väčšie ako

103
00:05:15,000 --> 00:05:17,000
alebo rovná uzla hodnoty.

104
00:05:17,000 --> 00:05:20,000
A konečne, ako ľavej a pravej podstromy všetkých uzlov

105
00:05:20,000 --> 00:05:23,000
sú tiež binárne vyhľadávacie stromy.

106
00:05:23,000 --> 00:05:26,000
Poďme sa pozrieť na príklad s rovnakými číslami sme používali predtým.

107
00:05:26,000 --> 00:05:30,000
Pre tých z vás, ktorí ešte nikdy nevidel počítačovej vedy strom pred,

108
00:05:30,000 --> 00:05:34,000
dovoľte mi začať tým, že povie, že počítačová veda strom rastie smerom dole.

109
00:05:34,000 --> 00:05:36,000
Áno, na rozdiel od stromov, na ktorú ste zvyknutí,

110
00:05:36,000 --> 00:05:38,000
koreň stromu počítačovej vedy je na vrchole,

111
00:05:38,000 --> 00:05:41,000
a listy sú na dne.

112
00:05:41,000 --> 00:05:45,000
Každý malý box sa nazýva uzol, a uzly sú navzájom spojené hranami.

113
00:05:45,000 --> 00:05:48,000
Takže Koreň tohto stromu je hodnota uzla s hodnotou 13,

114
00:05:48,000 --> 00:05:52,000
ktorá má 2 deti uzly s hodnotami 5 a 34.

115
00:05:52,000 --> 00:05:57,000
Podstrom je strom, ktorý je tvorený len tým, že pri pohľade na odseky celého stromu.

116
00:05:57,000 --> 00:06:03,000
>> Napríklad, ľavý podstrom uzla 3 je strom vytvorený uzly 0, 1, 2 a

117
00:06:03,000 --> 00:06:06,000
Takže, ak sa vrátime k vlastnostiam stromu binárne vyhľadávanie,

118
00:06:06,000 --> 00:06:09,000
vidíme, že každý uzol v strome zodpovedá všetkým 3 vlastnosti, a to,

119
00:06:09,000 --> 00:06:15,000
ľavého podstromu obsahuje iba hodnoty, ktoré sú menšie alebo rovná uzla hodnoty;

120
00:06:15,000 --> 00:06:16,000
právo podstromu všetkých uzlov

121
00:06:16,000 --> 00:06:19,000
obsahuje iba hodnoty, ktoré sú väčšie alebo rovné uzla hodnoty, a

122
00:06:19,000 --> 00:06:25,000
ako ľavej a pravej podstromy všetkých uzlov sú tiež stromy binárne vyhľadávanie.

123
00:06:25,000 --> 00:06:28,000
Hoci tento strom vyzerá inak, je to platný binárny vyhľadávací strom

124
00:06:28,000 --> 00:06:30,000
pre rovnakú sadu čísel.

125
00:06:30,000 --> 00:06:32,000
Ako v skutočnosti, existuje mnoho možných spôsobov, ktoré môžete vytvoriť

126
00:06:32,000 --> 00:06:35,000
platný binárny vyhľadávací strom z týchto čísel.

127
00:06:35,000 --> 00:06:38,000
No, vráťme sa k prvej sme vytvorili.

128
00:06:38,000 --> 00:06:40,000
Čo teda môžeme robiť s týmito stromami?

129
00:06:40,000 --> 00:06:44,000
No, môžeme veľmi jednoducho nájsť minimálne a maximálne hodnoty.

130
00:06:44,000 --> 00:06:46,000
Minimálne hodnoty možno nájsť vždy vľavo

131
00:06:46,000 --> 00:06:48,000
kým nie sú k dispozícii žiadne ďalšie uzly sa môžete vydať.

132
00:06:48,000 --> 00:06:53,000
Naopak, nájsť maximálnu je jednoducho len klesá doprava v každom okamihu.

133
00:06:54,000 --> 00:06:56,000
>> Nájdenie iné množstvo, že nie je minimálna alebo maximálna

134
00:06:56,000 --> 00:06:58,000
je rovnako jednoduché.

135
00:06:58,000 --> 00:07:00,000
Povedzme, že hľadáte pre číslo 89.

136
00:07:00,000 --> 00:07:03,000
Proste sme skontrolovať hodnotu každého uzla a ísť doľava alebo doprava,

137
00:07:03,000 --> 00:07:06,000
v závislosti na tom, či je uzol je hodnota menšia alebo väčšia, ako

138
00:07:06,000 --> 00:07:08,000
ten, ktorého hľadáme.

139
00:07:08,000 --> 00:07:11,000
Takže, počnúc pri koreni 13, vidíme, že 89 je väčšia,

140
00:07:11,000 --> 00:07:13,000
a tak ideme na pravej strane.

141
00:07:13,000 --> 00:07:16,000
Potom vidíme uzol pre 34, a znovu sme sa ísť doprava.

142
00:07:16,000 --> 00:07:20,000
89 je ešte vyššia ako 55, takže sa aj naďalej bude na pravej strane.

143
00:07:20,000 --> 00:07:24,000
Potom sme prišli s uzlom s hodnotou 144 a ísť doľava.

144
00:07:24,000 --> 00:07:26,000
A ajhľa, 89 je tu.

145
00:07:26,000 --> 00:07:31,000
>> Ďalšia vec, čo môžeme urobiť, je vytlačiť všetky čísla prevedením nevyhnutného traversal.

146
00:07:31,000 --> 00:07:35,000
Nevyhnutného traversal znamená tlačiť všetko v ľavom podstromu

147
00:07:35,000 --> 00:07:37,000
po ktorom nasleduje potlač na uzol sám

148
00:07:37,000 --> 00:07:40,000
a potom po ktorom nasleduje potlač všetko von v pravého podstrome.

149
00:07:40,000 --> 00:07:43,000
Napríklad, poďme sa náš obľúbený strom binárneho vyhľadávania

150
00:07:43,000 --> 00:07:46,000
a vytlačiť čísla v zoradené poradí.

151
00:07:46,000 --> 00:07:49,000
Začneme pri koreni 13, ale pred tlačou 13 budeme musieť vytlačiť

152
00:07:49,000 --> 00:07:51,000
všetko v ľavom podstrome.

153
00:07:51,000 --> 00:07:55,000
Takže ideme na 5. Máme ešte ísť hlbšie v strome, kým nenájdeme najviac vľavo uzol,

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

155
00:07:57,000 --> 00:08:00,000
Po tlače nulové, ideme späť do 1 a tlač, že von.

156
00:08:00,000 --> 00:08:03,000
Potom ideme na pravého podstromu, čo je o 2, a vytlačte, že von.

157
00:08:03,000 --> 00:08:05,000
Teraz, keď už sme to urobili s tým podstromu,

158
00:08:05,000 --> 00:08:07,000
sa môžeme vrátiť do 3 a vytlačiť.

159
00:08:07,000 --> 00:08:11,000
Pokračovanie zálohovať, sme vytlačiť 5 a potom 8.

160
00:08:11,000 --> 00:08:13,000
Teraz, keď sme dokončili celý ľavého podstromu,

161
00:08:13,000 --> 00:08:17,000
môžeme vytlačiť 13 a začať pracovať na pravý podstrom.

162
00:08:17,000 --> 00:08:21,000
My hop až 34, ale pred tlačou 34 budeme musieť vytlačiť jeho ľavého podstrome.

163
00:08:21,000 --> 00:08:27,000
Tak sme vytlačiť 21, potom sme si vytlačiť 34 a navštíviť jeho pravého podstromu.

164
00:08:27,000 --> 00:08:31,000
Vzhľadom k tomu, 55 nemá ľavého podstromu, sme vytlačiť a pokračovať na svoje právo podstrome.

165
00:08:31,000 --> 00:08:36,000
144 má ľavého podstromu, a tak sme vytlačiť 89, nasleduje 144,

166
00:08:36,000 --> 00:08:39,000
a nakoniec najviac vpravo uzol z 233.

167
00:08:39,000 --> 00:08:44,000
Tu to máte, všetky čísla sú vytlačené v poradí od najnižšej po najvyššiu.

168
00:08:44,000 --> 00:08:47,000
>> Pridanie niečo stromu je relatívne bezbolestná rovnako.

169
00:08:47,000 --> 00:08:51,000
Všetko, čo musíme urobiť, je uistiť, že budeme nasledovať 3 binárne vlastnosti vyhľadávacieho stromu

170
00:08:51,000 --> 00:08:53,000
a potom vložiť hodnotu tam, kde je priestor.

171
00:08:53,000 --> 00:08:55,000
Povedzme, že chcete vložiť hodnotu 7.

172
00:08:55,000 --> 00:08:58,000
Vzhľadom k tomu, 7 je menší ako 13, ideme vľavo.

173
00:08:58,000 --> 00:09:01,000
Ale to je väčšia ako 5, takže traverz doprava.

174
00:09:01,000 --> 00:09:04,000
Vzhľadom k tomu, že je to menej ako 8 a 8 je koncový uzol, pridáme 7 do ľavého dieťa 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Pridali sme niekoľko našich stromu binárne vyhľadávanie.

176
00:09:09,000 --> 00:09:12,000
>> Ak sa nám podarí pridať veci, budeme lepšie schopní odstrániť veci rovnako.

177
00:09:12,000 --> 00:09:14,000
Bohužiaľ pre nás, mazanie je trochu zložitejšie -

178
00:09:14,000 --> 00:09:16,000
nič moc, ale len trochu.

179
00:09:16,000 --> 00:09:18,000
K dispozícii sú 3 rôzne scenáre, ktoré máme, aby zvážila

180
00:09:18,000 --> 00:09:21,000
pri mazaní prvkov z binárnych vyhľadávacích stromov.

181
00:09:21,000 --> 00:09:24,000
Po prvé, najjednoduchšie prípad je, že prvok je koncový uzol.

182
00:09:24,000 --> 00:09:27,000
V tomto prípade, sme jednoducho odstrániť a pokračovať s našej obchodnej činnosti.

183
00:09:27,000 --> 00:09:30,000
Povedzme, že chceme odstrániť 7, ktoré sme práve pridali.

184
00:09:30,000 --> 00:09:34,000
No, jednoducho nájsť, odstrániť, a to je všetko.

185
00:09:35,000 --> 00:09:37,000
Ďalší prípad je v prípade, že uzol má len 1 dieťa.

186
00:09:37,000 --> 00:09:40,000
Tu môžeme zmazať uzol, ale musíme najprv uistiť,

187
00:09:40,000 --> 00:09:42,000
pripojiť podstrome, ktorý je teraz ponechané bez rodičov

188
00:09:42,000 --> 00:09:44,000
na rodičov uzla sme práve zmazal.

189
00:09:44,000 --> 00:09:47,000
Povedzme, že chceme odstrániť 3 z nášho stromu.

190
00:09:47,000 --> 00:09:50,000
Berieme podriadený prvok tohto uzla a pripojiť ju k nadradenej uzla.

191
00:09:50,000 --> 00:09:54,000
V tomto prípade, sme teraz upevnenie 1 do 5.

192
00:09:54,000 --> 00:09:57,000
Táto funkcia je bez problémov, pretože je známe, v závislosti na binárne vyhľadávacie strom majetku,

193
00:09:57,000 --> 00:10:01,000
že všetko v ľavom podstrome 3 bolo menej ako 5.

194
00:10:01,000 --> 00:10:05,000
Teraz, keď je 3 je podstrom postarané, môžeme ho odstrániť.

195
00:10:05,000 --> 00:10:08,000
Tretí a posledný prípad je najzložitejšie.

196
00:10:08,000 --> 00:10:11,000
To je prípad, keď je uzol chceme odstrániť má 2 deti.

197
00:10:11,000 --> 00:10:15,000
Aby k tomu, musíme najprv nájsť uzol, ktorý má budúci najväčšiu hodnotu,

198
00:10:15,000 --> 00:10:18,000
swap dva, a potom odstráňte uzol v otázke.

199
00:10:18,000 --> 00:10:22,000
Všimnite si uzol, ktorý má budúci najväčšiu hodnotu nemožno mať 2 deti sama

200
00:10:22,000 --> 00:10:26,000
pretože jeho ľavej dieťa bude lepší kandidát na budúci najväčší.

201
00:10:26,000 --> 00:10:30,000
Preto odstránenie uzla s 2 deťmi robí prehodenie 2 uzly,

202
00:10:30,000 --> 00:10:33,000
a odstránením je riešený 1 z 2 uvedených pravidiel.

203
00:10:33,000 --> 00:10:37,000
Napríklad, povedzme, že chcete vymazať koreňový uzol, 13.

204
00:10:37,000 --> 00:10:39,000
Prvá vec, ktorú musíme urobiť, je nájdeme ďalšie najväčšiu hodnotu vo stromu

205
00:10:39,000 --> 00:10:41,000
ktorá je v tomto prípade, je 21.

206
00:10:41,000 --> 00:10:46,000
Potom sme prehodiť 2 uzly, takže 13 listov a 21 CENTRAL GROUP uzla.

207
00:10:46,000 --> 00:10:49,000
Teraz môžeme jednoducho odstrániť 13.

208
00:10:50,000 --> 00:10:53,000
>> Ako spomenul skôr, existuje mnoho možných spôsobov, ako platný binárny vyhľadávací strom.

209
00:10:53,000 --> 00:10:56,000
Bohužiaľ pre nás, niektoré sú horšie ako ostatné.

210
00:10:56,000 --> 00:10:59,000
Napríklad, čo sa stane, keď budujeme binárny vyhľadávací strom

211
00:10:59,000 --> 00:11:01,000
z triedeného zoznamu čísel?

212
00:11:01,000 --> 00:11:04,000
Všetky čísla a pridané doprava na každom kroku.

213
00:11:04,000 --> 00:11:06,000
Keď chceme hľadať číslo,

214
00:11:06,000 --> 00:11:08,000
nemáme inú možnosť, ale len pozrieť na pravej strane na každom kroku.

215
00:11:08,000 --> 00:11:11,000
To nie je lepšie ako lineárny hľadanie vôbec.

216
00:11:11,000 --> 00:11:13,000
Aj keď nebudeme ich pokrytie, je tu ďalšie, zložitejšie,

217
00:11:13,000 --> 00:11:16,000
dátové štruktúry, ktoré sa uistili, že sa tak nestane.

218
00:11:16,000 --> 00:11:18,000
Avšak, jedna jednoduchá vec, že ​​by bolo možné vyhnúť sa

219
00:11:18,000 --> 00:11:21,000
len na náhodne zamiešať vstupných hodnôt.

220
00:11:21,000 --> 00:11:26,000
Je veľmi nepravdepodobné, že by náhody je zoradená zamiešané zoznam čísel.

221
00:11:26,000 --> 00:11:29,000
Ak by tomu tak bolo, by kasína nezostal v podnikaní dlho.

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

223
00:11:31,000 --> 00:11:34,000
Teraz viete, o binárne vyhľadávanie a stromy binárne vyhľadávanie.

224
00:11:34,000 --> 00:11:36,000
Som 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 zrejmý spôsob, ako by bolo skenovať zoznamu od ... [píp]

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

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

229
00:11:50,000 --> 00:11:55,000
... Pridať uzol 234 ... augh.

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