1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Cautare binară]

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

3
00:00:04,000 --> 00:00:07,000
[Acest lucru este CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Dacă ți-am dat o listă de nume de caractere Disney, în ordine alfabetică

5
00:00:09,000 --> 00:00:11,000
și ți-a cerut să găsească Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
cum ai de gând să faci asta?

7
00:00:13,000 --> 00:00:15,000
Un mod evident ar fi de a scana si lista de la început

8
00:00:15,000 --> 00:00:18,000
și să verificați fiecare nume pentru a vedea dacă e Mickey.

9
00:00:18,000 --> 00:00:22,000
Dar, așa cum ai citit Aladdin, Alice, Ariel, și așa mai departe,

10
00:00:22,000 --> 00:00:25,000
iti vei da seama repede că începând de la partea din față a listei nu a fost o idee bună.

11
00:00:25,000 --> 00:00:29,000
Bine, poate că ar trebui să înceapă lucrul înapoi de la sfârșitul listei.

12
00:00:29,000 --> 00:00:33,000
Acum ai citit Tarzan, Stitch, Alba ca Zapada, și așa mai departe.

13
00:00:33,000 --> 00:00:36,000
Totusi, acest lucru nu pare ca cel mai bun mod de a merge despre asta.

14
00:00:36,000 --> 00:00:38,000
>> Ei bine, un alt mod de faptul că ați putea merge despre a face acest lucru este de a încerca pentru a restrânge

15
00:00:38,000 --> 00:00:41,000
lista de nume pe care va trebui să se uite la.

16
00:00:41,000 --> 00:00:43,000
Din moment ce știu că sunt în ordine alfabetică,

17
00:00:43,000 --> 00:00:45,000
ai putea uita doar la numele în mijlocul listei

18
00:00:45,000 --> 00:00:49,000
și verificați dacă Mickey Mouse este înainte sau după acest nume.

19
00:00:49,000 --> 00:00:51,000
Privind la numele de familie, în coloana a doua

20
00:00:51,000 --> 00:00:54,000
vei realiza că M pentru Mickey vine dupa J pentru Jasmine,

21
00:00:54,000 --> 00:00:57,000
asa ca ar fi pur și simplu ignorați prima jumătate a listei.

22
00:00:57,000 --> 00:00:59,000
Apoi te-ai uita, probabil, în partea de sus a coloanei ultimei

23
00:00:59,000 --> 00:01:02,000
și vezi că începe cu Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey vine inainte de Rapunzel, arata ca putem ignora ultima coloana, de asemenea.

25
00:01:06,000 --> 00:01:08,000
Continuând strategia de căutare, veți vedea repede că Mickey

26
00:01:08,000 --> 00:01:11,000
este în prima jumătate a listei de nume rămase

27
00:01:11,000 --> 00:01:14,000
și de a găsi în cele din urmă Mickey ascuns între Merlin și Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Ce ai făcut a fost practic căutare binară.

29
00:01:17,000 --> 00:01:22,000
Deoarece această sugereaza si numele, aceasta efectuează strategia de căutare într-o chestiune binar.

30
00:01:22,000 --> 00:01:24,000
Ce înseamnă?

31
00:01:24,000 --> 00:01:27,000
Ei bine, având în vedere o listă de articole sortate, algoritmul de cautare binara face o decizie binar -

32
00:01:27,000 --> 00:01:33,000
la stânga sau la dreapta, mai mare sau mai mică, în ordine alfabetică înainte sau după - la fiecare punct.

33
00:01:33,000 --> 00:01:35,000
Acum, că avem un nume, care merge impreuna cu acest algoritm de căutare,

34
00:01:35,000 --> 00:01:38,000
să ne uităm la un alt exemplu, dar de data aceasta cu o listă de numere sortate.

35
00:01:38,000 --> 00:01:43,000
Spune cautam pentru numărul 144 în această listă de numere sortate.

36
00:01:43,000 --> 00:01:46,000
La fel ca înainte, vom găsi numărul care este în mijlocul -

37
00:01:46,000 --> 00:01:50,000
care în acest caz este de 13 - 144 și a vedea dacă este mai mare sau mai mică de 13.

38
00:01:50,000 --> 00:01:54,000
Din moment ce este în mod evident mai mare de 13, putem ignora tot ceea ce este de 13 sau mai putin

39
00:01:54,000 --> 00:01:57,000
și să se concentreze doar pe jumătatea rămasă.

40
00:01:57,000 --> 00:01:59,000
Din moment ce avem acum un numar par de elemente plecat,

41
00:01:59,000 --> 00:02:01,000
vom alege pur și simplu un număr care este aproape de mijloc.

42
00:02:01,000 --> 00:02:03,000
În acest caz, vom alege 55.

43
00:02:03,000 --> 00:02:06,000
Am fi putut la fel de ușor de ales 89.

44
00:02:06,000 --> 00:02:11,000
Bine. Din nou, 144 este mai mare decât 55 de ani, asa ca du-te la dreapta.

45
00:02:11,000 --> 00:02:14,000
Din fericire pentru noi, numărul de mijloc următoare este 144,

46
00:02:14,000 --> 00:02:16,000
cel pe care îl căutăm.

47
00:02:16,000 --> 00:02:21,000
Deci, în scopul de a găsi 144 utilizând o căutare binară, suntem în măsură să-l găsească în doar 3 pași.

48
00:02:21,000 --> 00:02:24,000
Dacă ne-ar fi folosit de căutare liniară aici, ne-ar fi luat 12 etape.

49
00:02:24,000 --> 00:02:28,000
Ca o chestiune de fapt, deoarece această metodă de căutare reprize la numărul de articole

50
00:02:28,000 --> 00:02:31,000
are să se uite puțin la fiecare pas, ea va găsi elementul care este în căutarea

51
00:02:31,000 --> 00:02:35,000
în legătură cu jurnalul de numărul de elemente din listă.

52
00:02:35,000 --> 00:02:37,000
Acum, că ne-am văzut 2 exemple, haideți să aruncăm o privire la

53
00:02:37,000 --> 00:02:41,000
unele pseudocod pentru o funcție recursivă care pune în aplicare cautare binara.

54
00:02:41,000 --> 00:02:44,000
Începând de la partea de sus, vedem că trebuie să găsim o funcție care ia 4 argumente:

55
00:02:44,000 --> 00:02:47,000
cheie, matrice, min, si max.

56
00:02:47,000 --> 00:02:51,000
Cheia este numărul pe care îl căutați, deci 144 în exemplul anterior.

57
00:02:51,000 --> 00:02:54,000
Array este lista de numere pe care le căutați.

58
00:02:54,000 --> 00:02:57,000
Min și max sunt indicii ale pozițiilor minime și maxime

59
00:02:57,000 --> 00:02:59,000
că suntem în prezent în căutarea de la.

60
00:02:59,000 --> 00:03:03,000
Deci, atunci când vom începe, min va fi zero si maxim va fi indicele maxim de matrice.

61
00:03:03,000 --> 00:03:07,000
Așa cum am restrânge căutarea în jos, vom actualiza min și max

62
00:03:07,000 --> 00:03:10,000
să fie doar intervalul pe care suntem încă în căutarea inch

63
00:03:10,000 --> 00:03:12,000
>> Să trece la partea interesantă primul.

64
00:03:12,000 --> 00:03:14,000
Primul lucru pe care facem este să găsească punctul de mijloc,

65
00:03:14,000 --> 00:03:19,000
indicele care este la jumătatea distanței dintre min si max de matrice pe care suntem încă în considerare.

66
00:03:19,000 --> 00:03:22,000
Apoi ne uităm la valoarea de matrice de la acea locație punctul de mijloc

67
00:03:22,000 --> 00:03:25,000
și a vedea dacă numărul pe care îl căutați este mai mică decât cea cheie.

68
00:03:25,000 --> 00:03:27,000
În cazul în care numărul de la această poziție este mai puțin,

69
00:03:27,000 --> 00:03:31,000
atunci înseamnă că cheia este mai mare decât toate numerele de la stânga această poziție.

70
00:03:31,000 --> 00:03:33,000
Deci, putem apela funcția de căutare binară, din nou,

71
00:03:33,000 --> 00:03:36,000
dar de data aceasta actualizarea min și max parametrii pentru a citi doar jumătate

72
00:03:36,000 --> 00:03:40,000
care este mai mare sau egală cu valoarea ne-am uitat la.

73
00:03:40,000 --> 00:03:44,000
Pe de altă parte, în cazul în care cheia este mai mic decât numărul de la punctul de mijloc curent de matrice,

74
00:03:44,000 --> 00:03:47,000
vrem să mergem la stânga și ignora toate numerele care sunt mai mari.

75
00:03:47,000 --> 00:03:52,000
Din nou, noi numim binar de căutare, dar de data aceasta cu gama de min max și actualizate

76
00:03:52,000 --> 00:03:54,000
pentru a include doar jumătatea inferioară.

77
00:03:54,000 --> 00:03:57,000
În cazul în care valoarea de la punctul de mijloc curentă în matrice nu este nici

78
00:03:57,000 --> 00:04:01,000
mai mare decât nici mai mică decât cheia, atunci acesta trebuie să fie egală cu cheia.

79
00:04:01,000 --> 00:04:05,000
Astfel, ne putem întoarce pur și simplu indicele mijloc curent, și am terminat.

80
00:04:05,000 --> 00:04:09,000
În cele din urmă, această verificare este aici pentru cazul în care numărul de

81
00:04:09,000 --> 00:04:11,000
nu este de fapt în matrice de numere cautam.

82
00:04:11,000 --> 00:04:14,000
În cazul în care indicele maxim din gama pe care le căutați

83
00:04:14,000 --> 00:04:17,000
este tot mai puțin decât minimul, ceea ce înseamnă că ne-am mers prea departe.

84
00:04:17,000 --> 00:04:20,000
Deoarece numărul nu a fost în matrice de intrare, ne întoarcem -1

85
00:04:20,000 --> 00:04:24,000
pentru a indica faptul că nimic nu a fost găsit.

86
00:04:24,000 --> 00:04:26,000
>> Este posibil să fi observat că, pentru acest algoritm pentru a lucra,

87
00:04:26,000 --> 00:04:28,000
lista de numere trebuie să fie sortate.

88
00:04:28,000 --> 00:04:31,000
Cu alte cuvinte, putem găsi numai 144 folosind cautare binara

89
00:04:31,000 --> 00:04:34,000
în cazul în care toate numerele sunt ordonate de la cel mai mic la cel mai mare.

90
00:04:34,000 --> 00:04:38,000
Dacă acest lucru nu a fost cazul, nu am fi în măsură să excludă jumătate din numerele de la fiecare pas.

91
00:04:38,000 --> 00:04:40,000
Deci avem 2 opțiuni.

92
00:04:40,000 --> 00:04:43,000
Fie putem lua o listă nesortate și sorta-l înainte de a utiliza căutare binară,

93
00:04:43,000 --> 00:04:48,000
sau putem să ne asigurăm că lista de numere este sortată după cum vom adăuga numere la ea.

94
00:04:48,000 --> 00:04:50,000
Astfel, în loc de sortare doar atunci când avem de a căuta,

95
00:04:50,000 --> 00:04:53,000
de ce nu ține lista sortată în orice moment?

96
00:04:53,000 --> 00:04:57,000
>> O modalitate de a păstra o listă de numere sortată în același timp permițând

97
00:04:57,000 --> 00:04:59,000
o să adăugați sau mutați numerele din această listă

98
00:04:59,000 --> 00:05:02,000
este prin utilizarea ceva numit un arbore binar de căutare.

99
00:05:02,000 --> 00:05:05,000
Un arbore binar de căutare este o structură de date care are 3 proprietati.

100
00:05:05,000 --> 00:05:09,000
În primul rând, subarborele stâng al oricărui nod conține numai valorile care sunt mai puțin

101
00:05:09,000 --> 00:05:11,000
sau egală cu valoarea nodului.

102
00:05:11,000 --> 00:05:15,000
În al doilea rând, dreptul subarbore al unui nod conține doar valori care sunt mai mari decât

103
00:05:15,000 --> 00:05:17,000
sau egală cu valoarea nodului.

104
00:05:17,000 --> 00:05:20,000
Și, în sfârșit, atât subarbori stânga și din dreapta ale tuturor nodurilor

105
00:05:20,000 --> 00:05:23,000
sunt, de asemenea, arbori binari de căutare.

106
00:05:23,000 --> 00:05:26,000
Să ne uităm la un exemplu, cu aceleași numere le-am folosit mai devreme.

107
00:05:26,000 --> 00:05:30,000
Pentru cei dintre voi care nu au văzut un copac computer înainte de stiinta,

108
00:05:30,000 --> 00:05:34,000
permiteți-mi să încep prin a vă spune că un copac informatică crește în jos.

109
00:05:34,000 --> 00:05:36,000
Da, spre deosebire de copaci v-ați obișnuit să,

110
00:05:36,000 --> 00:05:38,000
rădăcina unui copac informatică este în partea de sus,

111
00:05:38,000 --> 00:05:41,000
și frunzele sunt în partea de jos.

112
00:05:41,000 --> 00:05:45,000
Fiecare cutie mica se numeste un nod, iar nodurile sunt conectate între ele prin muchii.

113
00:05:45,000 --> 00:05:48,000
Deci, rădăcina acestui arbore este o valoare nod cu valoarea 13,

114
00:05:48,000 --> 00:05:52,000
care are 2 copii cu noduri valorile 5 și 34.

115
00:05:52,000 --> 00:05:57,000
Un subarbore este copac care este format doar uitandu-te la o subsecțiune a tot arborele.

116
00:05:57,000 --> 00:06:03,000
>> De exemplu, subarbore stâng al nodului 3 este arborele creat de la 0, 1, noduri și 2.

117
00:06:03,000 --> 00:06:06,000
Deci, dacă ne întoarcem la proprietățile unui arbore binar de căutare,

118
00:06:06,000 --> 00:06:09,000
vedem că fiecare nod din arbore conform cu toate cele 3 proprietăți, și anume,

119
00:06:09,000 --> 00:06:15,000
subarbore stânga conține numai valori care sunt mai mici sau egale cu valoarea nodului;

120
00:06:15,000 --> 00:06:16,000
dreptul subarbore al tuturor nodurilor

121
00:06:16,000 --> 00:06:19,000
conține numai valori care sunt mai mari sau egale cu valoarea nodului; și

122
00:06:19,000 --> 00:06:25,000
subarbori atât stânga și dreapta ale tuturor nodurilor, de asemenea, sunt copaci de căutare binare.

123
00:06:25,000 --> 00:06:28,000
Deși acest copac arată diferit, acest lucru este valabil un arbore binar de căutare

124
00:06:28,000 --> 00:06:30,000
pentru același set de numere.

125
00:06:30,000 --> 00:06:32,000
Ca o chestiune de fapt, există multe moduri posibile pe care le puteți crea

126
00:06:32,000 --> 00:06:35,000
o adresă validă de căutare arbore binar de la aceste numere.

127
00:06:35,000 --> 00:06:38,000
Ei bine, hai să ne întoarcem la primul am creat.

128
00:06:38,000 --> 00:06:40,000
Deci, ce putem face cu aceste copaci?

129
00:06:40,000 --> 00:06:44,000
Ei bine, putem foarte simplu găsi valorile minime și maxime.

130
00:06:44,000 --> 00:06:46,000
Valorile minime pot fi găsite de către întotdeauna merge spre stânga

131
00:06:46,000 --> 00:06:48,000
până când nu există noduri nu mai pentru a vizita.

132
00:06:48,000 --> 00:06:53,000
În schimb, pentru a găsi cea maximă pur și simplu doar se duce în jos la dreapta, la fiecare dată.

133
00:06:54,000 --> 00:06:56,000
>> Găsirea orice alt număr care nu este minim sau maxim

134
00:06:56,000 --> 00:06:58,000
este la fel de ușor.

135
00:06:58,000 --> 00:07:00,000
Spune-ne ce cautati numarul 89.

136
00:07:00,000 --> 00:07:03,000
Noi verificam pur și simplu valoarea fiecărui nod și du-te la stânga sau la dreapta,

137
00:07:03,000 --> 00:07:06,000
în funcție de valoarea nodului este mai mică sau mai mare decât

138
00:07:06,000 --> 00:07:08,000
cel pe care îl căutăm.

139
00:07:08,000 --> 00:07:11,000
Deci, pornind de la rădăcina de 13, vom vedea că 89 este mai mare,

140
00:07:11,000 --> 00:07:13,000
și astfel vom merge la dreapta.

141
00:07:13,000 --> 00:07:16,000
Apoi vom vedea nodul de 34, și din nou mergem la dreapta.

142
00:07:16,000 --> 00:07:20,000
89 este încă mai mare decât 55 de ani, asa ca va continua spre dreapta.

143
00:07:20,000 --> 00:07:24,000
Am venit apoi cu un nod cu valoarea de 144 și du-te la stânga.

144
00:07:24,000 --> 00:07:26,000
Lo și iată, 89 este chiar acolo.

145
00:07:26,000 --> 00:07:31,000
>> Un alt lucru pe care îl putem face este imprima toate numerele de efectuarea unei traversarea inorder.

146
00:07:31,000 --> 00:07:35,000
O traversare inorder înseamnă totul pentru a imprima în subarborele stâng

147
00:07:35,000 --> 00:07:37,000
urmată de imprimare nodul în sine

148
00:07:37,000 --> 00:07:40,000
și apoi urmată de imprimarea totul în dreapta subarbore.

149
00:07:40,000 --> 00:07:43,000
De exemplu, să luăm nostru favorit arbore binar de căutare

150
00:07:43,000 --> 00:07:46,000
și imprima numerele în ordine sortată.

151
00:07:46,000 --> 00:07:49,000
Vom începe de la rădăcina de 13, dar înainte de imprimare 13 trebuie să imprime

152
00:07:49,000 --> 00:07:51,000
totul în subarborele stâng.

153
00:07:51,000 --> 00:07:55,000
Deci, mergem la 5. Noi încă mai trebuie să meargă mai adânc în arborele până când vom găsi cea mai din stânga nod,

154
00:07:55,000 --> 00:07:57,000
care este zero.

155
00:07:57,000 --> 00:08:00,000
După imprimare de zero, vom merge înapoi până la 1 și a imprima asta.

156
00:08:00,000 --> 00:08:03,000
Apoi vom merge la subarborele drept, care este 2, și imprima asta.

157
00:08:03,000 --> 00:08:05,000
Acum că am terminat cu asta subarborele,

158
00:08:05,000 --> 00:08:07,000
putem merge înapoi până la 3 și imprimați-l.

159
00:08:07,000 --> 00:08:11,000
Continuând back-up, am imprima 5 și apoi 8.

160
00:08:11,000 --> 00:08:13,000
Acum, că ne-am completat tot subarborele stânga,

161
00:08:13,000 --> 00:08:17,000
putem imprima 13 și începe să lucreze la dreapta subarbore.

162
00:08:17,000 --> 00:08:21,000
Am hop până la 34 de ani, dar înainte de imprimare 34 trebuie să imprime subarbore stânga sa.

163
00:08:21,000 --> 00:08:27,000
Așa că am tipări 21; apoi vom ajunge să imprime 34 și vizita de dreptul său de subarborele.

164
00:08:27,000 --> 00:08:31,000
Din moment ce 55 nu are subarbore stâng, l-am tipăriți și să continue pe subarbore drept al acestuia.

165
00:08:31,000 --> 00:08:36,000
144 are un subarbore stâng, și așa am imprima 89, urmat de 144,

166
00:08:36,000 --> 00:08:39,000
și, în final nodul dreapta-cea mai mare de 233.

167
00:08:39,000 --> 00:08:44,000
Nu-l ai, toate numerele sunt imprimate în ordine de la cel mai mic la cel mai mare.

168
00:08:44,000 --> 00:08:47,000
>> Adăugarea ceva de copac este relativ nedureroasa, de asemenea.

169
00:08:47,000 --> 00:08:51,000
Tot ce trebuie să faceți este să vă asigurați că urmăm 3 Proprietăți de căutare binare copac

170
00:08:51,000 --> 00:08:53,000
și apoi introduceți valoarea în cazul în care există spațiu.

171
00:08:53,000 --> 00:08:55,000
Să spunem că doriți să introduceți valoarea de 7.

172
00:08:55,000 --> 00:08:58,000
Deoarece 7 este mai mic de 13, mergem la stânga.

173
00:08:58,000 --> 00:09:01,000
Dar e mai mare de 5, asa ca am traversare la dreapta.

174
00:09:01,000 --> 00:09:04,000
Deoarece este mai mică de 8 și 8 este un nod frunză, se adaugă 7 la copilul stânga 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Am adăugat un număr la arbore binar nostru de cautare.

176
00:09:09,000 --> 00:09:12,000
>> Dacă putem adăuga lucruri, vom fi mai în măsură să ștergeți lucrurile la fel de bine.

177
00:09:12,000 --> 00:09:14,000
Din nefericire pentru noi, ștergerea este un pic mai complicată -

178
00:09:14,000 --> 00:09:16,000
nu de mult, dar doar un pic.

179
00:09:16,000 --> 00:09:18,000
Există 3 scenarii diferite care trebuie să le ia în considerare

180
00:09:18,000 --> 00:09:21,000
atunci când ștergeți elemente din arborii de căutare binare.

181
00:09:21,000 --> 00:09:24,000
În primul rând, cel mai simplu caz este faptul că elementul este un nod frunză.

182
00:09:24,000 --> 00:09:27,000
În acest caz, vom șterge pur și simplu și du-te mai departe cu afacerea noastră.

183
00:09:27,000 --> 00:09:30,000
Spune că vrem să ștergeți 7 pe care tocmai l-am adăugat.

184
00:09:30,000 --> 00:09:34,000
Ei bine, am găsit pur și simplu, scoateți-l, și asta e tot.

185
00:09:35,000 --> 00:09:37,000
Următorul caz este daca nodul are doar 1 copil.

186
00:09:37,000 --> 00:09:40,000
Aici putem șterge nodul, dar mai întâi trebuie să ne asigurăm

187
00:09:40,000 --> 00:09:42,000
pentru a conecta subarborelui care este acum lăsat fără părinți

188
00:09:42,000 --> 00:09:44,000
la mamă a nodului ne-am șters.

189
00:09:44,000 --> 00:09:47,000
Spune că vrem să ștergeți 3 de la copacul nostru.

190
00:09:47,000 --> 00:09:50,000
Ne ia copilul elementul de acel nod și atașați-l la mamă a nodului.

191
00:09:50,000 --> 00:09:54,000
În acest caz, suntem acum atașarea de la 1 la 5.

192
00:09:54,000 --> 00:09:57,000
Aceasta funcționează fără nici o problemă pentru că știm, în funcție de copac binar de căutare de proprietate,

193
00:09:57,000 --> 00:10:01,000
că totul în subarborele stâng al 3 a fost mai mică de 5.

194
00:10:01,000 --> 00:10:05,000
Acum, că a subarborelui 3 este ocupat de, putem sterge.

195
00:10:05,000 --> 00:10:08,000
Caz treia și ultima este cel mai complex.

196
00:10:08,000 --> 00:10:11,000
Acesta este cazul atunci când nodul vrem să ștergeți are 2 copii.

197
00:10:11,000 --> 00:10:15,000
În scopul de a face acest lucru, trebuie mai întâi să găsească nod care are cea mai mare valoare următoare,

198
00:10:15,000 --> 00:10:18,000
schimba doi, iar apoi ștergeți nodul în cauză.

199
00:10:18,000 --> 00:10:22,000
Observați nodul care are cea mai mare valoare următoare nu poate avea 2 copii în sine

200
00:10:22,000 --> 00:10:26,000
de la copilul său din stânga ar fi un candidat mai bun pentru cea mai mare următoare.

201
00:10:26,000 --> 00:10:30,000
De aceea, ștergerea unui nod cu 2 copii se ridică la schimbarea de 2 noduri,

202
00:10:30,000 --> 00:10:33,000
și apoi ștergerea este manipulat de 1 din cele 2 regulilor menționate mai sus.

203
00:10:33,000 --> 00:10:37,000
De exemplu, să spunem că doriți să ștergeți nodul rădăcină, 13.

204
00:10:37,000 --> 00:10:39,000
Primul lucru ce facem este găsim valoarea următoare cea mai mare în structura

205
00:10:39,000 --> 00:10:41,000
care, în acest caz, este de 21.

206
00:10:41,000 --> 00:10:46,000
Noi swap cele 2 noduri, făcând o frunză 13 și 21 nodul central de grup.

207
00:10:46,000 --> 00:10:49,000
Acum putem șterge pur și simplu 13.

208
00:10:50,000 --> 00:10:53,000
>> În ceea ce a făcut aluzie la mai devreme, există multe moduri de a face posibile valid arbore binar de căutare.

209
00:10:53,000 --> 00:10:56,000
Din nefericire pentru noi, unele sunt mai rău decât altele.

210
00:10:56,000 --> 00:10:59,000
De exemplu, ce se întâmplă atunci când ne construim un arbore binar de căutare

211
00:10:59,000 --> 00:11:01,000
dintr-o listă sortată de numere?

212
00:11:01,000 --> 00:11:04,000
Toate numerele sunt doar adaugă la dreapta la fiecare pas.

213
00:11:04,000 --> 00:11:06,000
Când ne-am dori pentru a căuta un număr,

214
00:11:06,000 --> 00:11:08,000
nu avem de ales, ci doar să se uite la dreapta, la fiecare pas.

215
00:11:08,000 --> 00:11:11,000
Acest lucru nu este mai bună decât căutarea liniară, la toate.

216
00:11:11,000 --> 00:11:13,000
Desi nu le vom acoperi aici, există și alte, mult mai complexe,

217
00:11:13,000 --> 00:11:16,000
structuri de date care fac sigur că acest lucru nu se întâmplă.

218
00:11:16,000 --> 00:11:18,000
Cu toate acestea, un lucru simplu care poate fi făcut pentru a evita acest lucru este

219
00:11:18,000 --> 00:11:21,000
la doar shuffle aleatoriu valorile de intrare.

220
00:11:21,000 --> 00:11:26,000
Este foarte puțin probabil ca prin întâmplare o listă de numere amestecate este sortat.

221
00:11:26,000 --> 00:11:29,000
Dacă acesta ar fi cazul, cazinourile nu ar rămâne în afaceri pentru mult timp.

222
00:11:29,000 --> 00:11:31,000
>> Nu-l ai.

223
00:11:31,000 --> 00:11:34,000
Acum știi despre căutarea binară și copaci de căutare binare.

224
00:11:34,000 --> 00:11:36,000
Sunt Patrick Schmid, iar acest lucru este CS50.

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

226
00:11:38,000 --> 00:11:43,000
Un mod evident ar fi de a scana lista de la ... [bip]

227
00:11:43,000 --> 00:11:46,000
... Numărul de articole ... yep

228
00:11:46,000 --> 00:11:50,000
[Râde]

229
00:11:50,000 --> 00:11:55,000
... Posta nod de 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Asta a fost -