1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Dvejetainis Paieška]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Harvardo universiteto]

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

4
00:00:07,000 --> 00:00:09,000
>> Jei aš davė jums Disney simbolių vardai abėcėlinį sąrašą

5
00:00:09,000 --> 00:00:11,000
ir paprašė rasti Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
kaip jums eiti apie tai daryti?

7
00:00:13,000 --> 00:00:15,000
Vienas akivaizdus būdas būtų nuskaityti nuo pradžios

8
00:00:15,000 --> 00:00:18,000
ir patikrinkite kiekvieną pavadinimą, kad pamatytumėte, jei tai Mickey.

9
00:00:18,000 --> 00:00:22,000
Bet, kaip jūs skaitote ALADDIN, Alice, Arielis, ir tt,

10
00:00:22,000 --> 00:00:25,000
jūs greitai suprasite, kad pradedant nuo sąrašo priekyje nebuvo gera idėja.

11
00:00:25,000 --> 00:00:29,000
Gerai, galbūt jums reikia pradėti darbo atgal iš sąrašo pabaigoje.

12
00:00:29,000 --> 00:00:33,000
Dabar jūs skaityti Tarzan, Stitch, Snieguolė, ir taip toliau.

13
00:00:33,000 --> 00:00:36,000
Vis dėlto, tai neatrodo, kad geriausias būdas eiti apie tai.

14
00:00:36,000 --> 00:00:38,000
>> Na, dar vienas būdas, kad galite eiti apie tai daryti yra bandyti susiaurinti

15
00:00:38,000 --> 00:00:41,000
pavadinimų sąrašas, kad jūs turite pažvelgti.

16
00:00:41,000 --> 00:00:43,000
, Nes jūs žinote, kad jie yra abėcėlės tvarka,

17
00:00:43,000 --> 00:00:45,000
galite tiesiog pažvelgti pavadinimų sąrašo viduryje

18
00:00:45,000 --> 00:00:49,000
ir patikrinkite, ar Peliukas Mikis yra prieš arba po šiuo pavadinimu.

19
00:00:49,000 --> 00:00:51,000
Žiūri į antrąjį stulpelį, pavardės

20
00:00:51,000 --> 00:00:54,000
jums reikia suprasti, kad M Mickey ateina po J Jasmine,

21
00:00:54,000 --> 00:00:57,000
todėl jūs tiesiog ignoruoti sąraše pirmąją pusę.

22
00:00:57,000 --> 00:00:59,000
Tada jūs tikriausiai pažvelgti paskutinio stulpelio viršuje

23
00:00:59,000 --> 00:01:02,000
ir pamatysite, kad jis prasideda Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey ateina prieš Rapunzel, atrodo, kad mes negali ignoruoti paskutinį stulpelį taip pat.

25
00:01:06,000 --> 00:01:08,000
Tęstinis paieškos strategijos, jūs greitai pamatyti, kad Mickey

26
00:01:08,000 --> 00:01:11,000
pirmoje pusėje likusios pavadinimų sąrašą

27
00:01:11,000 --> 00:01:14,000
ir pagaliau rasti Mickey slepiasi tarp "Merlin" ir Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Ką tik padarė, buvo iš esmės dvejetainis paieškos.

29
00:01:17,000 --> 00:01:22,000
Kadangi šis pavadinimas reiškia, ji atlieka savo Searching strategijos dvejetainis medžiagos.

30
00:01:22,000 --> 00:01:24,000
Ką tai reiškia?

31
00:01:24,000 --> 00:01:27,000
Na, atsižvelgiant išdėstyti elementai sąrašas, dvejetainis paieškos algoritmas leidžia dvejetainis sprendimą -

32
00:01:27,000 --> 00:01:33,000
kairę arba į dešinę didesnis arba mažesnis, nei, pagal abėcėlę prieš arba po - kiekviename taške.

33
00:01:33,000 --> 00:01:35,000
Dabar, mes turime vardą, kad eina su šios paieškos algoritmas,

34
00:01:35,000 --> 00:01:38,000
leiskite pažvelgti į kitą, pavyzdžiui, bet šį kartą su rūšiuotų numerių sąrašą.

35
00:01:38,000 --> 00:01:43,000
Pasakykite, mes ieškome skaičius 144 šioje rūšiuotų numerių sąrašą.

36
00:01:43,000 --> 00:01:46,000
Tiesiog kaip ir anksčiau, mes rasti numerį, kad viduryje -

37
00:01:46,000 --> 00:01:50,000
, kuris šiuo atveju yra 13, ir pamatyti, jei 144 yra didesnis arba mažesnis nei 13.

38
00:01:50,000 --> 00:01:54,000
Kadangi tai yra aiškiai didesnis nei 13, mes galime ignoruoti viską, kas yra 13 ar mažiau

39
00:01:54,000 --> 00:01:57,000
ir tiesiog sutelkti dėmesį į kitą pusę.

40
00:01:57,000 --> 00:01:59,000
Kadangi dabar mes turime net jų pozicijų skaičių į kairę,

41
00:01:59,000 --> 00:02:01,000
mes tiesiog pasirinkti skaičių, kuris yra beveik viduryje.

42
00:02:01,000 --> 00:02:03,000
Šiuo atveju mes pasirinkti 55.

43
00:02:03,000 --> 00:02:06,000
Mes galėjo taip pat lengvai, pasirinktas 89.

44
00:02:06,000 --> 00:02:11,000
Gerai. Vėlgi, 144 yra didesnis nei 55, todėl mes einame į dešinę.

45
00:02:11,000 --> 00:02:14,000
Laimei mums, kitas vidutinio numeris yra 144,

46
00:02:14,000 --> 00:02:16,000
vienas, mes ieškome.

47
00:02:16,000 --> 00:02:21,000
Taigi, siekiant rasti 144 Dvejetainė paieška, mes galime jį rasti tik 3 žingsniai.

48
00:02:21,000 --> 00:02:24,000
Jei būtume čia naudojamas linijinis paiešką, jis ėmėsi 12 veiksmus.

49
00:02:24,000 --> 00:02:28,000
Tiesą sakant, nes tai paieškos metodas puselės pozicijų skaičių

50
00:02:28,000 --> 00:02:31,000
ji turi atrodyti ne kiekviename žingsnyje, ji ras elementą, jis ieško

51
00:02:31,000 --> 00:02:35,000
apie žurnalą elementų sąrašą.

52
00:02:35,000 --> 00:02:37,000
Dabar, kad mes matėme 2 pavyzdžius, galime pažvelgti

53
00:02:37,000 --> 00:02:41,000
kai rekursinis funkcija, kuri įgyvendina Dvejetainė paieška Pseudocode.

54
00:02:41,000 --> 00:02:44,000
Pradėdami nuo viršaus, matome, kad turime rasti funkciją, kuri trunka 4 argumentus:

55
00:02:44,000 --> 00:02:47,000
raktas, masyvas, min ir max.

56
00:02:47,000 --> 00:02:51,000
Svarbiausia yra skaičius, kad mes ieškome, 144 ankstesniame pavyzdyje pan.

57
00:02:51,000 --> 00:02:54,000
Masyvas yra numerių sąrašą, kad mes ieškome.

58
00:02:54,000 --> 00:02:57,000
Min ir max yra minimalūs ir maksimalūs pozicijas indeksai

59
00:02:57,000 --> 00:02:59,000
, kad mes šiuo metu ieško.

60
00:02:59,000 --> 00:03:03,000
Taigi, kai mes pradedame, min bus lygus nuliui, ir max bus maksimalus masyvo indeksas.

61
00:03:03,000 --> 00:03:07,000
Kaip mes susiaurinti paiešką, mes atnaujinsime MIN ir MAX

62
00:03:07,000 --> 00:03:10,000
būti tik asortimentą, kad mes vis dar ieškome.

63
00:03:10,000 --> 00:03:12,000
>> Leiskite pereiti prie įdomiausia dalis.

64
00:03:12,000 --> 00:03:14,000
Pirmas dalykas, ką mes darome, yra rasti įpusėjo,

65
00:03:14,000 --> 00:03:19,000
indeksas, kuris yra pusiaukelėje tarp MIN ir MAX masyvo, kad mes vis dar svarsto.

66
00:03:19,000 --> 00:03:22,000
Tada mes pažvelgti iš masyvo vertę tuo Midpoint vietą

67
00:03:22,000 --> 00:03:25,000
ir pamatyti, jei skaičius yra mažesnis nei to mygtuko, kad mes ieškome.

68
00:03:25,000 --> 00:03:27,000
Jei toje vietoje yra mažiau,

69
00:03:27,000 --> 00:03:31,000
tai reiškia, raktas yra didesnis nei visos tos pozicijos kairėje numerių.

70
00:03:31,000 --> 00:03:33,000
Taigi, mes galime vėl skambinti dvejetainis paieškos funkcija,

71
00:03:33,000 --> 00:03:36,000
bet šį kartą atnaujinti MIN ir MAX parametrus skaityti tik 1/2

72
00:03:36,000 --> 00:03:40,000
, kuris yra didesnis nei arba lygus mes tiesiog pažvelgė vertės.

73
00:03:40,000 --> 00:03:44,000
Kita vertus, jei raktas yra mažesnis nei esant dabartiniam Mediana masyvo,

74
00:03:44,000 --> 00:03:47,000
mes norime eiti į kairę ir ignoruoti visus skaičius, kurios yra didesnės.

75
00:03:47,000 --> 00:03:52,000
Vėlgi, mes vadiname Dvejetainė paieška, bet šį kartą su MIN ir MAX Atnaujinta diapazone

76
00:03:52,000 --> 00:03:54,000
įtraukti tik apatinėje.

77
00:03:54,000 --> 00:03:57,000
, Jei esant dabartiniam Mediana masyve vertė nėra nei

78
00:03:57,000 --> 00:04:01,000
nei didesnis nei mažesnis nei rakto, tada ji turi būti lygi iki rakto.

79
00:04:01,000 --> 00:04:05,000
Taigi, mes galime tiesiog grįžti esamą Midpoint indeksą, ir baigsime.

80
00:04:05,000 --> 00:04:09,000
Galiausiai, šis tikrinimas turi čia yra atveju, kad numeris

81
00:04:09,000 --> 00:04:11,000
nėra faktiškai Ieškome skaičių masyvas.

82
00:04:11,000 --> 00:04:14,000
Jei maksimali asortimentą, kad mes ieškome indeksas

83
00:04:14,000 --> 00:04:17,000
yra vis mažiau ir mažiau nei minimalus, o tai reiškia, kad mes per toli.

84
00:04:17,000 --> 00:04:20,000
Kadangi nebuvo įvesties masyvo, mes grįžti -1

85
00:04:20,000 --> 00:04:24,000
rodo, kad nieko buvo rasta.

86
00:04:24,000 --> 00:04:26,000
>> Galbūt jūs pastebėjote, kad šis algoritmas dirbti,

87
00:04:26,000 --> 00:04:28,000
numerių sąrašą turi būti rūšiuojami.

88
00:04:28,000 --> 00:04:31,000
Kitaip tariant, mes galime rasti tik 144 Dvejetainė paieška

89
00:04:31,000 --> 00:04:34,000
jei visi numeriai yra rūšiuojami nuo žemiausios iki aukščiausios.

90
00:04:34,000 --> 00:04:38,000
Jei tai ne tas atvejis, mes negalėtų išskirti pusę skaičių kiekviename žingsnyje.

91
00:04:38,000 --> 00:04:40,000
Taigi, mes turime 2 variantai.

92
00:04:40,000 --> 00:04:43,000
Arba mes galime imtis nerūšiuotų sąrašą ir rūšiuoti jį prieš naudojant Dvejetainė paieška

93
00:04:43,000 --> 00:04:48,000
ar mes galime įsitikinti, kad numerių sąrašas surūšiuotas kaip mes pridėti numerius.

94
00:04:48,000 --> 00:04:50,000
Taigi, vietoj to rūšiavimas, tik tada, kai mes turime ieškoti,

95
00:04:50,000 --> 00:04:53,000
kodėl gi ne išlaikyti visais laikais sąrašas, surūšiuotas?

96
00:04:53,000 --> 00:04:57,000
>> Surūšiuoti vienas būdas išlaikyti numerių sąrašą, ir tuo pat metu leidžiant

97
00:04:57,000 --> 00:04:59,000
pridėti, arba perkelti numerius iš šio sąrašo

98
00:04:59,000 --> 00:05:02,000
naudojant kažką vadinama dvejetainis paieškos medis.

99
00:05:02,000 --> 00:05:05,000
Dvejetainis paieškos medis yra duomenų struktūra, kuri turi 3 savybes.

100
00:05:05,000 --> 00:05:09,000
Pirma, bet kokio mazgo šaka kairėje yra tik tas vertybes, kurios yra mažiau nei

101
00:05:09,000 --> 00:05:11,000
arba lygus mazgas vertės.

102
00:05:11,000 --> 00:05:15,000
Antra, teisė šaka mazgas yra tik vertybes, kurios yra didesnės nei

103
00:05:15,000 --> 00:05:17,000
arba lygus mazgas vertės.

104
00:05:17,000 --> 00:05:20,000
Ir, pagaliau, tiek į kairę ir dešinę subtrees visų mazgų

105
00:05:20,000 --> 00:05:23,000
taip pat yra dvejetainiai paieškos medžiai.

106
00:05:23,000 --> 00:05:26,000
Pažvelkime į pavyzdį pačiais numeriais, mes naudojamas anksčiau.

107
00:05:26,000 --> 00:05:30,000
Tiems iš jūsų, kurie niekada nematė kompiuteris mokslas medis prieš,

108
00:05:30,000 --> 00:05:34,000
leiskite man pradėti, sakau, kad kompiuterių mokslas medis auga į apačią.

109
00:05:34,000 --> 00:05:36,000
Taip, skirtingai nei medžių esate įpratę,

110
00:05:36,000 --> 00:05:38,000
informatikos medžio šaknis yra viršuje,

111
00:05:38,000 --> 00:05:41,000
ir lapai yra apačioje.

112
00:05:41,000 --> 00:05:45,000
Kiekviena maža dėžutė yra vadinama mazgas, ir mazgai yra sujungti vienas su kitu kraštais.

113
00:05:45,000 --> 00:05:48,000
Taigi šio medžio šaknis yra mazgas, kurių vertė 13 vertė,

114
00:05:48,000 --> 00:05:52,000
kuris turi 2 vaikus mazgai su vertėmis, 5 ir 34.

115
00:05:52,000 --> 00:05:57,000
Šaka yra medis, kuris susidaro tiesiog žiūri visą medžio poskirsnyje.

116
00:05:57,000 --> 00:06:03,000
>> Pavyzdžiui, kairėje šaka mazgo 3 medis sukurtas mazgų 0, 1, ir 2.

117
00:06:03,000 --> 00:06:06,000
Taigi, jei mes grįžti į dvejetainis paieškos medis savybių,

118
00:06:06,000 --> 00:06:09,000
matome, kad kiekvienas medžio mazgas atitinka visus 3 savybės, ty,

119
00:06:09,000 --> 00:06:15,000
kairėje šaka yra tik vertybes, kurios yra mažesnė arba lygi mazgas vertės;

120
00:06:15,000 --> 00:06:16,000
teisė šaka visų mazgų

121
00:06:16,000 --> 00:06:19,000
yra tik vertybes, kurios yra didesnis nei arba lygus mazgas vertės ir

122
00:06:19,000 --> 00:06:25,000
kairės ir dešinės subtrees visų mazgų, taip pat yra dvejetainiai paieškos medžiai.

123
00:06:25,000 --> 00:06:28,000
Nors šis medis atrodo kitaip, tai leistinas dvejetainis paieškos medis

124
00:06:28,000 --> 00:06:30,000
už tą patį skaičių rinkinio.

125
00:06:30,000 --> 00:06:32,000
Tiesą sakant, yra daug galimų būdų, kad jūs galite sukurti

126
00:06:32,000 --> 00:06:35,000
galioja dvejetainis paieškos medis iš šių numerių.

127
00:06:35,000 --> 00:06:38,000
Na, grįžkime į pirmąjį, mes sukūrėme.

128
00:06:38,000 --> 00:06:40,000
Taigi, ką mes galime padaryti su šių medžių?

129
00:06:40,000 --> 00:06:44,000
Na, mes galime labai paprastai rasti minimalūs ir maksimalūs dydžiai.

130
00:06:44,000 --> 00:06:46,000
Mažiausios vertės galima rasti visada bus į kairę

131
00:06:46,000 --> 00:06:48,000
kol yra ne daugiau mazgų aplankyti.

132
00:06:48,000 --> 00:06:53,000
Priešingai, gauti maksimalų tiesiog tiesiog krinta į dešinę kiekvieną kartą.

133
00:06:54,000 --> 00:06:56,000
>> Apie bet kokį kitą numerį, kad nėra minimalus arba maksimalus

134
00:06:56,000 --> 00:06:58,000
yra lygiai taip pat lengva.

135
00:06:58,000 --> 00:07:00,000
Pasakykite, mes ieškome skaičius 89.

136
00:07:00,000 --> 00:07:03,000
Mes tiesiog patikrinti kiekvieno mazgo reikšmę ir eiti į kairę arba į dešinę,

137
00:07:03,000 --> 00:07:06,000
priklausomai nuo to, ar mazgas vertė yra mažesnė arba didesnė už

138
00:07:06,000 --> 00:07:08,000
vienas, mes ieškome.

139
00:07:08,000 --> 00:07:11,000
Taigi, pradedant nuo 13 metų šaknis, mes matome, kad 89 yra didesnis,

140
00:07:11,000 --> 00:07:13,000
ir taip mes einame į dešinę.

141
00:07:13,000 --> 00:07:16,000
Tada mes matome, kad už 34 mazgas, vėl eina į dešinę.

142
00:07:16,000 --> 00:07:20,000
89 vis dar yra didesnis nei 55, todėl mes ir toliau ketiname į dešinę.

143
00:07:20,000 --> 00:07:24,000
Mes tada sugalvoti su 144 vertės mazgas ir eiti į kairę.

144
00:07:24,000 --> 00:07:26,000
Štai ir štai, 89 yra teisus ten.

145
00:07:26,000 --> 00:07:31,000
>> Kitas dalykas, kad mes galime padaryti spausdinti visus numerius atlikti Inorder apeiti.

146
00:07:31,000 --> 00:07:35,000
Inorder Sankryþos spausdinti viską į kairę šaka

147
00:07:35,000 --> 00:07:37,000
spausdinimo mazgas save

148
00:07:37,000 --> 00:07:40,000
, o po to spausdinti viską iš teisė šaka.

149
00:07:40,000 --> 00:07:43,000
Pavyzdžiui, galime imtis mūsų mėgstamiausia dvejetainis paieškos medis

150
00:07:43,000 --> 00:07:46,000
ir atsispausdinti numerius rūšiuotų tvarka.

151
00:07:46,000 --> 00:07:49,000
Mes pradedame nuo 13 metų šaknis, bet 13 prieš spausdinant turime atsispausdinti

152
00:07:49,000 --> 00:07:51,000
viskas į kairę šaka.

153
00:07:51,000 --> 00:07:55,000
Taigi mes einame iki 5. Mes vis dar turime gilintis į medį, kol randame kairę pačią mazgas,

154
00:07:55,000 --> 00:07:57,000
kuris yra lygus nuliui.

155
00:07:57,000 --> 00:08:00,000
Po spausdinimo nulio, mes grįžti iki 1 ir atspausdinti, kad iš.

156
00:08:00,000 --> 00:08:03,000
Tada mes einame į dešinę šaka, kuri yra 2, ir atspausdinti, kad iš.

157
00:08:03,000 --> 00:08:05,000
Dabar, kai mes su šaka,

158
00:08:05,000 --> 00:08:07,000
galime grįžti į 3 ir atsispausdinti.

159
00:08:07,000 --> 00:08:11,000
Ir toliau atgal, mes spausdinti 5 ir 8.

160
00:08:11,000 --> 00:08:13,000
Dabar, kad mes užbaigėme visą paliko šaka,

161
00:08:13,000 --> 00:08:17,000
mes galime atspausdinti iš 13 ir pradėti dirbti dėl teisės šaka.

162
00:08:17,000 --> 00:08:21,000
Mes hop iki 34, bet 34 prieš spausdinant mes turime atsispausdinti jos kairysis šaka.

163
00:08:21,000 --> 00:08:27,000
Taigi, mes spausdinti iš 21, tada mes gauname atsispausdinti 34 ir aplankyti savo teise šaka.

164
00:08:27,000 --> 00:08:31,000
Nuo 55 neturi kairėje šaka, spausdinti, ir toliau savo teisės šaka.

165
00:08:31,000 --> 00:08:36,000
144 yra kairėje šaka, tad ir išspausdinti 89, 144,

166
00:08:36,000 --> 00:08:39,000
ir, galiausiai, dešiniuoju pelės labiausiai mazgas 233.

167
00:08:39,000 --> 00:08:44,000
Jūs turite jį, visi numeriai spausdinami, kad nuo žemiausios iki aukščiausios.

168
00:08:44,000 --> 00:08:47,000
>> Įrašyta kažką į medį, taip pat yra gana neskausmingas.

169
00:08:47,000 --> 00:08:51,000
Visi mes turime padaryti, tai įsitikinkite, kad mes laikomės 3 dvejetainis paieškos medis savybes

170
00:08:51,000 --> 00:08:53,000
ir įdėkite verte tuomet, kai yra vietos.

171
00:08:53,000 --> 00:08:55,000
Tarkime, mes norime įterpti 7 vertę.

172
00:08:55,000 --> 00:08:58,000
Nuo 7 yra mažesnis nei 13, mes einame į kairę.

173
00:08:58,000 --> 00:09:01,000
Bet tai didesnis nei 5, todėl mes feed į dešinę.

174
00:09:01,000 --> 00:09:04,000
Kadangi tai yra mažiau kaip 8 ir 8 lapų mazgas, kuriuos mes įtraukiame 7 į kairę vaiką 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Mes pridėjome numerį į mūsų dvejetainis paieškos medis.

176
00:09:09,000 --> 00:09:12,000
>> Jei mes galime pridėti dalykų, mes geriau būtų galima pašalinti dalykų, taip pat.

177
00:09:12,000 --> 00:09:14,000
Deja, mums, išbraukiant yra šiek tiek sudėtingesnis -

178
00:09:14,000 --> 00:09:16,000
nėra daug, bet tik šiek tiek.

179
00:09:16,000 --> 00:09:18,000
Yra 3 skirtingi scenarijai, kad mes turime apsvarstyti

180
00:09:18,000 --> 00:09:21,000
ištrinti elementus iš dvejetainiai paieškos medžiai.

181
00:09:21,000 --> 00:09:24,000
Pirmasis, paprasčiausias atvejis, kad elementas yra lapų mazgas.

182
00:09:24,000 --> 00:09:27,000
Šiuo atveju, mes tiesiog ištrinti jį ir eiti su mūsų verslo.

183
00:09:27,000 --> 00:09:30,000
Tarkime, mes norime ištrinti, kad mes ką tik įdėjote 7.

184
00:09:30,000 --> 00:09:34,000
Na, mes tiesiog rasti, ją pašalinkite, ir viskas.

185
00:09:35,000 --> 00:09:37,000
Kitas atvejis, jei mazgas turi tik 1 vaikas.

186
00:09:37,000 --> 00:09:40,000
Čia mes galime ištrinti mazgas, tačiau mes pirmiausia turite įsitikinti, kad

187
00:09:40,000 --> 00:09:42,000
prijungti šaka, kad dabar yra paliktas tėvų tik

188
00:09:42,000 --> 00:09:44,000
mazgas tėvų mes tiesiog ištrinti.

189
00:09:44,000 --> 00:09:47,000
Tarkime, mes norime ištrinti 3 iš mūsų medžio.

190
00:09:47,000 --> 00:09:50,000
Mes priimame vaikų to mazgo elementas ir pridėti jį prie tėvų mazgo.

191
00:09:50,000 --> 00:09:54,000
Šiuo atveju, mes dabar pritvirtinti 1 į 5.

192
00:09:54,000 --> 00:09:57,000
Tai veikia be problemų, nes mes žinome, pagal dvejetainis paieškos medis turto,

193
00:09:57,000 --> 00:10:01,000
kad viskas į kairę šaka iš 3 mažesnis nei 5.

194
00:10:01,000 --> 00:10:05,000
Dabar, kad 3 pomedžio pasirūpinta, mes jį ištrinti.

195
00:10:05,000 --> 00:10:08,000
Trečiasis ir paskutinis atvejis yra sudėtingas.

196
00:10:08,000 --> 00:10:11,000
Tai tas atvejis, kai norime ištrinti mazgas turi 2 vaikus.

197
00:10:11,000 --> 00:10:15,000
Siekiant tai padaryti, mes pirmiausia turi rasti mazgas, kuris turi kitą didžiausią reikšmę,

198
00:10:15,000 --> 00:10:18,000
apsikeitimo dviejų, ir tada ištrinti atitinkamą mazgas.

199
00:10:18,000 --> 00:10:22,000
Atkreipkite dėmesį mazgas, turi kitas didžiausia vertė negali turėti 2 vaikus, pati

200
00:10:22,000 --> 00:10:26,000
nes jos kairysis vaikas būtų geresnis kandidatas Kitas didžiausias.

201
00:10:26,000 --> 00:10:30,000
Todėl, ištrinti mazgas su 2 vaikais Swapping 2 mazgų,

202
00:10:30,000 --> 00:10:33,000
ir tada ištrinti perkrauta 1 iš 2 minėtų taisyklių.

203
00:10:33,000 --> 00:10:37,000
Pavyzdžiui, tarkime, kad mes norime ištrinti šaknų mazgas, 13.

204
00:10:37,000 --> 00:10:39,000
Pirmas dalykas, ką mes darome, yra rasti kitą didžiausią reikšmę medyje

205
00:10:39,000 --> 00:10:41,000
, kuris, šiuo atveju, yra 21.

206
00:10:41,000 --> 00:10:46,000
Mes tada apsikeitimo 2 mazgus, 13 lapų ir 21 Centrinė grupė mazgas.

207
00:10:46,000 --> 00:10:49,000
Dabar mes galime tiesiog ištrinti 13.

208
00:10:50,000 --> 00:10:53,000
>> Kaip užsiminiau anksčiau, yra daug galimų būdų, kaip padaryti galiojantį dvejetainis paieškos medis.

209
00:10:53,000 --> 00:10:56,000
Deja, mums, kai yra blogiau nei kiti.

210
00:10:56,000 --> 00:10:59,000
Pavyzdžiui, kas atsitinka, kai mes sukurti dvejetainis paieškos medis

211
00:10:59,000 --> 00:11:01,000
rūšiuotų sąrašą skaičius?

212
00:11:01,000 --> 00:11:04,000
Visi skaičiai yra tik įdėjote į dešinę kiekviename žingsnyje.

213
00:11:04,000 --> 00:11:06,000
Kai mes norime ieškoti skaičiaus,

214
00:11:06,000 --> 00:11:08,000
mes neturime kito pasirinkimo, tačiau tik pažvelgti į dešinėje kiekviename žingsnyje.

215
00:11:08,000 --> 00:11:11,000
Tai ne geriau nei tiesiškai paieškoje.

216
00:11:11,000 --> 00:11:13,000
Nors mes padengti juos čia, yra ir kitų, vis sudėtingesni,

217
00:11:13,000 --> 00:11:16,000
duomenų struktūros, įsitikinkite, kad tai neįvyks.

218
00:11:16,000 --> 00:11:18,000
Tačiau vienas paprastas dalykas, kad galima padaryti, kad būtų išvengta šios

219
00:11:18,000 --> 00:11:21,000
tiesiog atsitiktinai shuffle įvesties reikšmių.

220
00:11:21,000 --> 00:11:26,000
Tai labai mažai tikėtina, kad atsitiktine atsitiktinai išmaišytos numerių sąrašas yra rūšiuojama.

221
00:11:26,000 --> 00:11:29,000
Jei taip nutiktų, kazino nebūtų likti versle ilgai.

222
00:11:29,000 --> 00:11:31,000
>> Čia jūs turite jį.

223
00:11:31,000 --> 00:11:34,000
Dabar jūs žinote apie dvejetainis paieškos ir dvejetainiai paieškos medžiai.

224
00:11:34,000 --> 00:11:36,000
Aš esu Patrick Schmid, ir tai yra CS50.

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

226
00:11:38,000 --> 00:11:43,000
Vienas akivaizdus būdas būtų nuskaityti sąrašą iš ... [pyptelėjimas]

227
00:11:43,000 --> 00:11:46,000
... Elementų skaičius ... yep

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

229
00:11:50,000 --> 00:11:55,000
... Po 234 ... augh mazgas.

230
00:11:55,000 --> 00:11:58,000
>> Valio! Tai buvo