1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary Search]

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

3
00:00:04,000 --> 00:00:07,000
[Dit is CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Als ik u een lijst met Disney-karakter namen in alfabetische volgorde

5
00:00:09,000 --> 00:00:11,000
en vroeg je om Mickey Mouse te vinden,

6
00:00:11,000 --> 00:00:13,000
hoe zou je dat doen?

7
00:00:13,000 --> 00:00:15,000
Een voor de hand liggende manier zou zijn om de lijst vanaf het begin te scannen

8
00:00:15,000 --> 00:00:18,000
en controleer elke naam om te zien of het is Mickey.

9
00:00:18,000 --> 00:00:22,000
Maar als je leest Aladdin, Alice, Ariel, enzovoort,

10
00:00:22,000 --> 00:00:25,000
je zult snel beseffen dat vanaf de voorzijde van de lijst niet een goed idee was.

11
00:00:25,000 --> 00:00:29,000
Oke, misschien moet je beginnen met werk hierbij vanaf het einde van de lijst.

12
00:00:29,000 --> 00:00:33,000
Nu lees je Tarzan, Stitch, Sneeuwwitje, enzovoort.

13
00:00:33,000 --> 00:00:36,000
Toch lijkt dit niet als de beste manier om te gaan over.

14
00:00:36,000 --> 00:00:38,000
>> Nou, nog een manier waarop je zou kunnen gaan over het doen van dit is om te proberen om een ​​beperking van

15
00:00:38,000 --> 00:00:41,000
de lijst met namen die je moet kijken.

16
00:00:41,000 --> 00:00:43,000
Omdat je weet dat ze in alfabetische volgorde,

17
00:00:43,000 --> 00:00:45,000
kon je gewoon kijkt naar de namen in het midden van de lijst

18
00:00:45,000 --> 00:00:49,000
en controleer of Mickey Mouse is voor of na deze naam.

19
00:00:49,000 --> 00:00:51,000
Kijkend naar de laatste naam in de tweede kolom

20
00:00:51,000 --> 00:00:54,000
je zou beseffen dat M voor Mickey komt na J voor Jasmine,

21
00:00:54,000 --> 00:00:57,000
dus je zou gewoon negeren de eerste helft van de lijst.

22
00:00:57,000 --> 00:00:59,000
Dan zou je waarschijnlijk kijken naar de top van de laatste kolom

23
00:00:59,000 --> 00:01:02,000
en zie dat het begint met Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey komt voor Rapunzel, lijkt erop dat we kunnen de laatste kolom negeren ook.

25
00:01:06,000 --> 00:01:08,000
Voortzetting van de zoekstrategie, zul je snel zien dat Mickey

26
00:01:08,000 --> 00:01:11,000
in de eerste helft van de resterende namenlijst

27
00:01:11,000 --> 00:01:14,000
en eindelijk Mickey verstopt tussen Merlijn en Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Wat je net deed was eigenlijk binaire zoekopdracht.

29
00:01:17,000 --> 00:01:22,000
Zoals deze naam al impliceert, zij haar zoeken strategie in een binaire kwestie.

30
00:01:22,000 --> 00:01:24,000
Wat betekent dit?

31
00:01:24,000 --> 00:01:27,000
Nou, gegeven een lijst met gesorteerde items, de binaire zoekalgoritme maakt een binaire beslissing -

32
00:01:27,000 --> 00:01:33,000
links of rechts, groter of kleiner dan, alfabetisch voor of na - op elk punt.

33
00:01:33,000 --> 00:01:35,000
Nu we een naam die gepaard gaat met deze zoekalgoritme te hebben,

34
00:01:35,000 --> 00:01:38,000
Laten we eens kijken naar een ander voorbeeld, maar dit keer met een lijst met gesorteerde nummers.

35
00:01:38,000 --> 00:01:43,000
Stel dat we op zoek zijn naar het nummer 144 in deze lijst van gesorteerd nummers.

36
00:01:43,000 --> 00:01:46,000
Net als vroeger, vinden we het getal dat is in het midden -

37
00:01:46,000 --> 00:01:50,000
in dit geval is 13 - 144 om te zien of groter of minder dan 13.

38
00:01:50,000 --> 00:01:54,000
Omdat het duidelijk groter dan 13, kunnen we negeren alles wat is 13 of minder

39
00:01:54,000 --> 00:01:57,000
en gewoon concentreren op de andere helft.

40
00:01:57,000 --> 00:01:59,000
Omdat we nu een even aantal items achtergelaten,

41
00:01:59,000 --> 00:02:01,000
we gewoon een nummer kiezen die dicht bij het midden.

42
00:02:01,000 --> 00:02:03,000
In dit geval kiezen we 55.

43
00:02:03,000 --> 00:02:06,000
We konden net zo goed hebben gekozen 89.

44
00:02:06,000 --> 00:02:11,000
Oke. Nogmaals, 144 groter is dan 55, dus we gaan naar rechts.

45
00:02:11,000 --> 00:02:14,000
Gelukkig voor ons, de volgende middelste getal is 144,

46
00:02:14,000 --> 00:02:16,000
degene die we zoeken.

47
00:02:16,000 --> 00:02:21,000
Dus om 144 vinden met behulp van een binair zoeken, zijn we in staat om het te vinden in slechts 3 stappen.

48
00:02:21,000 --> 00:02:24,000
Als we gebruik hebben gemaakt van lineair zoeken hier, zou het hebben genomen ons 12 stappen.

49
00:02:24,000 --> 00:02:28,000
In feite, aangezien deze zoekmethode halveert het aantal items

50
00:02:28,000 --> 00:02:31,000
het moet kijken bij elke stap zal vinden het produkt dat zoekt

51
00:02:31,000 --> 00:02:35,000
in ongeveer de log van het aantal items in de lijst.

52
00:02:35,000 --> 00:02:37,000
Nu we 2 voorbeelden gezien, laten we eens een kijkje op

53
00:02:37,000 --> 00:02:41,000
wat pseudocode voor een recursieve functie die binaire zoekopdracht implementeert.

54
00:02:41,000 --> 00:02:44,000
Begin bij de bovenkant, zien we dat we een functie die 4 argumenten neemt te vinden:

55
00:02:44,000 --> 00:02:47,000
sleutel, array, min en max.

56
00:02:47,000 --> 00:02:51,000
De sleutel is het nummer dat we op zoek zijn naar, dus 144 in het vorige voorbeeld.

57
00:02:51,000 --> 00:02:54,000
Matrix is ​​de lijst met nummers die we zoeken.

58
00:02:54,000 --> 00:02:57,000
Min en max zijn de indices van de minimale en maximale posities

59
00:02:57,000 --> 00:02:59,000
dat we momenteel op zoek naar.

60
00:02:59,000 --> 00:03:03,000
Dus als we beginnen, zullen min nul en max is de maximale index van de array.

61
00:03:03,000 --> 00:03:07,000
Als we de zoekopdracht naar beneden, zullen we een update van min en max

62
00:03:07,000 --> 00:03:10,000
om alleen het assortiment dat we nog steeds op zoek zijn naar binnen worden

63
00:03:10,000 --> 00:03:12,000
>> Laten we eerst naar het interessante deel.

64
00:03:12,000 --> 00:03:14,000
Het eerste wat we doen is het vinden het middelpunt,

65
00:03:14,000 --> 00:03:19,000
de index die is halverwege tussen de min en max van de array dat we nog overwegen.

66
00:03:19,000 --> 00:03:22,000
Vervolgens kijken we naar de waarde van de array op dat punt locatie

67
00:03:22,000 --> 00:03:25,000
en kijk of het nummer dat we op zoek zijn naar minder dan die toets.

68
00:03:25,000 --> 00:03:27,000
Als het aantal op die positie minder,

69
00:03:27,000 --> 00:03:31,000
dan betekent de sleutel groter is dan alle getallen links van die positie.

70
00:03:31,000 --> 00:03:33,000
Dus we kunnen noemen binaire zoekfunctie weer,

71
00:03:33,000 --> 00:03:36,000
maar deze keer het bijwerken van de min. en max. parameters om enkel de helft gelezen

72
00:03:36,000 --> 00:03:40,000
die groter dan of gelijk aan de waarde die we keek.

73
00:03:40,000 --> 00:03:44,000
Anderzijds, als de sleutel dan het aantal in de huidige midden van de array,

74
00:03:44,000 --> 00:03:47,000
we willen gaan naar links en alle nummers die groter zijn negeren.

75
00:03:47,000 --> 00:03:52,000
Nogmaals, we noemen binair zoeken, maar dit keer met het bereik van de min en max updated

76
00:03:52,000 --> 00:03:54,000
alleen de onderste helft omvat.

77
00:03:54,000 --> 00:03:57,000
Als de waarde op de huidige midden in de array noch

78
00:03:57,000 --> 00:04:01,000
groter dan of kleiner dan de sleutel, dan moet gelijk zijn aan de sleutel.

79
00:04:01,000 --> 00:04:05,000
Zo kunnen we gewoon terug de huidige midden-index, en we zijn klaar.

80
00:04:05,000 --> 00:04:09,000
Tenslotte, deze controle is hier voor het geval dat het aantal

81
00:04:09,000 --> 00:04:11,000
is eigenlijk niet in de array van getallen zijn we op zoek.

82
00:04:11,000 --> 00:04:14,000
Als de maximale index van het bereik dat we op zoek zijn naar

83
00:04:14,000 --> 00:04:17,000
is altijd minder dan het minimum, dat betekent dat we zijn te ver gegaan.

84
00:04:17,000 --> 00:04:20,000
Omdat het aantal was niet in de input array, we -1 terug

85
00:04:20,000 --> 00:04:24,000
dat niets dan gevonden.

86
00:04:24,000 --> 00:04:26,000
>> Je hebt misschien gemerkt dat het voor dit algoritme te laten werken,

87
00:04:26,000 --> 00:04:28,000
de lijst met nummers moet worden gesorteerd.

88
00:04:28,000 --> 00:04:31,000
Met andere woorden, kunnen we alleen maar vinden 144 met behulp van binaire zoekopdracht

89
00:04:31,000 --> 00:04:34,000
Als alle nummers zijn gerangschikt van laag naar hoog.

90
00:04:34,000 --> 00:04:38,000
Als dit niet het geval is, zouden we niet in staat zijn om de helft van de nummers te sluiten bij elke stap.

91
00:04:38,000 --> 00:04:40,000
Dus we hebben 2 opties.

92
00:04:40,000 --> 00:04:43,000
Of we kunnen een ongesorteerde lijst en sorteren voordat u binary search,

93
00:04:43,000 --> 00:04:48,000
of we kunnen ervoor zorgen dat de lijst met nummers wordt gesorteerd als we nummers aan toe te voegen.

94
00:04:48,000 --> 00:04:50,000
Dus in plaats van sorteren net toen we moeten zoeken,

95
00:04:50,000 --> 00:04:53,000
waarom niet houden van de lijst gesorteerd op elk moment?

96
00:04:53,000 --> 00:04:57,000
>> Een manier om een ​​lijst met nummers houden gesorteerd en tegelijkertijd toestaan

97
00:04:57,000 --> 00:04:59,000
een toe te voegen of nummers te verplaatsen van de lijst

98
00:04:59,000 --> 00:05:02,000
is met behulp van een zogenaamde binaire zoekboom.

99
00:05:02,000 --> 00:05:05,000
Een binaire zoekboom is een datastructuur die 3 eigenschappen heeft.

100
00:05:05,000 --> 00:05:09,000
Enerzijds de linker deelboom van elke node alleen waarden die kleiner zijn dan

101
00:05:09,000 --> 00:05:11,000
of gelijk is aan de waarde van de node.

102
00:05:11,000 --> 00:05:15,000
Ten tweede, de rechter deelboom van een knooppunt bevat alleen waarden die groter zijn dan

103
00:05:15,000 --> 00:05:17,000
of gelijk is aan de waarde van de node.

104
00:05:17,000 --> 00:05:20,000
En tenslotte de linker en rechter subbomen van alle knooppunten

105
00:05:20,000 --> 00:05:23,000
zijn ook binaire zoekbomen.

106
00:05:23,000 --> 00:05:26,000
Laten we eens kijken naar een voorbeeld met dezelfde nummers die we eerder gebruikt.

107
00:05:26,000 --> 00:05:30,000
Voor degenen onder u die nog nooit een computer science boom eerder gezien,

108
00:05:30,000 --> 00:05:34,000
laat ik beginnen met te vertellen dat een computer science boom naar beneden groeit.

109
00:05:34,000 --> 00:05:36,000
Ja, in tegenstelling tot bomen u gewend bent,

110
00:05:36,000 --> 00:05:38,000
de wortel van een informatica boom bovenaan

111
00:05:38,000 --> 00:05:41,000
en de bladeren staan ​​onderaan.

112
00:05:41,000 --> 00:05:45,000
Elk doosje wordt een knooppunt en de knooppunten met elkaar verbonden door randen.

113
00:05:45,000 --> 00:05:48,000
Dus de wortel van deze boom is een knooppunt waarde met de waarde 13,

114
00:05:48,000 --> 00:05:52,000
die heeft 2 kinderen nodes met de waarden 5 en 34.

115
00:05:52,000 --> 00:05:57,000
Een substructuur is de boom die wordt gevormd door gewoon te kijken naar een onderafdeling van de gehele boom.

116
00:05:57,000 --> 00:06:03,000
>> Bijvoorbeeld de linker deelboom van het knooppunt 3 is de boom die door de knooppunten 0, 1 en 2.

117
00:06:03,000 --> 00:06:06,000
Dus, als we terug gaan naar de eigenschappen van een binaire zoekboom,

118
00:06:06,000 --> 00:06:09,000
we zien dat elke knoop in de boom voldoet aan alle drie eigenschappen, namelijk

119
00:06:09,000 --> 00:06:15,000
de linker deelboom bevat alleen waarden die minder dan of gelijk aan de waarde van het knooppunt;

120
00:06:15,000 --> 00:06:16,000
de rechter deelboom van alle knooppunten

121
00:06:16,000 --> 00:06:19,000
Alleen bevat waarden die groter dan of gelijk aan de waarde van het knooppunt, en

122
00:06:19,000 --> 00:06:25,000
zowel links als rechts substructuren van alle knooppunten zijn ook binaire zoekbomen.

123
00:06:25,000 --> 00:06:28,000
Hoewel deze boom er anders, dit een geldig binaire zoekboom

124
00:06:28,000 --> 00:06:30,000
voor dezelfde reeks getallen.

125
00:06:30,000 --> 00:06:32,000
In feite zijn er vele mogelijke manieren waarop u kunt

126
00:06:32,000 --> 00:06:35,000
een geldige binaire zoekboom van deze nummers.

127
00:06:35,000 --> 00:06:38,000
Nou, laten we terug gaan naar de eerste die we gemaakt.

128
00:06:38,000 --> 00:06:40,000
Dus wat kunnen we doen met deze bomen?

129
00:06:40,000 --> 00:06:44,000
Nou, we kunnen heel gewoon vinden de minimale en maximale waarden.

130
00:06:44,000 --> 00:06:46,000
De minimumwaarden kan worden gevonden door altijd naar links

131
00:06:46,000 --> 00:06:48,000
totdat er geen meer knooppunten te bezoeken.

132
00:06:48,000 --> 00:06:53,000
Omgekeerd, het vinden van de maximum een ​​simpelweg naar beneden gaat naar rechts op elk tijdstip.

133
00:06:54,000 --> 00:06:56,000
>> Het vinden van een ander nummer dat niet het minimale of de maximale

134
00:06:56,000 --> 00:06:58,000
is net zo gemakkelijk.

135
00:06:58,000 --> 00:07:00,000
Zeggen dat we op zoek naar het nummer 89.

136
00:07:00,000 --> 00:07:03,000
We hebben gewoon controleren van de waarde van elk knooppunt en ga naar links of rechts,

137
00:07:03,000 --> 00:07:06,000
naargelang het knooppunt waarde kleiner is dan of groter dan

138
00:07:06,000 --> 00:07:08,000
degene die we zoeken.

139
00:07:08,000 --> 00:07:11,000
Dus vanaf de wortel van 13 zien we dat 89 groter is,

140
00:07:11,000 --> 00:07:13,000
en dus gaan we naar rechts.

141
00:07:13,000 --> 00:07:16,000
Dan zien we het knooppunt voor 34, en weer gaan we naar rechts.

142
00:07:16,000 --> 00:07:20,000
89 nog steeds groter is dan 55, dus we blijven gaan naar rechts.

143
00:07:20,000 --> 00:07:24,000
Vervolgens komen met een knooppunt met de waarde van 144 en naar links.

144
00:07:24,000 --> 00:07:26,000
Lo en zie, 89 is daar.

145
00:07:26,000 --> 00:07:31,000
>> Een ander ding dat we kunnen doen is uit te printen alle nummers door het uitvoeren van een inorder traversal.

146
00:07:31,000 --> 00:07:35,000
Een inorder traversal betekent om alles af te drukken in de linker deelboom

147
00:07:35,000 --> 00:07:37,000
gevolgd door de knoop zelf drukken

148
00:07:37,000 --> 00:07:40,000
en dan gevolgd door bedrukken alles in de rechter deelboom.

149
00:07:40,000 --> 00:07:43,000
Bijvoorbeeld, laten we onze favoriete binaire zoekboom

150
00:07:43,000 --> 00:07:46,000
en print de nummers in gesorteerde volgorde.

151
00:07:46,000 --> 00:07:49,000
We beginnen bij de wortel van 13, maar voordat u gaat afdrukken 13 moeten we uit te printen

152
00:07:49,000 --> 00:07:51,000
alles in de linker deelboom.

153
00:07:51,000 --> 00:07:55,000
Dus gaan we naar 5. We moeten nog dieper naar beneden gaan in de boom totdat we de meest linkse knooppunt,

154
00:07:55,000 --> 00:07:57,000
dat nul is.

155
00:07:57,000 --> 00:08:00,000
Na het afdrukken nul, gaan we terug naar de 1 en af ​​te drukken dat uit.

156
00:08:00,000 --> 00:08:03,000
Dan gaan we naar de rechter deelboom, dat is 2, en af ​​te drukken dat uit.

157
00:08:03,000 --> 00:08:05,000
Nu we klaar zijn met die substructuur,

158
00:08:05,000 --> 00:08:07,000
kunnen we terug te gaan naar de 3 en print het uit.

159
00:08:07,000 --> 00:08:11,000
Voortzetting van een back-up is een afdruk van de 5 en dan de 8.

160
00:08:11,000 --> 00:08:13,000
Nu we de hele afgerond linker deelboom,

161
00:08:13,000 --> 00:08:17,000
Wij kunnen de 13 en gaan werken aan de rechter deelboom.

162
00:08:17,000 --> 00:08:21,000
We springen naar 34, maar voordat u gaat afdrukken 34 moeten we uit te printen zijn linker deelboom.

163
00:08:21,000 --> 00:08:27,000
Dus we afdrukken 21; dan krijgen we te printen 34 en de rechter deelboom te bezoeken.

164
00:08:27,000 --> 00:08:31,000
Omdat 55 heeft geen linker deelboom, drukken we het uit en verder naar de rechter deelboom.

165
00:08:31,000 --> 00:08:36,000
144 heeft een linker deelboom, en dus de 89 afdrukken, gevolgd door 144,

166
00:08:36,000 --> 00:08:39,000
en tenslotte de meest rechtse node 233.

167
00:08:39,000 --> 00:08:44,000
Daar heb je het, alle nummers zijn afgedrukt in de volgorde van laag naar hoog.

168
00:08:44,000 --> 00:08:47,000
>> Het toevoegen van iets aan de boom is relatief pijnloos ook.

169
00:08:47,000 --> 00:08:51,000
Het enige wat we hoeven te doen is ervoor te zorgen dat we 3 binaire zoekboom eigenschappen te volgen

170
00:08:51,000 --> 00:08:53,000
en steek vervolgens de waarde waar ruimte is.

171
00:08:53,000 --> 00:08:55,000
Laten we zeggen dat we de waarde van 7 in te voegen.

172
00:08:55,000 --> 00:08:58,000
Sinds 7 is minder dan 13, gaan we naar links.

173
00:08:58,000 --> 00:09:01,000
Maar het is groter dan 5, dus beweeg naar rechts.

174
00:09:01,000 --> 00:09:04,000
Omdat het minder dan 8 en 8 een eindknooppunt voegen wij 7 naar links kind van 8.

175
00:09:04,000 --> 00:09:09,000
Voila! We hebben een aantal van onze binaire zoekboom.

176
00:09:09,000 --> 00:09:12,000
>> Als we kunnen toevoegen dingen, we beter in staat zijn om dingen te verwijderen ook.

177
00:09:12,000 --> 00:09:14,000
Helaas voor ons, het verwijderen is een beetje ingewikkelder -

178
00:09:14,000 --> 00:09:16,000
niet veel, maar slechts een klein beetje.

179
00:09:16,000 --> 00:09:18,000
Er zijn 3 verschillende scenario's die we moeten overwegen

180
00:09:18,000 --> 00:09:21,000
bij het verwijderen van elementen uit binaire zoekbomen.

181
00:09:21,000 --> 00:09:24,000
Eerste, het eenvoudigste geval is dat het element een eindknooppunt.

182
00:09:24,000 --> 00:09:27,000
In dit geval hebben we gewoon verwijderen en verder gaan met ons bedrijf.

183
00:09:27,000 --> 00:09:30,000
Stel dat we willen de 7 die we net toegevoegd te verwijderen.

184
00:09:30,000 --> 00:09:34,000
Nou ja, gewoon wij het vinden, neem hem uit en dat is het.

185
00:09:35,000 --> 00:09:37,000
De volgende zaak is wanneer de node heeft slechts 1 kind.

186
00:09:37,000 --> 00:09:40,000
Hier kunnen we verwijderen van het knooppunt, maar moeten we eerst zorgen dat

187
00:09:40,000 --> 00:09:42,000
om de substructuur die nu ouderloos overblijft aansluiten

188
00:09:42,000 --> 00:09:44,000
aan de ouder van het knooppunt we gewoon verwijderd.

189
00:09:44,000 --> 00:09:47,000
Stel dat we willen 3 verwijderen uit onze boom.

190
00:09:47,000 --> 00:09:50,000
We nemen de onderliggend element van die knoop en voeg het bij de ouder van het knooppunt.

191
00:09:50,000 --> 00:09:54,000
In dit geval worden momenteel bevestigen van de een naar de 5.

192
00:09:54,000 --> 00:09:57,000
Dit werkt zonder problemen omdat we weten volgens het binaire zoekboom bezit,

193
00:09:57,000 --> 00:10:01,000
dat alles in de linker deelboom van 3 minder dan 5.

194
00:10:01,000 --> 00:10:05,000
Nu 3's substructuur wordt verzorgd, kunnen we verwijderen.

195
00:10:05,000 --> 00:10:08,000
De derde en laatste geval is het meest complex.

196
00:10:08,000 --> 00:10:11,000
Dit is het geval wanneer het knooppunt we willen verwijderen heeft 2 kinderen.

197
00:10:11,000 --> 00:10:15,000
Om dit te doen, moeten we eerst het knooppunt dat de volgende grootste waarde te vinden,

198
00:10:15,000 --> 00:10:18,000
swap de twee en verwijder het knooppunt in kwestie.

199
00:10:18,000 --> 00:10:22,000
Let op het knooppunt dat is de volgende grootste waarde kan geen 2 kinderen zelf

200
00:10:22,000 --> 00:10:26,000
sinds de linker kind zou een betere kandidaat voor de op een na grootste is.

201
00:10:26,000 --> 00:10:30,000
Daarom verwijderen van een knooppunt 2 kinderen bedraagt ​​wisselen van twee knooppunten,

202
00:10:30,000 --> 00:10:33,000
en dan te verwijderen wordt afgehandeld door 1 van de 2 voornoemde regels.

203
00:10:33,000 --> 00:10:37,000
Bijvoorbeeld, laten we zeggen dat we willen de root node, 13 verwijderen.

204
00:10:37,000 --> 00:10:39,000
Het eerste wat we doen is vinden we de volgende grootste waarde in de boom

205
00:10:39,000 --> 00:10:41,000
die in dit geval is 21.

206
00:10:41,000 --> 00:10:46,000
Vervolgens hebben we ruilen de 2 knopen, het maken van 13 een blad en 21 van de centrale groep knooppunt.

207
00:10:46,000 --> 00:10:49,000
Nu kunnen we gewoon verwijderen 13.

208
00:10:50,000 --> 00:10:53,000
>> Zoals eerder gezinspeeld, zijn er vele manieren om een ​​geldige binaire zoekboom maken.

209
00:10:53,000 --> 00:10:56,000
Helaas voor ons, sommige zijn erger dan anderen.

210
00:10:56,000 --> 00:10:59,000
Bijvoorbeeld, wat er gebeurt als we een binaire zoekboom

211
00:10:59,000 --> 00:11:01,000
uit een gesorteerde lijst van nummers?

212
00:11:01,000 --> 00:11:04,000
Alle nummers zijn gewoon toegevoegd aan de juiste bij elke stap.

213
00:11:04,000 --> 00:11:06,000
Wanneer we willen zoeken naar een aantal,

214
00:11:06,000 --> 00:11:08,000
We hebben geen andere keuze dan alleen aan op de juiste kijken bij elke stap.

215
00:11:08,000 --> 00:11:11,000
Dit is niet beter dan lineair zoeken op alle.

216
00:11:11,000 --> 00:11:13,000
Hoewel we hier niet bedek ze, zijn er andere, meer complexe,

217
00:11:13,000 --> 00:11:16,000
datastructuren die ervoor zorgen dat dit niet gebeurt.

218
00:11:16,000 --> 00:11:18,000
Echter, een simpel ding dat kan worden gedaan om dit te voorkomen is

219
00:11:18,000 --> 00:11:21,000
om gewoon willekeurig shuffle de ingevoerde waarden.

220
00:11:21,000 --> 00:11:26,000
Het is zeer onwaarschijnlijk dat bij toeval een geschud lijst met nummers gesorteerd.

221
00:11:26,000 --> 00:11:29,000
Als dit het geval is, zou casino's niet blijven in het bedrijfsleven voor lang.

222
00:11:29,000 --> 00:11:31,000
>> Daar heb je het.

223
00:11:31,000 --> 00:11:34,000
Je weet nu over binair zoeken en binaire zoekbomen.

224
00:11:34,000 --> 00:11:36,000
Ik ben Patrick Schmid, en dit is CS50.

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

226
00:11:38,000 --> 00:11:43,000
Een voor de hand liggende manier zou zijn om de lijst te scannen van ... [piep]

227
00:11:43,000 --> 00:11:46,000
... Het aantal items ... yep

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

229
00:11:50,000 --> 00:11:55,000
... Na knooppunt van 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Dat was -