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 - Harvardin yliopisto]

3
00:00:04,000 --> 00:00:07,000
[Tämä on CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Jos antaisin luettelon Disney aakkosjärjestyksessä

5
00:00:09,000 --> 00:00:11,000
ja pyysi sinua löytämään Mikki Hiiri,

6
00:00:11,000 --> 00:00:13,000
miten mennä noin tehdä tästä?

7
00:00:13,000 --> 00:00:15,000
Yksi ilmeinen tapa olisi skannata luettelon alusta

8
00:00:15,000 --> 00:00:18,000
ja tarkista jokaista nimeä, onko se Mikki.

9
00:00:18,000 --> 00:00:22,000
Mutta kun luet Aladdin, Alice, Ariel, ja niin edelleen,

10
00:00:22,000 --> 00:00:25,000
voit nopeasti, että alkaen edessä luettelon ei ollut hyvä idea.

11
00:00:25,000 --> 00:00:29,000
Okei, ehkä sinun pitäisi aloittaa työskentely taaksepäin luettelon loppuun.

12
00:00:29,000 --> 00:00:33,000
Nyt voit lukea Tarzan, Stitch, Lumikki, ja niin edelleen.

13
00:00:33,000 --> 00:00:36,000
Silti tämä ei tunnu paras tapa edetä asiassa.

14
00:00:36,000 --> 00:00:38,000
>> No, toinen tapa että voisit mennä noin tehdä tämä on yrittää kaventaa

15
00:00:38,000 --> 00:00:41,000
nimiluettelo, että sinun täytyy katsoa.

16
00:00:41,000 --> 00:00:43,000
Koska tiedät, että ne ovat aakkosjärjestyksessä,

17
00:00:43,000 --> 00:00:45,000
voisit katsokaa nimet keskellä luettelon

18
00:00:45,000 --> 00:00:49,000
ja tarkista, Mikki Hiiri on ennen tai jälkeen tämän nimen.

19
00:00:49,000 --> 00:00:51,000
Tarkasteltaessa sukunimi toisessa sarakkeessa

20
00:00:51,000 --> 00:00:54,000
sinun ymmärtää, että M Mickey jälkeen tulee J Jasmine,

21
00:00:54,000 --> 00:00:57,000
niin olisit yksinkertaisesti sivuuttaa alkupuoliskolla luettelon.

22
00:00:57,000 --> 00:00:59,000
Sitten sinun todennäköisesti näyttää yläreunassa viimeisen sarakkeen

23
00:00:59,000 --> 00:01:02,000
ja nähdä, että se alkaa Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mikki tulee ennen Tähkäpää, näyttää voimme jättää viimeinen sarake samoin.

25
00:01:06,000 --> 00:01:08,000
Jatkuvat hakustrategia, voit nopeasti nähdä, että Mikki

26
00:01:08,000 --> 00:01:11,000
on alkupuoliskolla jäljellä nimiluettelon

27
00:01:11,000 --> 00:01:14,000
ja lopulta löytää Mickey piilossa välillä Merlin ja Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Mitä teit oli pohjimmiltaan binäärihakupuu.

29
00:01:17,000 --> 00:01:22,000
Koska tämä nimi kertoo, se suorittaa haun strategiaa binary asiassa.

30
00:01:22,000 --> 00:01:24,000
Mitä tämä tarkoittaa?

31
00:01:24,000 --> 00:01:27,000
No, annetaan luettelo lajiteltuja, binäärihakupuu algoritmi tekee binäärisen päätöksen -

32
00:01:27,000 --> 00:01:33,000
vasemmalle tai oikealle, suurempi tai pienempi kuin, aakkosellisesti ennen tai jälkeen - kussakin pisteessä.

33
00:01:33,000 --> 00:01:35,000
Nyt meillä on nimi, joka menee yhdessä tämän hakualgoritmi,

34
00:01:35,000 --> 00:01:38,000
Katsotaanpa toinen esimerkki, mutta tällä kertaa listan lajiteltu numeroita.

35
00:01:38,000 --> 00:01:43,000
Sano etsimme numero 144 tässä luettelossa lajiteltu numeroita.

36
00:01:43,000 --> 00:01:46,000
Aivan kuten ennen, huomaamme numero, joka on keskellä -

37
00:01:46,000 --> 00:01:50,000
joka tässä tapauksessa on 13 - ja nähdä, jos 144 on suurempi tai pienempi kuin 13.

38
00:01:50,000 --> 00:01:54,000
Koska se on selvästi suurempi kuin 13, voimme sivuuttaa kaikki, mikä on 13 tai vähemmän

39
00:01:54,000 --> 00:01:57,000
ja vain keskittyä jäljellä puoli.

40
00:01:57,000 --> 00:01:59,000
Koska meillä on parillinen määrä kohteita jäljellä,

41
00:01:59,000 --> 00:02:01,000
me yksinkertaisesti valita numeron, joka on lähellä keskellä.

42
00:02:01,000 --> 00:02:03,000
Tässä tapauksessa me valitsemme 55.

43
00:02:03,000 --> 00:02:06,000
Olisimme voineet yhtä hyvin valittu 89.

44
00:02:06,000 --> 00:02:11,000
Okei. Jälleen 144 on suurempi kuin 55, joten menemme oikealle.

45
00:02:11,000 --> 00:02:14,000
Onneksi meille seuraavaksi keskimmäinen numero on 144,

46
00:02:14,000 --> 00:02:16,000
yksi etsimme.

47
00:02:16,000 --> 00:02:21,000
Joten jotta löydettäisiin 144 käyttäen binäärihakupuu, pystymme löytämään sen vain 3 vaihetta.

48
00:02:21,000 --> 00:02:24,000
Jos olisimme käyttäneet lineaarista hakua täällä, se olisi vienyt meidät 12 askelta.

49
00:02:24,000 --> 00:02:28,000
Koska itse asiassa, koska tämä hakumenetelmä puolittaa kappalemäärä

50
00:02:28,000 --> 00:02:31,000
se on tutkittava kussakin vaiheessa, se löytää kohteen se hakee

51
00:02:31,000 --> 00:02:35,000
noin loki kohteiden määrä luettelossa.

52
00:02:35,000 --> 00:02:37,000
Nyt kun olemme nähneet 2 esimerkkejä, katsotaanpa katsomaan

53
00:02:37,000 --> 00:02:41,000
Joissakin pseudokoodi rekursiivinen funktio, joka toteuttaa binäärihakupuu.

54
00:02:41,000 --> 00:02:44,000
Aloita ylhäältä, näemme, että meidän on löydettävä funktio, joka kestää 4 argumentit:

55
00:02:44,000 --> 00:02:47,000
avain, array, min ja max.

56
00:02:47,000 --> 00:02:51,000
Tärkeintä on numero että etsimme, niin 144 edellisessä esimerkissä.

57
00:02:51,000 --> 00:02:54,000
Array on luettelo numeroista että etsimme.

58
00:02:54,000 --> 00:02:57,000
Min ja Max ovat indeksit minimi ja maksimi kantoja

59
00:02:57,000 --> 00:02:59,000
että olemme parhaillaan osoitteessa.

60
00:02:59,000 --> 00:03:03,000
Joten kun aloitamme, min on nolla, ja max on suurin indeksi jono.

61
00:03:03,000 --> 00:03:07,000
Kuten rajata hakua alas, päivitämme min ja max

62
00:03:07,000 --> 00:03:10,000
olla vain välillä, että etsimme edelleen sisään

63
00:03:10,000 --> 00:03:12,000
>> Katsotaanpa siirtyä mielenkiintoinen osa ensin.

64
00:03:12,000 --> 00:03:14,000
Ensimmäinen asia mitä teemme on löytää midpoint,

65
00:03:14,000 --> 00:03:19,000
indeksi on välissä min ja max array että olemme vielä harkitsevat.

66
00:03:19,000 --> 00:03:22,000
Sitten katsomme arvo array siinä keskipisteessä paikassa

67
00:03:22,000 --> 00:03:25,000
ja katso jos numero etsimme on pienempi avain.

68
00:03:25,000 --> 00:03:27,000
Jos numero tuossa asemassa on vähemmän,

69
00:03:27,000 --> 00:03:31,000
sitten se tarkoittaa, että avain on suurempi kuin kaikki numerot vasemmalla puolella, että kanta.

70
00:03:31,000 --> 00:03:33,000
Joten voimme kutsua binary hakutoiminto uudestaan,

71
00:03:33,000 --> 00:03:36,000
mutta tällä kertaa päivittää min ja max parametrit lukea vain puoli

72
00:03:36,000 --> 00:03:40,000
, joka on suurempi tai yhtä suuri kuin arvo me vain tarkasteltiin.

73
00:03:40,000 --> 00:03:44,000
Toisaalta, jos avain on pienempi kuin numero nykyisellä keskikohdassa array,

74
00:03:44,000 --> 00:03:47,000
haluamme mennä vasemmalle ja sivuuttaa kaikki luvut, jotka ovat suurempia.

75
00:03:47,000 --> 00:03:52,000
Jälleen kutsumme binäärihakupuu mutta tällä kertaa valikoima min ja max päivitettyjä

76
00:03:52,000 --> 00:03:54,000
sisällyttää vain alempi puoli.

77
00:03:54,000 --> 00:03:57,000
Jos arvo on nykyisen keskikohdassa pakassa ei ole

78
00:03:57,000 --> 00:04:01,000
suurempi kuin eikä pienempi kuin näppäintä, niin se on yhtä suuri kuin avaimen.

79
00:04:01,000 --> 00:04:05,000
Näin voimme yksinkertaisesti palata nykyinen keskipiste indeksi, ja olemme tehneet.

80
00:04:05,000 --> 00:04:09,000
Lopuksi, tämä tarkastus tässä, on siinä tapauksessa, että numero

81
00:04:09,000 --> 00:04:11,000
ei oikeastaan ​​joukko numeroita etsimme.

82
00:04:11,000 --> 00:04:14,000
Jos suurin indeksi alue että etsimme

83
00:04:14,000 --> 00:04:17,000
on aina pienempi kuin minimi, se tarkoittaa, että olemme menneet liian pitkälle.

84
00:04:17,000 --> 00:04:20,000
Koska määrä ei ollut tulo array, palaamme -1

85
00:04:20,000 --> 00:04:24,000
osoittaa, että mitään ei löytynyt.

86
00:04:24,000 --> 00:04:26,000
>> Olet ehkä huomannut, että tämä algoritmi toimii,

87
00:04:26,000 --> 00:04:28,000
luettelo numeroista on lajiteltu.

88
00:04:28,000 --> 00:04:31,000
Toisin sanoen, voimme vain löytää 144 käyttäen binäärihakupuu

89
00:04:31,000 --> 00:04:34,000
jos kaikki numerot tilataan alimmasta ylimpään.

90
00:04:34,000 --> 00:04:38,000
Jos näin ei olisi, emme voi sulkea pois puolet numerot jokaisessa vaiheessa.

91
00:04:38,000 --> 00:04:40,000
Eli meillä on 2 vaihtoehtoa.

92
00:04:40,000 --> 00:04:43,000
Joko voimme lajittelemattomana luetteloa ja lajitella se ennen binäärihakupuu,

93
00:04:43,000 --> 00:04:48,000
tai voimme varmistaa, että luettelo numeroista on järjestetty niin lisäämme numeroita sitä.

94
00:04:48,000 --> 00:04:50,000
Niinpä sen sijaan, lajittelu juuri kun meidän täytyy etsiä,

95
00:04:50,000 --> 00:04:53,000
miksi ei pidä luetteloa lajitellaan aina?

96
00:04:53,000 --> 00:04:57,000
>> Yksi tapa pitää luetteloa numeroiden järjestetty samalla mahdollistaa

97
00:04:57,000 --> 00:04:59,000
yksi lisätä tai siirtää numeroita listalta

98
00:04:59,000 --> 00:05:02,000
on käyttää jotain kutsutaan binäärihakupuu.

99
00:05:02,000 --> 00:05:05,000
Binäärihakupuu on tietorakenne, joka on 3 ominaisuudet.

100
00:05:05,000 --> 00:05:09,000
Ensinnäkin vasemman alipuun tahansa solmu sisältää vain arvot, jotka ovat vähemmän kuin

101
00:05:09,000 --> 00:05:11,000
tai yhtä suuri kuin solmun arvo.

102
00:05:11,000 --> 00:05:15,000
Toiseksi, oikea alipuun solmun sisältää vain arvot, jotka ovat suurempia kuin

103
00:05:15,000 --> 00:05:17,000
tai yhtä suuri kuin solmun arvo.

104
00:05:17,000 --> 00:05:20,000
Ja lopuksi, sekä vasen ja oikea alipuut kaikkien solmujen

105
00:05:20,000 --> 00:05:23,000
Myös binäärihakupuu puita.

106
00:05:23,000 --> 00:05:26,000
Katsotaanpa esimerkiksi samat numerot käytimme aikaisemmin.

107
00:05:26,000 --> 00:05:30,000
Niille teistä, jotka eivät ole koskaan nähneet tietojenkäsittelytieteen puu ennen,

108
00:05:30,000 --> 00:05:34,000
haluaisin aloittaa kertomalla, että tietojenkäsittelytieteen puu kasvaa alaspäin.

109
00:05:34,000 --> 00:05:36,000
Kyllä, toisin kuin puut olet tottunut,

110
00:05:36,000 --> 00:05:38,000
juuri tietojenkäsittelytieteen puu on ylhäällä,

111
00:05:38,000 --> 00:05:41,000
ja lehdet ovat alareunassa.

112
00:05:41,000 --> 00:05:45,000
Jokainen pieni laatikko kutsutaan solmu, ja solmut on yhdistetty toisiinsa reunoista.

113
00:05:45,000 --> 00:05:48,000
Niinpä juuri tämä puu on solmu arvo arvo 13,

114
00:05:48,000 --> 00:05:52,000
joka on 2 lasta solmujen arvojen 5 ja 34.

115
00:05:52,000 --> 00:05:57,000
Alipuu on puu, joka on muodostettu vain katsomalla momentti koko puun.

116
00:05:57,000 --> 00:06:03,000
>> Esimerkiksi vasemman alipuun solmun 3 on puun luoman solmut 0, 1, ja 2.

117
00:06:03,000 --> 00:06:06,000
Joten, jos menemme takaisin ominaisuuksien binäärihakupuu,

118
00:06:06,000 --> 00:06:09,000
näemme, että jokainen solmu puussa täyttää kaikki 3 ominaisuuksia, nimittäin,

119
00:06:09,000 --> 00:06:15,000
vasemman alipuun sisältää vain arvot, jotka ovat pienempiä tai yhtä suuri kuin solmun arvo;

120
00:06:15,000 --> 00:06:16,000
oikea alipuu kaikkien solmujen

121
00:06:16,000 --> 00:06:19,000
sisältää vain arvoja, jotka ovat suurempi tai yhtä suuri kuin solmun arvo; ja

122
00:06:19,000 --> 00:06:25,000
sekä vasen alipuut kaikkien solmujen ovat myös binäärihakupuu puita.

123
00:06:25,000 --> 00:06:28,000
Vaikka tämä puu näyttää erilaiselta, tämä on voimassa binäärihakupuu

124
00:06:28,000 --> 00:06:30,000
sillä samoja numeroita.

125
00:06:30,000 --> 00:06:32,000
Koska itse asiassa, on olemassa monia mahdollisia tapoja, joilla voit luoda

126
00:06:32,000 --> 00:06:35,000
voimassa binäärihakupuu näistä numeroita.

127
00:06:35,000 --> 00:06:38,000
No, mennään takaisin ensimmäinen loimme.

128
00:06:38,000 --> 00:06:40,000
Mitä voimme tehdä näitä puita?

129
00:06:40,000 --> 00:06:44,000
No, voimme hyvin yksinkertaisesti löytää minimi-ja maksimiarvot.

130
00:06:44,000 --> 00:06:46,000
Minimiarvoja löytyy aina menossa vasemmalle

131
00:06:46,000 --> 00:06:48,000
kunnes ei enää ole solmuja käydä.

132
00:06:48,000 --> 00:06:53,000
Kääntäen, löytää enintään yksi yksinkertaisesti vain menee alas oikealle kullakin hetkellä.

133
00:06:54,000 --> 00:06:56,000
>> Löytää jokin muu numero, joka ei ole pienin tai suurin

134
00:06:56,000 --> 00:06:58,000
on aivan yhtä helppoa.

135
00:06:58,000 --> 00:07:00,000
Sano etsimme numero 89.

136
00:07:00,000 --> 00:07:03,000
Me yksinkertaisesti tarkistaa arvo kunkin solmun ja siirry vasemmalle tai oikealle,

137
00:07:03,000 --> 00:07:06,000
riippuen siitä, onko solmun arvo on pienempi kuin tai suurempi kuin

138
00:07:06,000 --> 00:07:08,000
yksi etsimme.

139
00:07:08,000 --> 00:07:11,000
Joten, alkaa juureen 13, huomaamme, että 89 on suurempi,

140
00:07:11,000 --> 00:07:13,000
joten menemme oikealle.

141
00:07:13,000 --> 00:07:16,000
Sitten näemme solmu 34, ja jälleen menemme oikealle.

142
00:07:16,000 --> 00:07:20,000
89 on edelleen suurempi kuin 55, joten jatkamme menossa oikealle.

143
00:07:20,000 --> 00:07:24,000
Sitten keksiä solmu arvo 144 ja mene vasemmalle.

144
00:07:24,000 --> 00:07:26,000
Kas kummaa, 89 on oikeassa.

145
00:07:26,000 --> 00:07:31,000
>> Toinen asia, että voimme tehdä, on tulostaa kaikki numerot suorittamalla monena läpikäyminen.

146
00:07:31,000 --> 00:07:35,000
Monena traversal tarkoittaa tulostaa kaiken ulos vasemman alipuun

147
00:07:35,000 --> 00:07:37,000
seuraa painaminen solmu itse

148
00:07:37,000 --> 00:07:40,000
ja sitten seuraa painaminen kaiken ulos oikealla alipuu.

149
00:07:40,000 --> 00:07:43,000
Esimerkiksi sallikaa meidän suosikki binäärihakupuu

150
00:07:43,000 --> 00:07:46,000
ja tulostaa numerot lajiteltu järjestyksessä.

151
00:07:46,000 --> 00:07:49,000
Aloitamme juureen 13, mutta ennen tulostusta 13 meidän täytyy tulostaa

152
00:07:49,000 --> 00:07:51,000
kaikki vasemman alipuun.

153
00:07:51,000 --> 00:07:55,000
Joten menemme 5. Meillä on vielä mennä syvemmälle puuhun kunnes löydämme äärimmäisenä vasemmalla solmu,

154
00:07:55,000 --> 00:07:57,000
joka on nolla.

155
00:07:57,000 --> 00:08:00,000
Tulostuksen jälkeen nolla, menemme takaisin ylös 1 ja tulostaa se ulos.

156
00:08:00,000 --> 00:08:03,000
Sitten menemme oikeaan alipuun, joka on 2, ja tulosta se ulos.

157
00:08:03,000 --> 00:08:05,000
Nyt olemme tehneet, että alipuu,

158
00:08:05,000 --> 00:08:07,000
voimme mennä takaisin ylös 3 ja tulostaa sen.

159
00:08:07,000 --> 00:08:11,000
Jatkuvat takaisin ylös, me painamme 5 ja sitten 8.

160
00:08:11,000 --> 00:08:13,000
Nyt olemme saattaneet koko vasen alipuu,

161
00:08:13,000 --> 00:08:17,000
Voimme tulostaa 13 ja alkaa työstää oikealla alipuu.

162
00:08:17,000 --> 00:08:21,000
Meidän hop alas 34, mutta ennen tulostusta 34 joudumme tulostaa sen vasemman alipuun.

163
00:08:21,000 --> 00:08:27,000
Joten me tulostaa 21, sitten pääsemme tulostaa 34 ja käydä oikeutta alipuu.

164
00:08:27,000 --> 00:08:31,000
Koska 55 ei vasemman alipuun, me tulostaa sen ja jatka sen oikealla alipuu.

165
00:08:31,000 --> 00:08:36,000
144 on vasen alipuu, ja niin me tulostaa 89, jota seuraa 144,

166
00:08:36,000 --> 00:08:39,000
ja lopuksi äärimmäisenä oikealla solmun 233.

167
00:08:39,000 --> 00:08:44,000
Siellä on se, kaikki numerot tulostetaan järjestyksessä pienimmästä suurimpaan.

168
00:08:44,000 --> 00:08:47,000
>> Lisäämällä jotain puu on suhteellisen kivuttomasti samoin.

169
00:08:47,000 --> 00:08:51,000
Meidän täytyy vain varmistaa, että me noudatamme 3 binäärihakupuu ominaisuudet

170
00:08:51,000 --> 00:08:53,000
ja aseta arvo, jossa on tilaa.

171
00:08:53,000 --> 00:08:55,000
Sanotaan haluamme lisätä arvoa 7.

172
00:08:55,000 --> 00:08:58,000
Koska 7 on alle 13, menemme vasemmalle.

173
00:08:58,000 --> 00:09:01,000
Mutta se on suurempi kuin 5, joten etene oikealle.

174
00:09:01,000 --> 00:09:04,000
Koska se on pienempi kuin 8 ja 8 on lehtisolmu, lisäämme 7 vasemmalla puolella lapsi 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Olemme lisänneet useita meidän binäärihakupuu.

176
00:09:09,000 --> 00:09:12,000
>> Jos voimme lisätä asioita, voimme paremmin pystyä poistamaan asioita.

177
00:09:12,000 --> 00:09:14,000
Valitettavasti meille, poistaminen on vähän monimutkaisempi -

178
00:09:14,000 --> 00:09:16,000
ei paljon, mutta vain vähän.

179
00:09:16,000 --> 00:09:18,000
On 3 eri skenaarioita, jotka meidän on harkittava

180
00:09:18,000 --> 00:09:21,000
kun poistat elementtejä binäärihakupuu puista.

181
00:09:21,000 --> 00:09:24,000
Ensinnäkin Helpoin tapaus on, että elementti on lehtisolmu.

182
00:09:24,000 --> 00:09:27,000
Tässä tapauksessa me yksinkertaisesti poistaa se ja mennä meidän liiketoimintaan.

183
00:09:27,000 --> 00:09:30,000
Sano haluamme poistaa 7 että lisäsimme vain.

184
00:09:30,000 --> 00:09:34,000
No, me yksinkertaisesti löydä sitä, poista se, ja se on siinä.

185
00:09:35,000 --> 00:09:37,000
Seuraava tapaus on, jos solmulla on vain 1 lapsi.

186
00:09:37,000 --> 00:09:40,000
Täällä voimme poistaa solmun, mutta meidän on ensin varmistettava

187
00:09:40,000 --> 00:09:42,000
yhdistää alipuun joka on nyt jätetty parentless

188
00:09:42,000 --> 00:09:44,000
sen vanhemman solmun me juuri poistettu.

189
00:09:44,000 --> 00:09:47,000
Sano haluamme poistaa 3 meidän puusta.

190
00:09:47,000 --> 00:09:50,000
Otamme lapsi osa tätä solmu ja kiinnitä se vanhempi solmun.

191
00:09:50,000 --> 00:09:54,000
Tässä tapauksessa olemme nyt liittää 1 5.

192
00:09:54,000 --> 00:09:57,000
Tämä toimii ilman ongelmia, koska tiedämme, mukaan binäärihakupuu omaisuutta,

193
00:09:57,000 --> 00:10:01,000
että kaikki vasemman alipuun 3 oli alle 5.

194
00:10:01,000 --> 00:10:05,000
Nyt 3: n alipuu on hoidettu, voimme poistaa sen.

195
00:10:05,000 --> 00:10:08,000
Kolmas ja viimeinen asia on kaikkein monimutkainen.

196
00:10:08,000 --> 00:10:11,000
Näin on silloin, kun solmu halutaan poistaa on 2 lasta.

197
00:10:11,000 --> 00:10:15,000
Voidakseen tehdä tämän, meidän on ensin löydettävä solmuun että on seuraavaksi suurin arvo,

198
00:10:15,000 --> 00:10:18,000
vaihtaa kaksi, ja sitten poistaa kyseisen solmun.

199
00:10:18,000 --> 00:10:22,000
Huomaa solmu, joka on seuraavaksi suurin arvo voi olla 2 lasta itseään

200
00:10:22,000 --> 00:10:26,000
koska sen vasen lapsi olisi parempi ehdokas seuraavaksi suurin.

201
00:10:26,000 --> 00:10:30,000
Siksi poistamalla solmu 2 lasta merkitsee vaihtamisen 2 solmua,

202
00:10:30,000 --> 00:10:33,000
ja poistamalla hoitaa 1 2 mainittuja sääntöjä.

203
00:10:33,000 --> 00:10:37,000
Esimerkiksi sanokaamme haluamme poistaa juurisolmu 13.

204
00:10:37,000 --> 00:10:39,000
Ensimmäinen asia mitä teemme on löydämme seuraavaksi suurimman arvon puussa

205
00:10:39,000 --> 00:10:41,000
, joka tässä tapauksessa on 21.

206
00:10:41,000 --> 00:10:46,000
Sitten vaihtaa 2 solmua, joten 13 lehtiä ja 21 Keski-ryhmän solmu.

207
00:10:46,000 --> 00:10:49,000
Nyt voimme yksinkertaisesti poistaa 13.

208
00:10:50,000 --> 00:10:53,000
>> Kuten on viitattu aikaisemmin, on olemassa monia mahdollisia tapoja tehdä voimassa binäärihakupuu.

209
00:10:53,000 --> 00:10:56,000
Valitettavasti meille, jotkut ovat pahempia kuin toiset.

210
00:10:56,000 --> 00:10:59,000
Esimerkiksi, mitä tapahtuu, kun me rakennamme binäärihakupuu

211
00:10:59,000 --> 00:11:01,000
alkaen järjestetty numeroiden luettelosta?

212
00:11:01,000 --> 00:11:04,000
Kaikki numerot ovat vain lisätään oikeaan jokaisessa vaiheessa.

213
00:11:04,000 --> 00:11:06,000
Kun haluamme etsiä numero,

214
00:11:06,000 --> 00:11:08,000
meillä ei ole muuta vaihtoehtoa kuin vain katsoa oikealla jokaisessa vaiheessa.

215
00:11:08,000 --> 00:11:11,000
Tämä ei ole parempi kuin lineaarinen haku lainkaan.

216
00:11:11,000 --> 00:11:13,000
Vaikka emme kata niitä täällä on muitakin, monimutkaisempia,

217
00:11:13,000 --> 00:11:16,000
tietorakenteita, varmista, että tämä ei tapahdu.

218
00:11:16,000 --> 00:11:18,000
Kuitenkin yksi yksinkertainen asia, joka voidaan tehdä välttää tämä on

219
00:11:18,000 --> 00:11:21,000
vain satunnaisesti shuffle lähtöarvot.

220
00:11:21,000 --> 00:11:26,000
On erittäin epätodennäköistä, että Sattumiin sekoitetaan listan numeroita lajitellaan.

221
00:11:26,000 --> 00:11:29,000
Jos näin olisi, kasinot eivät jatkamaan toimintaansa pitkään.

222
00:11:29,000 --> 00:11:31,000
>> Siinäpä se.

223
00:11:31,000 --> 00:11:34,000
Olet nyt tietää binary etsimistä ja binäärihakupuu puita.

224
00:11:34,000 --> 00:11:36,000
Olen Patrick Schmid, ja tämä on CS50.

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

226
00:11:38,000 --> 00:11:43,000
Yksi ilmeinen tapa olisi skannata luettelon ... [piip]

227
00:11:43,000 --> 00:11:46,000
... Kappalemäärä ... jep

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

229
00:11:50,000 --> 00:11:55,000
... Post solmu 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! , Joka oli -