1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary Keresés]

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

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

4
00:00:07,000 --> 00:00:09,000
>> Ha én adtam neked egy listát a Disney karakter nevek betűrendben

5
00:00:09,000 --> 00:00:11,000
és arra kérte, hogy megtalálja Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
hogyan megy a csinálod ezt?

7
00:00:13,000 --> 00:00:15,000
Az egyik kézenfekvő módja az lenne, hogy megvizsgálja a lista elején

8
00:00:15,000 --> 00:00:18,000
és ellenőrizze, minden nevet, hogy ha ez a Mickey.

9
00:00:18,000 --> 00:00:22,000
De ahogy olvasol Aladdin, Alice, Ariel, és így tovább,

10
00:00:22,000 --> 00:00:25,000
akkor hamar rájön, hogy az indítást elején a lista nem volt jó ötlet.

11
00:00:25,000 --> 00:00:29,000
Oké, lehet, hogy meg kell kezdeni visszafelé haladva az a lista végére.

12
00:00:29,000 --> 00:00:33,000
Most olvas Tarzan, Stitch, Hófehérke, és így tovább.

13
00:00:33,000 --> 00:00:36,000
Mégis, ez nem tűnik a legjobb módja, hogy menjen vele.

14
00:00:36,000 --> 00:00:38,000
>> Nos, egy másik módja, hogy meg tudná járni ezt az, hogy megpróbálja leszűkítheti

15
00:00:38,000 --> 00:00:41,000
a neveket, hogy meg kell nézni.

16
00:00:41,000 --> 00:00:43,000
Mivel tudja, hogy ABC sorrendben,

17
00:00:43,000 --> 00:00:45,000
akkor csak nézd meg a nevét a közepén a lista

18
00:00:45,000 --> 00:00:49,000
és ellenőrizze, hogy Mickey egér előtt vagy után ezt a nevet.

19
00:00:49,000 --> 00:00:51,000
Keresi az utolsó név a második oszlopban

20
00:00:51,000 --> 00:00:54,000
azt észre, hogy M Mickey után jön J Jasmine,

21
00:00:54,000 --> 00:00:57,000
így azt egyszerűen figyelmen kívül hagyja az első felében a listán.

22
00:00:57,000 --> 00:00:59,000
Akkor lenne talán nézd meg a tetején az utolsó oszlop

23
00:00:59,000 --> 00:01:02,000
és nézd meg, hogy kezdődik Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey előbb Rapunzel, úgy néz ki, mint tudjuk figyelmen kívül hagyni az utolsó oszlop is.

25
00:01:06,000 --> 00:01:08,000
Folytatva a keresési stratégiát, akkor gyorsan látni, hogy Mickey

26
00:01:08,000 --> 00:01:11,000
az első felében a fennmaradó nevek listáját

27
00:01:11,000 --> 00:01:14,000
és végül megtalálni Mickey bujkál között Merlin és Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Amit most tett, az tulajdonképpen a bináris keresés.

29
00:01:17,000 --> 00:01:22,000
Mivel ez a neve is mutatja, ez végzi keresés stratégiáját bináris kérdésben.

30
00:01:22,000 --> 00:01:24,000
Mit jelent ez?

31
00:01:24,000 --> 00:01:27,000
Nos, adott egy listát rendezett tárgyakat, a bináris keresés algoritmus teszi a bináris döntés -

32
00:01:27,000 --> 00:01:33,000
balra vagy jobbra, nagyobb vagy kisebb, mint betűrendben előtt vagy után - minden ponton.

33
00:01:33,000 --> 00:01:35,000
Most, hogy van egy név, amely együtt jár a keresést algoritmus,

34
00:01:35,000 --> 00:01:38,000
nézzük egy másik példát, de ezúttal egy listát a számok sorrendje.

35
00:01:38,000 --> 00:01:43,000
Mondja keresünk számát 144-ben ezt a listát a rendezett számok.

36
00:01:43,000 --> 00:01:46,000
Csakúgy, mint korábban, azt látjuk, hogy ez a szám a középső -

37
00:01:46,000 --> 00:01:50,000
amely ebben az esetben 13 -, és ha 144-nél nagyobb vagy kisebb mint 13.

38
00:01:50,000 --> 00:01:54,000
Mivel ez nyilvánvalóan nagyobb, mint 13, akkor figyelmen kívül mindent, ami 13 vagy kevesebb

39
00:01:54,000 --> 00:01:57,000
és csak koncentrálni a másik felét.

40
00:01:57,000 --> 00:01:59,000
Mivel most már páros számú tétel maradt,

41
00:01:59,000 --> 00:02:01,000
egyszerűen válassza ki a számot, amely közel áll a közepén.

42
00:02:01,000 --> 00:02:03,000
Ebben az esetben válassza a 55.

43
00:02:03,000 --> 00:02:06,000
Mi volna éppen olyan könnyen választott 89.

44
00:02:06,000 --> 00:02:11,000
Oké. Ismét, 144 nagyobb, mint 55, így megy a jobbra.

45
00:02:11,000 --> 00:02:14,000
Szerencsénkre, a következő középső szám 144,

46
00:02:14,000 --> 00:02:16,000
az, amit keresünk.

47
00:02:16,000 --> 00:02:21,000
Így annak érdekében, hogy megtalálják 144 egy bináris keresés, képesek vagyunk megtalálni mindössze 3 lépésben.

48
00:02:21,000 --> 00:02:24,000
Ha használta volna a lineáris keresést itt, akkor volna minket 12 lépésben.

49
00:02:24,000 --> 00:02:28,000
Ami azt illeti, mivel ez a keresési mód felezi a tételek száma

50
00:02:28,000 --> 00:02:31,000
azt, hogy nézd meg minden lépésben, akkor megtalálja a tételt, hogy keres

51
00:02:31,000 --> 00:02:35,000
körülbelül a naplót a tételek számát a listában.

52
00:02:35,000 --> 00:02:37,000
Most, hogy láttuk 2 példa, vessünk egy pillantást

53
00:02:37,000 --> 00:02:41,000
Néhány pszeudokód egy rekurzív függvény, amely megvalósítja a bináris keresés.

54
00:02:41,000 --> 00:02:44,000
Kezdve a tetején, azt látjuk, hogy meg kell találni egy függvényt, amely úgy 4 érvek:

55
00:02:44,000 --> 00:02:47,000
gombot, tömb, min és max.

56
00:02:47,000 --> 00:02:51,000
A legfontosabb az a szám, amelyet keresünk, ezért 144-ben az előző példában.

57
00:02:51,000 --> 00:02:54,000
Array a lista a számokat keresünk.

58
00:02:54,000 --> 00:02:57,000
Min és max a mutatók minimális és maximális pozíciók

59
00:02:57,000 --> 00:02:59,000
hogy jelenleg nézi.

60
00:02:59,000 --> 00:03:03,000
Szóval mikor kezdünk, min nulla lesz és max lesz a legnagyobb index a tömb.

61
00:03:03,000 --> 00:03:07,000
Ahogy szűkíteni a keresést, akkor frissíteni min és max

62
00:03:07,000 --> 00:03:10,000
hogy csak a tartomány, hogy mi még mindig keresi be

63
00:03:10,000 --> 00:03:12,000
>> Nézzük ugrás az érdekes rész első.

64
00:03:12,000 --> 00:03:14,000
Az első dolog, amit tennie, hogy megtalálja a középpont,

65
00:03:14,000 --> 00:03:19,000
az index, amely félúton a min és max értéke a tömb, hogy mi továbbra is vizsgálja.

66
00:03:19,000 --> 00:03:22,000
Akkor nézzük az érték a tömb az adott középponti helyen

67
00:03:22,000 --> 00:03:25,000
és nézd meg azt a számot, keresünk kisebb, mint hogy a kulcsot.

68
00:03:25,000 --> 00:03:27,000
Ha a szám ebben a pozícióban a kisebb,

69
00:03:27,000 --> 00:03:31,000
akkor ez azt jelenti, a legfontosabb az, nagyobb, mint az összes számot a bal oldalon ez az álláspont.

70
00:03:31,000 --> 00:03:33,000
Így tudjuk hívni a bináris keresési funkció újra,

71
00:03:33,000 --> 00:03:36,000
de ezúttal frissítésével min és max paraméterek olvasni, csak a felét

72
00:03:36,000 --> 00:03:40,000
amely nagyobb vagy egyenlő, mint az értéket adunk csak nézett.

73
00:03:40,000 --> 00:03:44,000
Másrészről, ha a kulcs kisebb, mint a szám az aktuális felezőpontja a tömb,

74
00:03:44,000 --> 00:03:47,000
akarunk menni a balra és figyelmen kívül hagyja az összes számot, amely nagyobb.

75
00:03:47,000 --> 00:03:52,000
Ismét hívjuk bináris keresés, de ezúttal tartomány min és max updated

76
00:03:52,000 --> 00:03:54,000
fel, csak az alsó felét.

77
00:03:54,000 --> 00:03:57,000
Ha az érték az aktuális felezőpontjában a tömbben sem

78
00:03:57,000 --> 00:04:01,000
nagyobb, sem kisebb, mint a kulcs, akkor meg kell egyeznie a kulcsot.

79
00:04:01,000 --> 00:04:05,000
Így, akkor egyszerűen vissza a jelenlegi felezőpontja index, és készen vagyunk.

80
00:04:05,000 --> 00:04:09,000
Végül, ez a csekk itt Az a helyzet, hogy a szám

81
00:04:09,000 --> 00:04:11,000
valójában nem a tömbben lévő számok keresünk.

82
00:04:11,000 --> 00:04:14,000
Ha a legnagyobb index a tartomány, hogy keresünk

83
00:04:14,000 --> 00:04:17,000
örökké kisebb, mint a minimum, ami azt jelenti, hogy már túl messzire ment.

84
00:04:17,000 --> 00:04:20,000
Mivel a szám nem volt az input tömb, akkor vissza -1

85
00:04:20,000 --> 00:04:24,000
annak jelzésére, hogy semmit sem találtak.

86
00:04:24,000 --> 00:04:26,000
>> Lehet, hogy észrevette, hogy ezen algoritmus működik,

87
00:04:26,000 --> 00:04:28,000
A számok listája kell válogatni.

88
00:04:28,000 --> 00:04:31,000
Más szóval, csak akkor tudjuk találni 144 bináris keresés

89
00:04:31,000 --> 00:04:34,000
ha minden a számokat a megrendelt legalacsonyabbtól a legmagasabb.

90
00:04:34,000 --> 00:04:38,000
Ha ez nem így lenne, akkor nem lenne képes kizárni felét a számok az egyes lépésekben.

91
00:04:38,000 --> 00:04:40,000
Tehát van 2 lehetőség.

92
00:04:40,000 --> 00:04:43,000
Vagy vehetjük a szétválogatott listát, és rendezheti előtt bináris keresés,

93
00:04:43,000 --> 00:04:48,000
vagy mi lehet benne, hogy a lista a számok sorrendje, ahogy hozzá számokat is.

94
00:04:48,000 --> 00:04:50,000
Így ahelyett, hogy válogatás csak amikor meg kell keresni,

95
00:04:50,000 --> 00:04:53,000
miért nem tartja a lista sorrendje minden alkalommal?

96
00:04:53,000 --> 00:04:57,000
>> Az egyik módja annak, hogy egy listát a számok sorrendje miközben lehetővé

97
00:04:57,000 --> 00:04:59,000
1 hozzáadásához vagy áthelyezni a telefonszámokat a listából

98
00:04:59,000 --> 00:05:02,000
a segítségével egy úgynevezett bináris kereső fa.

99
00:05:02,000 --> 00:05:05,000
A bináris kereső fa olyan adatszerkezet, amely 3 tulajdonságait.

100
00:05:05,000 --> 00:05:09,000
Először is, a bal részfájának bármely csomópont tartalmaz, csak olyan értékekre, amelyek kevesebb, mint

101
00:05:09,000 --> 00:05:11,000
vagy egyenlő a csomópont értékét.

102
00:05:11,000 --> 00:05:15,000
Másodszor, a jobb részfájának egy csomópont csak értékeket tartalmaz, amelyek-nél nagyobb

103
00:05:15,000 --> 00:05:17,000
vagy egyenlő a csomópont értékét.

104
00:05:17,000 --> 00:05:20,000
És végül, a bal és jobb részfákat az összes csomópont

105
00:05:20,000 --> 00:05:23,000
szintén bináris keresés fák.

106
00:05:23,000 --> 00:05:26,000
Nézzünk egy példát az azonos számokat használtunk korábban.

107
00:05:26,000 --> 00:05:30,000
Azok számára, akik még soha nem látott a számítógép-tudomány fa előtt,

108
00:05:30,000 --> 00:05:34,000
Hadd kezdjem azzal, amely jelzi, hogy a számítógép-tudomány fa nő lefelé.

109
00:05:34,000 --> 00:05:36,000
Igen, ellentétben a fák akkor szokott,

110
00:05:36,000 --> 00:05:38,000
gyökere a számítógép-tudomány fa van a tetején,

111
00:05:38,000 --> 00:05:41,000
és a levelek alján.

112
00:05:41,000 --> 00:05:45,000
Minden egyes kis doboz hívják csomópont, és a csomópontok kapcsolódnak egymáshoz élek.

113
00:05:45,000 --> 00:05:48,000
Tehát a gyökere ennek a fának van egy csomópont érték az érték 13,

114
00:05:48,000 --> 00:05:52,000
amely 2 gyermek csomópontok az értékek 5 és 34.

115
00:05:52,000 --> 00:05:57,000
A részfa az a fa, van kialakítva ránézésre egy alfejezetet az egész fa.

116
00:05:57,000 --> 00:06:03,000
>> Így például, a bal részfájának a 3 csomópont a fa által létrehozott csomópontok 0, 1, és 2.

117
00:06:03,000 --> 00:06:06,000
Tehát, ha visszamegyünk a tulajdonságait egy bináris keresési fa,

118
00:06:06,000 --> 00:06:09,000
azt látjuk, hogy minden csomópont a fában megfelel mind a 3 tulajdonságok, nevezetesen,

119
00:06:09,000 --> 00:06:15,000
a bal oldali részfa egyetlen értékeket tartalmaz, amelyek kisebb vagy egyenlő, mint a csomópont értékét;

120
00:06:15,000 --> 00:06:16,000
a jobb részfa összes csomópont

121
00:06:16,000 --> 00:06:19,000
csak azokat, amelyek értéke nagyobb, vagy egyenlő, mint a csomópont értékét, és

122
00:06:19,000 --> 00:06:25,000
mind a bal és jobb oldali részfa összes csomópont is vannak bináris keresési fák.

123
00:06:25,000 --> 00:06:28,000
Bár ez a fa másképp néz ki, ez egy érvényes bináris keresési fa

124
00:06:28,000 --> 00:06:30,000
számára ugyanazokat a számokat.

125
00:06:30,000 --> 00:06:32,000
Ami azt illeti, sok lehetséges módon lehet létrehozni

126
00:06:32,000 --> 00:06:35,000
érvényes bináris keresési fa ezeket a számokat.

127
00:06:35,000 --> 00:06:38,000
Nos, menjünk vissza az első hoztunk létre.

128
00:06:38,000 --> 00:06:40,000
Szóval mit tehetünk ezekkel a fák?

129
00:06:40,000 --> 00:06:44,000
Nos, akkor nagyon egyszerűen megtalálja a minimum és maximum értékek.

130
00:06:44,000 --> 00:06:46,000
A minimum értékek is talált mindig megy a bal

131
00:06:46,000 --> 00:06:48,000
amíg nincs több csomópont meglátogatni.

132
00:06:48,000 --> 00:06:53,000
Ezzel, hogy megtalálják a legnagyobb ember egyszerűen csak megy lefelé a jogot minden alkalommal.

133
00:06:54,000 --> 00:06:56,000
>> Finding bármely másik szám, amely nem a legkisebb, illetve a maximális

134
00:06:56,000 --> 00:06:58,000
éppen olyan egyszerű.

135
00:06:58,000 --> 00:07:00,000
Mondja keresünk a szám 89.

136
00:07:00,000 --> 00:07:03,000
Egyszerűen ellenőrizze értékét minden egyes csomópont és menj a balra vagy jobbra,

137
00:07:03,000 --> 00:07:06,000
attól függően, hogy a csomópont értéke kisebb vagy nagyobb, mint

138
00:07:06,000 --> 00:07:08,000
az, amit keresünk.

139
00:07:08,000 --> 00:07:11,000
Szóval, a gyökértől kiindulva 13, azt látjuk, hogy 89 nagyobb,

140
00:07:11,000 --> 00:07:13,000
és így megy a jobbra.

141
00:07:13,000 --> 00:07:16,000
Aztán látjuk a csomópont 34, és újra megyünk jobbra.

142
00:07:16,000 --> 00:07:20,000
89 még mindig nagyobb, mint 55, így továbbra is megy a jobb oldalon.

143
00:07:20,000 --> 00:07:24,000
Ezután jön egy csomópont értékét 144 és menj balra.

144
00:07:24,000 --> 00:07:26,000
Lo és íme, a 89 ott van.

145
00:07:26,000 --> 00:07:31,000
>> A másik dolog, amit tehetünk, nyomtassa ki az összes számok végző inorder bejárás.

146
00:07:31,000 --> 00:07:35,000
Egy inorder bejárás jelent nyomtatni mindent a bal oldali részfa

147
00:07:35,000 --> 00:07:37,000
nyomás követi a csomópont maga

148
00:07:37,000 --> 00:07:40,000
majd nyomás követi mindent a jobb részfa.

149
00:07:40,000 --> 00:07:43,000
Például vegyük a kedvenc bináris keresési fa

150
00:07:43,000 --> 00:07:46,000
és nyomtassa ki a számokat rendezetten.

151
00:07:46,000 --> 00:07:49,000
Kezdjük a gyökere a 13, de a nyomtatás előtt 13 van, hogy nyomtassa ki

152
00:07:49,000 --> 00:07:51,000
mindent a bal oldali részfa.

153
00:07:51,000 --> 00:07:55,000
Akkor megyünk 5-re. Meg kell még mélyebben le a fán, amíg meg nem találja a bal szélső csomópont,

154
00:07:55,000 --> 00:07:57,000
amely nulla.

155
00:07:57,000 --> 00:08:00,000
Nyomtatás után nulla, megyünk vissza az 1-es és nyomtassa azt ki.

156
00:08:00,000 --> 00:08:03,000
Aztán menj jobbra részfa, amely 2, és nyomtassa ki, hogy ki.

157
00:08:03,000 --> 00:08:05,000
Most, hogy mi történik, hogy a részfa,

158
00:08:05,000 --> 00:08:07,000
mehetünk vissza a 3 és nyomtassa ki.

159
00:08:07,000 --> 00:08:11,000
Folytatva vissza, kiírjuk az 5, majd a 8.

160
00:08:11,000 --> 00:08:13,000
Most, hogy elkészült az egész bal részfa,

161
00:08:13,000 --> 00:08:17,000
akkor nyomtassa ki a 13 és elkezd dolgozni a jobb részfa.

162
00:08:17,000 --> 00:08:21,000
Mi hop le a 34, de a nyomtatás előtt 34 van, hogy nyomtassa ki a bal oldali részfa.

163
00:08:21,000 --> 00:08:27,000
Tehát ki kell nyomtatni, 21, akkor megkapjuk, hogy nyomtassa ki 34 és látogasson el a jobb részfa.

164
00:08:27,000 --> 00:08:31,000
Mivel a 55 nincs bal részfa, akkor nyomtassa ki, és továbbra is a tőle jobbra részfa.

165
00:08:31,000 --> 00:08:36,000
144 egy balra részfa, és így ki kiírjuk a 89, majd a 144,

166
00:08:36,000 --> 00:08:39,000
és végül a jobb szélső csomópont, 233.

167
00:08:39,000 --> 00:08:44,000
Ott van ez, minden a számok kinyomtatható sorrendben a legalacsonyabbtól a legmagasabb.

168
00:08:44,000 --> 00:08:47,000
>> Hozzáadása valamit a fa viszonylag fájdalommentes is.

169
00:08:47,000 --> 00:08:51,000
Mindössze annyit kell tennie, hogy megbizonyosodjon arról, hogy követjük 3 bináris keresési fa tulajdonságai

170
00:08:51,000 --> 00:08:53,000
majd helyezze be az értéket, ahol van hely.

171
00:08:53,000 --> 00:08:55,000
Tegyük fel, hogy szeretnénk beszúrni értékének 7.

172
00:08:55,000 --> 00:08:58,000
7-től kevesebb, mint 13, akkor menj a bal oldalon.

173
00:08:58,000 --> 00:09:01,000
De ez 5-nél nagyobb, így keresztezik jobbra.

174
00:09:01,000 --> 00:09:04,000
Mivel ez kevesebb, mint 8 és 8 a levél csomópont, adjuk 7 balra gyermek 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Már ki egy számot a bináris keresési fa.

176
00:09:09,000 --> 00:09:12,000
>> Ha sikerül hozzá dolgokat, mi jobban tudja törölni a dolgokat is.

177
00:09:12,000 --> 00:09:14,000
Sajnos nekünk, törlésére egy kicsit bonyolultabb -

178
00:09:14,000 --> 00:09:16,000
Nem sok, de csak egy kicsit.

179
00:09:16,000 --> 00:09:18,000
Jelenleg 3 különböző forgatókönyvek, hogy meg kell vizsgálni

180
00:09:18,000 --> 00:09:21,000
törlésekor elemek bináris keresési fák.

181
00:09:21,000 --> 00:09:24,000
Először is, a legegyszerűbb eset az, hogy az elem egy levél csomópont.

182
00:09:24,000 --> 00:09:27,000
Ebben az esetben, egyszerűen törölje le, és folytassa a mi dolgunk.

183
00:09:27,000 --> 00:09:30,000
Mondja el akarjuk törölni a 7, hogy csak hozzá.

184
00:09:30,000 --> 00:09:34,000
Nos, egyszerűen keresse meg, távolítsa el, és ennyi.

185
00:09:35,000 --> 00:09:37,000
A következő eset az, ha a csomópont csak 1 gyerek.

186
00:09:37,000 --> 00:09:40,000
Itt törölheti a csomópont, de először meg kell győződjön meg róla,

187
00:09:40,000 --> 00:09:42,000
csatlakoztassa a részfa, hogy most marad árva

188
00:09:42,000 --> 00:09:44,000
a szülő a csomópont már csak el kell hagyni.

189
00:09:44,000 --> 00:09:47,000
Mondja el akarjuk törölni a mi 3 fa.

190
00:09:47,000 --> 00:09:50,000
Vesszük a gyermek eleme, hogy a csomópont és csatolja a szülő a csomópont.

191
00:09:50,000 --> 00:09:54,000
Ebben az esetben, most azon kapcsolódó az 1-től az 5.

192
00:09:54,000 --> 00:09:57,000
Ez úgy működik, anélkül, hogy a probléma, mert tudjuk, hogy szerint a bináris keresési fa ingatlanok,

193
00:09:57,000 --> 00:10:01,000
hogy mindent a bal részfa a 3 volt, kevesebb, mint 5.

194
00:10:01,000 --> 00:10:05,000
Most, hogy a 3-as részfa van intézve, akkor törölheti azt.

195
00:10:05,000 --> 00:10:08,000
A harmadik és egyben utolsó eset a legbonyolultabb.

196
00:10:08,000 --> 00:10:11,000
Ez az az eset, amikor a csomópont akarunk törölni területén 2 gyermek.

197
00:10:11,000 --> 00:10:15,000
Annak érdekében, hogy ezt, akkor először meg kell találnunk a csomópont, amely a következő legnagyobb érték,

198
00:10:15,000 --> 00:10:18,000
csere a két, majd törölje a csomópontot a kérdést.

199
00:10:18,000 --> 00:10:22,000
Figyeljük meg a csomópont, amely a következő legnagyobb érték nem lehet 2 gyermek maga

200
00:10:22,000 --> 00:10:26,000
mivel a bal gyerek lenne a jobb jelölt a következő legnagyobb.

201
00:10:26,000 --> 00:10:30,000
Ezért törlése csomópont 2 gyermek összege cseréje 2-csomópont,

202
00:10:30,000 --> 00:10:33,000
majd törli kezeli 1 a 2 említett szabályokat.

203
00:10:33,000 --> 00:10:37,000
Például, tegyük fel, szeretnénk törölni a gyökér csomópont, 13.

204
00:10:37,000 --> 00:10:39,000
Az első dolog, amit tennie, hogy megtalálja a következő legnagyobb érték a fában

205
00:10:39,000 --> 00:10:41,000
amely ebben az esetben, 21 év.

206
00:10:41,000 --> 00:10:46,000
Ezután cserélni a 2 csomópont, így 13 a levél és 21 a központi csoportban csomópontot.

207
00:10:46,000 --> 00:10:49,000
Most egyszerűen törölheti 13.

208
00:10:50,000 --> 00:10:53,000
>> Mint utalt korábban, sok lehetséges módja, hogy egy érvényes bináris keresési fa.

209
00:10:53,000 --> 00:10:56,000
Sajnos nekünk, néhány rosszabb, mint mások.

210
00:10:56,000 --> 00:10:59,000
Például, mi történik, ha építünk egy bináris keresési fa

211
00:10:59,000 --> 00:11:01,000
egy rendezett lista számok?

212
00:11:01,000 --> 00:11:04,000
Minden szám is csak hozzá a jogot minden lépést.

213
00:11:04,000 --> 00:11:06,000
Ha azt akarjuk, hogy keres egy számot,

214
00:11:06,000 --> 00:11:08,000
nincs más választásunk, csak hogy nézd meg a jogot minden lépést.

215
00:11:08,000 --> 00:11:11,000
Ez nem jobb, mint a lineáris keresés egyáltalán.

216
00:11:11,000 --> 00:11:13,000
Bár mi nem terjed ki őket ide, vannak más, bonyolultabb,

217
00:11:13,000 --> 00:11:16,000
adatszerkezeteket, hogy győződjön meg arról, hogy ez nem történhet meg.

218
00:11:16,000 --> 00:11:18,000
Azonban egy egyszerű dolog, amit tehetünk, hogy elkerüljék ezt

219
00:11:18,000 --> 00:11:21,000
hogy csak véletlenszerűen shuffle a bemeneti értékeket.

220
00:11:21,000 --> 00:11:26,000
Ez nagyon valószínűtlen, hogy a véletlen esélye a csoszogott számlista van rendezve.

221
00:11:26,000 --> 00:11:29,000
Ha ez lenne a helyzet, kaszinók nem marad az üzleti életben sokáig.

222
00:11:29,000 --> 00:11:31,000
>> Ott van ez.

223
00:11:31,000 --> 00:11:34,000
Most már tudni bináris keresést és bináris keresési fák.

224
00:11:34,000 --> 00:11:36,000
Vagyok Patrick Schmid, és ez CS50.

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

226
00:11:38,000 --> 00:11:43,000
Az egyik kézenfekvő módja az lenne, hogy végig a lista ... [BEEP]

227
00:11:43,000 --> 00:11:46,000
... A tételek számát ... yep

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

229
00:11:50,000 --> 00:11:55,000
... Elhelyezhet csomópontja 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Ez volt -