1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Szukaj binarny]

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

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

4
00:00:07,000 --> 00:00:09,000
>> Gdybym dał ci listę nazwisk Disney znaków w porządku alfabetycznym

5
00:00:09,000 --> 00:00:11,000
i poprosił o znalezienie Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
jak byś się za to zabrać?

7
00:00:13,000 --> 00:00:15,000
Oczywistym sposobem byłoby przeszukać listę od początku

8
00:00:15,000 --> 00:00:18,000
i sprawdzić każdą nazwę, aby zobaczyć, czy jest Mickey.

9
00:00:18,000 --> 00:00:22,000
Ale jak można przeczytać Aladdin, Alice, Ariel, i tak dalej,

10
00:00:22,000 --> 00:00:25,000
można szybko sobie sprawę, że zaczynając od początku listy nie był dobry pomysł.

11
00:00:25,000 --> 00:00:29,000
Okay, może powinieneś zacząć pracować wstecz od końca listy.

12
00:00:29,000 --> 00:00:33,000
Teraz możesz czytać Tarzan, Stich, Królewna Śnieżka, i tak dalej.

13
00:00:33,000 --> 00:00:36,000
Mimo to, to nie wydaje się najlepszym sposobem przejść o nim.

14
00:00:36,000 --> 00:00:38,000
>> Cóż, kolejny sposób, że można go o to robi to, aby spróbować zawęzić

15
00:00:38,000 --> 00:00:41,000
lista nazwisk, że trzeba patrzeć.

16
00:00:41,000 --> 00:00:43,000
Skoro wiesz, że są w porządku alfabetycznym,

17
00:00:43,000 --> 00:00:45,000
można po prostu spojrzeć na nazwiska w środku listy

18
00:00:45,000 --> 00:00:49,000
i sprawdzić, czy Mickey Mouse jest przed lub po tej nazwie.

19
00:00:49,000 --> 00:00:51,000
Patrząc na nazwiska w drugiej kolumnie

20
00:00:51,000 --> 00:00:54,000
, że zdajesz sobie sprawę, że M Mickey przychodzi po J dla Jasmine,

21
00:00:54,000 --> 00:00:57,000
więc trzeba po prostu zignorować pierwszą połowę listy.

22
00:00:57,000 --> 00:00:59,000
Potem pewnie patrzeć na szczycie ostatniej kolumnie

23
00:00:59,000 --> 00:01:02,000
i widzę, że zaczyna się od Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey jest przed Rapunzel; wygląda możemy zignorować ostatnią kolumnę, jak również.

25
00:01:06,000 --> 00:01:08,000
Kontynuując strategię wyszukiwania, można szybko zobaczyć, że Mickey

26
00:01:08,000 --> 00:01:11,000
jest w pierwszej połowie pozostałej listą nazw

27
00:01:11,000 --> 00:01:14,000
i wreszcie znaleźć Mickey ukrywając między Merlinem i Minnie.

28
00:01:14,000 --> 00:01:17,000
>> , Co po prostu nie było w zasadzie binary search.

29
00:01:17,000 --> 00:01:22,000
Jak to nazwa wskazuje, wykonuje swoją strategię poszukiwania w binarnym materii.

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

31
00:01:24,000 --> 00:01:27,000
Cóż, biorąc pod uwagę listę sortowanych elementów, sprawia, że ​​algorytm wyszukiwania binarnego binarnego decyzję -

32
00:01:27,000 --> 00:01:33,000
lewo lub w prawo, większa lub mniejsza, przed lub po alfabetycznie - w każdym punkcie.

33
00:01:33,000 --> 00:01:35,000
Teraz, gdy mamy nazwę, która idzie w parze z tym algorytmem wyszukiwania,

34
00:01:35,000 --> 00:01:38,000
Spójrzmy na inny przykład, tym razem z listy posortowanych numerów.

35
00:01:38,000 --> 00:01:43,000
Powiedzmy, że szukasz numeru 144 w tym listy posortowanych numerów.

36
00:01:43,000 --> 00:01:46,000
Podobnie jak wcześniej, możemy znaleźć numer, który znajduje się w środku -

37
00:01:46,000 --> 00:01:50,000
która w tym przypadku wynosi 13 - 144 i czy jest większa lub mniejsza niż 13.

38
00:01:50,000 --> 00:01:54,000
Ponieważ jest wyraźnie większa niż 13, możemy ignorować wszystko, co jest 13 lub mniej

39
00:01:54,000 --> 00:01:57,000
i po prostu skupić się na pozostałej połowy.

40
00:01:57,000 --> 00:01:59,000
Ponieważ mamy parzystą liczbę pozycji w lewo,

41
00:01:59,000 --> 00:02:01,000
po prostu wybrać numer, który jest blisko centrum.

42
00:02:01,000 --> 00:02:03,000
W tym przypadku mamy do wyboru 55.

43
00:02:03,000 --> 00:02:06,000
Moglibyśmy tak łatwo wybrać 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Ponownie, 144 jest większa niż 55, więc przejść do prawej.

45
00:02:11,000 --> 00:02:14,000
Na szczęście dla nas, następna liczba środku jest 144,

46
00:02:14,000 --> 00:02:16,000
jeden szukamy.

47
00:02:16,000 --> 00:02:21,000
Tak więc, aby wybrać 144 stosując wyszukiwanie binarne, jesteśmy w stanie go znaleźć w zaledwie 3 krokach.

48
00:02:21,000 --> 00:02:24,000
Gdybyśmy wykorzystali liniowe przeszukiwanie tutaj zajęłoby nam 12 kroków.

49
00:02:24,000 --> 00:02:28,000
W rzeczywistości, ponieważ metoda wyszukiwania połówki liczbę elementów

50
00:02:28,000 --> 00:02:31,000
musi patrzeć na każdym kroku, to znajdź element jest wyszukiwany

51
00:02:31,000 --> 00:02:35,000
w około dzienniku liczby elementów na liście.

52
00:02:35,000 --> 00:02:37,000
Teraz wiemy już 2 przykłady, rzućmy okiem na

53
00:02:37,000 --> 00:02:41,000
niektóre Pseudokod dla funkcji rekurencyjnej, który implementuje wyszukiwanie binarne.

54
00:02:41,000 --> 00:02:44,000
Zaczynając od góry, widzimy, że musimy znaleźć funkcję, która pobiera 4 argumenty:

55
00:02:44,000 --> 00:02:47,000
klucz, tablica, min i max.

56
00:02:47,000 --> 00:02:51,000
Kluczem jest numer, który szukamy, więc 144 w poprzednim przykładzie.

57
00:02:51,000 --> 00:02:54,000
Tablica jest lista numerów szukamy.

58
00:02:54,000 --> 00:02:57,000
Min i max są wskaźniki pozycji minimalnej i maksymalnej

59
00:02:57,000 --> 00:02:59,000
że jesteśmy obecnie patrząc na.

60
00:02:59,000 --> 00:03:03,000
Więc kiedy zaczynamy, min będzie zero i max będzie maksymalna indeksu tablicy.

61
00:03:03,000 --> 00:03:07,000
Jak zawęzić wyszukiwanie w dół, będziemy aktualizować MIN i MAX

62
00:03:07,000 --> 00:03:10,000
być tylko zakres, który wciąż szuka w.

63
00:03:10,000 --> 00:03:12,000
>> Pomińmy do interesującej części pierwsze.

64
00:03:12,000 --> 00:03:14,000
Pierwszą rzeczą, jaką możemy zrobić, to znaleźć punkt środkowy,

65
00:03:14,000 --> 00:03:19,000
Indeks, który jest w połowie drogi pomiędzy min i max w tablicy, że nadal rozważa.

66
00:03:19,000 --> 00:03:22,000
Patrząc na to w tablicy wartości w tym miejscu środkowym

67
00:03:22,000 --> 00:03:25,000
i sprawdzić, czy numer, który szukamy jest mniejsza niż tego klucza.

68
00:03:25,000 --> 00:03:27,000
Jeśli liczba w tej pozycji jest mniejsza,

69
00:03:27,000 --> 00:03:31,000
to znaczy, jest większy niż element z numerami na lewo tej pozycji.

70
00:03:31,000 --> 00:03:33,000
Więc możemy wywołać funkcję wyszukiwania binarnego ponownie

71
00:03:33,000 --> 00:03:36,000
ale tym razem aktualizując min i parametry max czytać tylko pół

72
00:03:36,000 --> 00:03:40,000
, która jest większa niż lub równa wartości po prostu sprawdzić.

73
00:03:40,000 --> 00:03:44,000
Z drugiej strony, jeśli klawisz jest mniejsza niż liczba w bieżącym środkowego tablicy

74
00:03:44,000 --> 00:03:47,000
chcemy iść w lewo i ignorować wszystkie numery, które są większe.

75
00:03:47,000 --> 00:03:52,000
Ponownie wzywamy przeszukiwanie binarne ale tym razem z zakresu min i max aktualizowane

76
00:03:52,000 --> 00:03:54,000
włączyć tylko dolną połowę.

77
00:03:54,000 --> 00:03:57,000
Jeżeli wartość na obecnym środkowym w tablicy nie jest ani

78
00:03:57,000 --> 00:04:01,000
większy niż nie mniejsze niż klucz, a następnie musi być równa do klucza.

79
00:04:01,000 --> 00:04:05,000
Tak więc możemy po prostu wrócić bieżący indeks punktu środkowego, a skończymy.

80
00:04:05,000 --> 00:04:09,000
Wreszcie, sprawdzanie jest dla przypadku, że liczba

81
00:04:09,000 --> 00:04:11,000
w rzeczywistości nie jest w tablicy liczb szukamy.

82
00:04:11,000 --> 00:04:14,000
Jeżeli maksymalny wskaźnik zakresu, że szukamy

83
00:04:14,000 --> 00:04:17,000
jest coraz mniej niż minimum, co oznacza, że ​​posunęliśmy się za daleko.

84
00:04:17,000 --> 00:04:20,000
Ponieważ liczba nie była w tablicy wejście, wracamy -1

85
00:04:20,000 --> 00:04:24,000
aby wskazać, że nic nie znaleziono.

86
00:04:24,000 --> 00:04:26,000
>> Można zauważyć, że w przypadku tego algorytmu do pracy,

87
00:04:26,000 --> 00:04:28,000
Lista numerów ma być sortowana.

88
00:04:28,000 --> 00:04:31,000
Innymi słowy, możemy znaleźć tylko 144 za pomocą wyszukiwania binarnego

89
00:04:31,000 --> 00:04:34,000
jeśli wszystkie numery są uporządkowane od najniższego do najwyższego.

90
00:04:34,000 --> 00:04:38,000
Jeśli nie było, to nie może wyłączyć połowę ilości, przy każdym kroku.

91
00:04:38,000 --> 00:04:40,000
Więc mamy 2 opcje.

92
00:04:40,000 --> 00:04:43,000
Albo możemy wziąć niesortowanych listę i sortować przed użyciem wyszukiwanie binarne,

93
00:04:43,000 --> 00:04:48,000
czy możemy mieć pewność, że lista numerów jest sortowana jak dodać numery do niego.

94
00:04:48,000 --> 00:04:50,000
Tak więc, zamiast sortowania tylko gdy mamy do wyszukiwania,

95
00:04:50,000 --> 00:04:53,000
dlaczego nie przechowywać listę posortowaną w każdej chwili?

96
00:04:53,000 --> 00:04:57,000
>> Jednym ze sposobów, aby utrzymać listę numerów posortowane jednocześnie umożliwiając

97
00:04:57,000 --> 00:04:59,000
jeden dodać lub przenieść numery z tej listy

98
00:04:59,000 --> 00:05:02,000
jest za pomocą czegoś, co nazywa drzewo binarne wyszukiwania.

99
00:05:02,000 --> 00:05:05,000
Drzewo wyszukiwania binarnego jest strukturą danych, która ma 3 właściwości.

100
00:05:05,000 --> 00:05:09,000
Po pierwsze, po lewej stronie każdego węzła poddrzewo zawiera tylko wartości, które są mniej niż

101
00:05:09,000 --> 00:05:11,000
lub równa wartości węzła.

102
00:05:11,000 --> 00:05:15,000
Po drugie, z prawego poddrzewa węzła zawiera tylko wartości, które są większe niż

103
00:05:15,000 --> 00:05:17,000
lub równa wartości węzła.

104
00:05:17,000 --> 00:05:20,000
I wreszcie, po lewej i prawej poddrzew wszystkich węzłów

105
00:05:20,000 --> 00:05:23,000
są również binarne drzewa wyszukiwania.

106
00:05:23,000 --> 00:05:26,000
Spójrzmy na przykład z takimi samymi numerami używaliśmy wcześniej.

107
00:05:26,000 --> 00:05:30,000
Dla tych z was, którzy nigdy nie widzieli drzewo informatyka przed,

108
00:05:30,000 --> 00:05:34,000
Zacznę mówiąc, że drzewo rośnie informatyka dół.

109
00:05:34,000 --> 00:05:36,000
Tak, w przeciwieństwie do drzew jesteś przyzwyczajony do,

110
00:05:36,000 --> 00:05:38,000
korzeń drzewa informatyki jest na górze,

111
00:05:38,000 --> 00:05:41,000
Liście i na dole.

112
00:05:41,000 --> 00:05:45,000
Każdy małe pole nazywa węzła, a węzły są połączone ze sobą krawędziami.

113
00:05:45,000 --> 00:05:48,000
Więc korzeń tego drzewa jest węzeł z wartością 13,

114
00:05:48,000 --> 00:05:52,000
która ma 2 dzieci węzły z wartościami 5 i 34.

115
00:05:52,000 --> 00:05:57,000
Poddrzewo jest drzewo, które powstaje po prostu patrząc w podsekcji całego drzewa.

116
00:05:57,000 --> 00:06:03,000
>> Na przykład, lewy poddrzewa węzeł 3 jest utworzony przez drzewa węzłów, 0, 1 i 2.

117
00:06:03,000 --> 00:06:06,000
Tak więc, jeśli chcemy wrócić do właściwości drzewa wyszukiwania binarnego,

118
00:06:06,000 --> 00:06:09,000
widzimy, że każdy węzeł w drzewie spełnia wszystkie 3 nieruchomości, a mianowicie,

119
00:06:09,000 --> 00:06:15,000
lewego poddrzewa zawiera tylko wartości, które są mniej niż lub równa wartości węzła;

120
00:06:15,000 --> 00:06:16,000
prawego poddrzewa wszystkich węzłów

121
00:06:16,000 --> 00:06:19,000
zawiera jedynie wartości, które są większe lub równe wartości węzła oraz

122
00:06:19,000 --> 00:06:25,000
zarówno lewego i prawego poddrzewa wszystkich węzłów, które są drzewa binarne wyszukiwania.

123
00:06:25,000 --> 00:06:28,000
Mimo to drzewo wygląda inaczej, jest to ważne binary search tree

124
00:06:28,000 --> 00:06:30,000
dla tych samych numerów.

125
00:06:30,000 --> 00:06:32,000
W rzeczywistości, istnieje wiele sposobów, które można tworzyć

126
00:06:32,000 --> 00:06:35,000
binary search tree ważne od tych liczb.

127
00:06:35,000 --> 00:06:38,000
Dobrze, wróćmy do pierwszego stworzyliśmy.

128
00:06:38,000 --> 00:06:40,000
Więc co możemy zrobić z tymi drzewami?

129
00:06:40,000 --> 00:06:44,000
Cóż, możemy w bardzo prosty sposób znaleźć wartości minimalne i maksymalne.

130
00:06:44,000 --> 00:06:46,000
Minimalne wartości można znaleźć, zawsze będzie w lewo

131
00:06:46,000 --> 00:06:48,000
dopóki nie ma więcej węzłów do odwiedzenia.

132
00:06:48,000 --> 00:06:53,000
Odwrotnie, aby znaleźć maksymalną tuż po prostu przechodzi do prawego w każdym czasie.

133
00:06:54,000 --> 00:06:56,000
>> Znalezienie inny numer nie minimalnej lub maksymalnej jest

134
00:06:56,000 --> 00:06:58,000
jest tak samo łatwe.

135
00:06:58,000 --> 00:07:00,000
Powiedzmy, że szukasz numeru 89.

136
00:07:00,000 --> 00:07:03,000
Po prostu sprawdzić wartość każdego węzła i iść w lewo lub w prawo,

137
00:07:03,000 --> 00:07:06,000
zależnie od tego czy wartość węzła jest mniejszy lub większy niż

138
00:07:06,000 --> 00:07:08,000
jeden szukamy.

139
00:07:08,000 --> 00:07:11,000
Więc, zaczynając od podstaw 13, widzimy, że 89 jest większa,

140
00:07:11,000 --> 00:07:13,000
i tak idziemy w prawo.

141
00:07:13,000 --> 00:07:16,000
Następnie widzimy węzeł 34, i znowu idziemy w prawo.

142
00:07:16,000 --> 00:07:20,000
89 jest w dalszym ciągu większe niż 55, tak, że nadal będzie do prawej.

143
00:07:20,000 --> 00:07:24,000
Następnie wymyślić węzła o wartości 144 i idź w lewo.

144
00:07:24,000 --> 00:07:26,000
I oto 89 jest tu.

145
00:07:26,000 --> 00:07:31,000
>> Inną rzeczą, którą możemy zrobić, to wydrukować wszystkie numery, wykonując inorder przechodzenie.

146
00:07:31,000 --> 00:07:35,000
Inorder traversal oznacza drukować wszystko w lewo poddrzewo

147
00:07:35,000 --> 00:07:37,000
poprzez drukowanie węzeł się

148
00:07:37,000 --> 00:07:40,000
a następnie poprzez drukowanie wszystkiego w prawym poddrzewie.

149
00:07:40,000 --> 00:07:43,000
Na przykład, weźmy nasze ulubione drzewo wyszukiwania binarnego

150
00:07:43,000 --> 00:07:46,000
i wydrukować numery posortowanych.

151
00:07:46,000 --> 00:07:49,000
Zaczynamy u podstaw 13, ale przed drukowaniem 13 mamy do wydrukowania

152
00:07:49,000 --> 00:07:51,000
wszystko w lewo poddrzewa.

153
00:07:51,000 --> 00:07:55,000
Więc idziemy do 5. Mamy jeszcze głębiej w dół drzewa, aż znajdziemy lewej najwięcej węzła

154
00:07:55,000 --> 00:07:57,000
która jest zero.

155
00:07:57,000 --> 00:08:00,000
Po wydrukowaniu zerowej, wracamy do 1 i wydrukować to.

156
00:08:00,000 --> 00:08:03,000
Potem idziemy do prawego poddrzewa, które jest 2 i wydrukować to.

157
00:08:03,000 --> 00:08:05,000
Teraz, kiedy skończysz z tym poddrzewie

158
00:08:05,000 --> 00:08:07,000
możemy wrócić do 3 i wydrukować.

159
00:08:07,000 --> 00:08:11,000
Kontynuując powrotem, drukujemy 5 i 8.

160
00:08:11,000 --> 00:08:13,000
Teraz, po zakończeniu całego lewego poddrzewa,

161
00:08:13,000 --> 00:08:17,000
możemy wydrukować 13 i rozpocząć pracę na prawym poddrzewie.

162
00:08:17,000 --> 00:08:21,000
Mamy hop aż do 34, ale przed drukowaniem 34 musimy wydrukować jego lewego poddrzewa.

163
00:08:21,000 --> 00:08:27,000
Więc wydrukować 21, a następnie dostać się do wydrukowania 34 i odwiedzić jego prawego poddrzewa.

164
00:08:27,000 --> 00:08:31,000
Od 55 nie ma lewego poddrzewa, możemy wydrukować go i przejdź do jego prawego poddrzewa.

165
00:08:31,000 --> 00:08:36,000
144 ma lewą poddrzewa i wydrukować więc 89, a następnie przez 144,

166
00:08:36,000 --> 00:08:39,000
wreszcie najbardziej prawym węzłem 233.

167
00:08:39,000 --> 00:08:44,000
Nie masz go, wszystkie numery są drukowane w kolejności od najniższego do najwyższego.

168
00:08:44,000 --> 00:08:47,000
>> Dodając coś do drzewa jest stosunkowo bezbolesny, jak również.

169
00:08:47,000 --> 00:08:51,000
Wszystko, co musimy zrobić, to upewnić się, że idziemy za 3 wyszukiwania właściwości drzewa binarnego

170
00:08:51,000 --> 00:08:53,000
a następnie wstawić wartości, gdzie jest miejsce.

171
00:08:53,000 --> 00:08:55,000
Powiedzmy, że chcemy wstawić wartość 7.

172
00:08:55,000 --> 00:08:58,000
Od 7 jest mniejsza niż 13, idziemy w lewo.

173
00:08:58,000 --> 00:09:01,000
Ale jest większy niż 5, tak, że przechodzenie w prawo.

174
00:09:01,000 --> 00:09:04,000
Ponieważ jest to mniej niż 8, a 8 jest węzeł liścia, to dodaje się 7 do 8 lewej dziecka.

175
00:09:04,000 --> 00:09:09,000
Voila! Dodaliśmy numer do naszego drzewa wyszukiwania binarnego.

176
00:09:09,000 --> 00:09:12,000
>> Jeśli możemy dodać rzeczy, lepiej być w stanie usunąć rzeczy, jak również.

177
00:09:12,000 --> 00:09:14,000
Niestety dla nas, usuwania jest trochę bardziej skomplikowane -

178
00:09:14,000 --> 00:09:16,000
nie dużo, ale tylko trochę.

179
00:09:16,000 --> 00:09:18,000
Istnieją 3 różne scenariusze, które musimy wziąć pod uwagę

180
00:09:18,000 --> 00:09:21,000
podczas usuwania elementów z drzewa binarne wyszukiwania.

181
00:09:21,000 --> 00:09:24,000
Po pierwsze, jest najprostszym przypadku jest to, że element węzeł liścia.

182
00:09:24,000 --> 00:09:27,000
W tym przypadku, po prostu usunąć i przejść z naszej działalności.

183
00:09:27,000 --> 00:09:30,000
Powiedzmy, że chcesz usunąć 7 że właśnie dodane.

184
00:09:30,000 --> 00:09:34,000
Cóż, po prostu znaleźć, usuń go, a to jest to.

185
00:09:35,000 --> 00:09:37,000
Następna sprawa, jeśli węzeł ma tylko 1 dziecko.

186
00:09:37,000 --> 00:09:40,000
Tutaj możemy usunąć węzeł, ale najpierw musimy się upewnić,

187
00:09:40,000 --> 00:09:42,000
połączyć poddrzewa, które teraz w lewo nadrzędnymi

188
00:09:42,000 --> 00:09:44,000
do nadrzędnego węzła po prostu usunięte.

189
00:09:44,000 --> 00:09:47,000
Powiedzmy, że chcesz usunąć 3 z naszego drzewa.

190
00:09:47,000 --> 00:09:50,000
Bierzemy element podrzędny tego węzła i dołączyć go do nadrzędnego węzła.

191
00:09:50,000 --> 00:09:54,000
W tym przypadku, jesteśmy teraz mocowania 1 do 5.

192
00:09:54,000 --> 00:09:57,000
Działa to bez problemu, ponieważ wiadomo, w zależności od własności wyszukiwania binarnego drzewa

193
00:09:57,000 --> 00:10:01,000
że wszystko w lewo poddrzewo 3 było mniej niż 5.

194
00:10:01,000 --> 00:10:05,000
Teraz, 3'S poddrzewo jest pod opieką, możemy go usunąć.

195
00:10:05,000 --> 00:10:08,000
Trzecia i ostatnia sprawa jest najbardziej skomplikowana.

196
00:10:08,000 --> 00:10:11,000
Tak jest w przypadku, gdy węzeł chcemy usunąć ma 2 dzieci.

197
00:10:11,000 --> 00:10:15,000
Aby to zrobić, musimy najpierw znaleźć węzeł, który ma z kolei największą wartość,

198
00:10:15,000 --> 00:10:18,000
zamienić dwa, a następnie usunąć węzeł pytanie.

199
00:10:18,000 --> 00:10:22,000
Wskazówka węzeł, który ma następna największa wartość nie może mieć 2 dzieci się

200
00:10:22,000 --> 00:10:26,000
ponieważ jego lewa dziecko będzie lepszym kandydatem na następne największe.

201
00:10:26,000 --> 00:10:30,000
Dlatego usuwanie węzła z 2 dzieci wynosi swapping 2 węzłów,

202
00:10:30,000 --> 00:10:33,000
a następnie usuwając jest obsługiwany przez 1 z 2 wymienionymi powyżej regułami.

203
00:10:33,000 --> 00:10:37,000
Na przykład, powiedzmy, że chcemy usunąć węzeł główny, 13.

204
00:10:37,000 --> 00:10:39,000
Pierwszą rzeczą, jaką możemy zrobić, to znaleźć następną największą wartość w drzewie

205
00:10:39,000 --> 00:10:41,000
która w tym przypadku wynosi 21.

206
00:10:41,000 --> 00:10:46,000
Następnie zamienić 2 węzłów, co czyni 13 liści i 21 centralny węzeł grupy.

207
00:10:46,000 --> 00:10:49,000
Teraz możemy po prostu usunąć 13.

208
00:10:50,000 --> 00:10:53,000
>> Jak wspomniałem wcześniej, istnieje wiele możliwych sposobów, aby poprawny drzewo wyszukiwania binarnego.

209
00:10:53,000 --> 00:10:56,000
Niestety dla nas, niektóre są gorsze od innych.

210
00:10:56,000 --> 00:10:59,000
Na przykład, co się dzieje, kiedy możemy zbudować drzewo binarne wyszukiwania

211
00:10:59,000 --> 00:11:01,000
z posortowanej listy liczb?

212
00:11:01,000 --> 00:11:04,000
Wszystkie numery są po prostu dodaje się w prawo w każdym kroku.

213
00:11:04,000 --> 00:11:06,000
Gdy chcemy wyszukać numer,

214
00:11:06,000 --> 00:11:08,000
nie mamy wyboru, ale tylko patrzeć na prawo na każdym kroku.

215
00:11:08,000 --> 00:11:11,000
To nie jest lepszy niż liniowy wyszukiwania.

216
00:11:11,000 --> 00:11:13,000
Mimo, że nie obejmie ich tutaj, istnieją inne, bardziej złożone,

217
00:11:13,000 --> 00:11:16,000
struktury danych, które składają się, że tak się nie stanie.

218
00:11:16,000 --> 00:11:18,000
Jednakże, jeden prosty, co można wykonać w celu uniknięcia jest

219
00:11:18,000 --> 00:11:21,000
do po prostu losowo Shuffle wartości wejściowych.

220
00:11:21,000 --> 00:11:26,000
Jest wysoce prawdopodobne, że przez przypadek losowy tasuje lista numerów jest posortowana.

221
00:11:26,000 --> 00:11:29,000
Jeśli tak było, kasyna nie zatrzymam się w biznesie na długo.

222
00:11:29,000 --> 00:11:31,000
>> Nie masz go.

223
00:11:31,000 --> 00:11:34,000
Teraz wiesz o binarnego przeszukiwania i wyszukiwania drzew binarnych.

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

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

226
00:11:38,000 --> 00:11:43,000
Oczywistym sposobem byłoby przeszukać listę od ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Liczba elementów ... yep

228
00:11:46,000 --> 00:11:50,000
[Śmieje się]

229
00:11:50,000 --> 00:11:55,000
... Post węzeł 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! To było -