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
[Þetta er CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Ef ég gaf þér lista af Disney eðli nöfn í stafrófsröð

5
00:00:09,000 --> 00:00:11,000
og spurði þig að finna Mikki Mús,

6
00:00:11,000 --> 00:00:13,000
hvernig myndir þú fara að gera þetta?

7
00:00:13,000 --> 00:00:15,000
Ein augljós leið væri að skanna lista frá upphafi

8
00:00:15,000 --> 00:00:18,000
og athuga hvert nafn til að sjá hvort það er Mickey.

9
00:00:18,000 --> 00:00:22,000
En eins og þú lesið Aladdin, Alice, Ariel, og svo framvegis,

10
00:00:22,000 --> 00:00:25,000
þú munt fljótt grein fyrir því að byrja á the andlit af listanum var ekki góð hugmynd.

11
00:00:25,000 --> 00:00:29,000
Jæja, kannski þú ættir að byrja að vinna aftur á bak frá lokum listanum.

12
00:00:29,000 --> 00:00:33,000
Nú að lesa Tarzan, sauma, snjó hvítt, og svo framvegis.

13
00:00:33,000 --> 00:00:36,000
Samt, það virðist ekki eins og besta leiðin til að fara um hana.

14
00:00:36,000 --> 00:00:38,000
>> Jæja, önnur leið sem þú getur farið að gera þetta er að reyna að þrengja niður

15
00:00:38,000 --> 00:00:41,000
lista af nöfnum sem þú þarft til að líta á.

16
00:00:41,000 --> 00:00:43,000
Þar sem þú veist að þeir eru í stafrófsröð,

17
00:00:43,000 --> 00:00:45,000
þú gætir bara að líta á nöfn í miðjum listanum

18
00:00:45,000 --> 00:00:49,000
og athuga hvort Mikki Mús er fyrir eða eftir þessu nafni.

19
00:00:49,000 --> 00:00:51,000
Þegar litið er á síðasta nafn í öðrum dálki

20
00:00:51,000 --> 00:00:54,000
þú vilt skilja að M Mickey kemur eftir J fyrir Jasmine,

21
00:00:54,000 --> 00:00:57,000
þannig að þú vilt einfaldlega hunsa fyrri hluta listanum.

22
00:00:57,000 --> 00:00:59,000
Síðan sem þú vilt sennilega að líta efst í síðasta dálki

23
00:00:59,000 --> 00:01:02,000
og sjá að það byrjar með Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey kemur fyrir Rapunzel, lítur út eins og við getum að hunsa síðasta dálki eins og heilbrigður.

25
00:01:06,000 --> 00:01:08,000
Áframhaldandi leit tækni, munt þú fljótt sjá að Mickey

26
00:01:08,000 --> 00:01:11,000
er í fyrri hluta sem eftir lista yfir nöfn

27
00:01:11,000 --> 00:01:14,000
og að lokum finna Mickey felum milli Merlin og Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Það sem þú gerðir var bara í rauninni tvöfaldur leit.

29
00:01:17,000 --> 00:01:22,000
Eins þetta nafn gefur til kynna, það virkar að leita stefnu sinni í a tvöfaldur efni.

30
00:01:22,000 --> 00:01:24,000
Hvað þýðir þetta?

31
00:01:24,000 --> 00:01:27,000
Jæja, í ljósi lista yfir raðað atriði, leita tvöfaldur reiknirit gerir tvöfaldur ákvörðun -

32
00:01:27,000 --> 00:01:33,000
vinstri eða hægri, meiri en eða minna en, í stafrófsröð áður eða eftir - á hverjum stað.

33
00:01:33,000 --> 00:01:35,000
Nú þegar við höfum nafn sem fer með þessa leit reiknirit,

34
00:01:35,000 --> 00:01:38,000
skulum líta á annað dæmi, en í þetta skiptið með lista yfir raðað númer.

35
00:01:38,000 --> 00:01:43,000
Segja að við séum að leita að númer 144 á þessum lista raðað númer.

36
00:01:43,000 --> 00:01:46,000
Rétt eins og áður, finnum við fjölda sem er í miðju -

37
00:01:46,000 --> 00:01:50,000
sem í þessu tilfelli er 13 - og sjá hvort 144 er meiri en eða minna en 13.

38
00:01:50,000 --> 00:01:54,000
Þar sem það er greinilega meiri en 13, getum við hunsa allt sem er 13 eða minna

39
00:01:54,000 --> 00:01:57,000
og bara einbeita sér að hinum helming.

40
00:01:57,000 --> 00:01:59,000
Þar sem við höfum nú jafnvel fjölda af hlutum til vinstri,

41
00:01:59,000 --> 00:02:01,000
við veljum einfaldlega að tala sem er nálægt miðju.

42
00:02:01,000 --> 00:02:03,000
Í þessu tilfelli erum við að velja 55.

43
00:02:03,000 --> 00:02:06,000
Við gætum hafa bara eins auðveldlega valið 89.

44
00:02:06,000 --> 00:02:11,000
Allt í lagi. Aftur, 144 er meira en 55, þannig að við förum til hægri.

45
00:02:11,000 --> 00:02:14,000
Sem betur fer fyrir okkur, næsta miðju talan er 144,

46
00:02:14,000 --> 00:02:16,000
sá sem við erum að leita að.

47
00:02:16,000 --> 00:02:21,000
Svo í röð til að finna 144 með tvöfaldur leita, erum við fær um að finna það í aðeins 3 skrefum.

48
00:02:21,000 --> 00:02:24,000
Ef við hefðum notað línulegan leita hér, hefði það tekið okkur 12 skref.

49
00:02:24,000 --> 00:02:28,000
Eins og a staðreynd, þar sem þetta leita aðferð helminga fjölda liða

50
00:02:28,000 --> 00:02:31,000
það þarf að líta á í hverju skrefi, það verður að finna hlutinn sem það er að leita að

51
00:02:31,000 --> 00:02:35,000
í um þig inn á fjölda staka í listanum.

52
00:02:35,000 --> 00:02:37,000
Nú þegar við höfum séð 2 dæmi, við skulum taka a líta á

53
00:02:37,000 --> 00:02:41,000
sumir sauðakóðanum fyrir endurkvæma fall sem útfærir tvöfaldur leit.

54
00:02:41,000 --> 00:02:44,000
Byrjar efst, sjáum við að við verðum að finna fall sem tekur 4 rök:

55
00:02:44,000 --> 00:02:47,000
lykill, array, mín og max.

56
00:02:47,000 --> 00:02:51,000
Lykilatriðið er tala sem við erum að leita að, svo 144 í fyrra dæmi.

57
00:02:51,000 --> 00:02:54,000
Array er listi yfir númer sem við erum að leita.

58
00:02:54,000 --> 00:02:57,000
Min og Max eru vísitölur á lágmarks og hámarks stöðu

59
00:02:57,000 --> 00:02:59,000
sem við erum nú að horfa á.

60
00:02:59,000 --> 00:03:03,000
Svo þegar við byrjum, mín verður að vera núll og Max verður hámark vísitölu fylkisins.

61
00:03:03,000 --> 00:03:07,000
Eins og við þrengja leitina niður, munum við uppfæra min og max

62
00:03:07,000 --> 00:03:10,000
að vera bara allt sem við erum enn að leita inn

63
00:03:10,000 --> 00:03:12,000
>> Við skulum sleppa að áhugaverður hluti fyrst.

64
00:03:12,000 --> 00:03:14,000
The fyrstur hlutur sem við gerum er að finna miðpunkt,

65
00:03:14,000 --> 00:03:19,000
vísitalan sem er miðja vegu á milli min og max í fjölda sem við erum enn að íhuga.

66
00:03:19,000 --> 00:03:22,000
Þá erum við að líta á gildi fylkisins á þeim miðpunkt stað

67
00:03:22,000 --> 00:03:25,000
og sjá hvort sú tala sem við erum að leita að er minna en þessi lykill.

68
00:03:25,000 --> 00:03:27,000
Ef tala á þeirri stöðu er minna,

69
00:03:27,000 --> 00:03:31,000
þá þýðir það að lykillinn er stærri en öll númer vinstra megin við þá stöðu.

70
00:03:31,000 --> 00:03:33,000
Þannig að við getum kalla tvöfaldur leita virka aftur,

71
00:03:33,000 --> 00:03:36,000
en í þetta skiptið að uppfæra mín og Max breytur til að lesa bara helminginn

72
00:03:36,000 --> 00:03:40,000
sem er meiri en eða jafnt og gildi sem við horfði bara á.

73
00:03:40,000 --> 00:03:44,000
Á hinn bóginn, ef lykillinn er minni en fjöldi í núverandi miðju fylkisins,

74
00:03:44,000 --> 00:03:47,000
við viljum fara til vinstri og hunsa allar tölur sem eru stærri.

75
00:03:47,000 --> 00:03:52,000
Aftur, köllum tvöfaldur leita en í þetta skiptið með ýmsum mín og Max uppfært

76
00:03:52,000 --> 00:03:54,000
að fela bara neðri helminginn.

77
00:03:54,000 --> 00:03:57,000
Ef verð á núverandi miðju í fylkinu er hvorki

78
00:03:57,000 --> 00:04:01,000
stærri en né minna en lykillinn, þá verður það að vera jafn á takka.

79
00:04:01,000 --> 00:04:05,000
Þannig getum við einfaldlega aftur núverandi miðpunkt vísitölu, og við erum að gera.

80
00:04:05,000 --> 00:04:09,000
Að lokum, þetta athuga hér er um að ræða að fjöldi

81
00:04:09,000 --> 00:04:11,000
er í raun ekki í array af tölum sem við erum að leita.

82
00:04:11,000 --> 00:04:14,000
Ef hámarks Vísitala svið sem við erum að leita að

83
00:04:14,000 --> 00:04:17,000
er alltaf minna en lágmarki, sem þýðir að við höfum gengið of langt.

84
00:04:17,000 --> 00:04:20,000
Þar sem fjöldi var ekki í inntak fylking, aftur við -1

85
00:04:20,000 --> 00:04:24,000
benda til þess að ekkert fannst.

86
00:04:24,000 --> 00:04:26,000
>> Þú gætir hafa tekið eftir því að þessi reiknirit til að vinna,

87
00:04:26,000 --> 00:04:28,000
listi af númerum þarf að vera flokkaður.

88
00:04:28,000 --> 00:04:31,000
Með öðrum orðum, getum við aðeins að finna 144 með tvöfaldur leit

89
00:04:31,000 --> 00:04:34,000
ef allar tölur eru pöntuð frá lægsta til hæsta.

90
00:04:34,000 --> 00:04:38,000
Ef þetta væri ekki raunin, myndum við ekki vera fær um að útiloka helming tölurnar í hverju skrefi.

91
00:04:38,000 --> 00:04:40,000
Þannig að við höfum 2 möguleika.

92
00:04:40,000 --> 00:04:43,000
Annaðhvort getum við tekið óflokkuðu lista og raða því áður en þú notar tvöfaldur leit

93
00:04:43,000 --> 00:04:48,000
eða við getum verið fullviss um að listi af tölum er raðað eins og við bæta tölur til þess.

94
00:04:48,000 --> 00:04:50,000
Svona, í stað þess að flokka bara þegar við þurfum að leita að,

95
00:04:50,000 --> 00:04:53,000
hvers vegna ekki að halda lista raðað á öllum tímum?

96
00:04:53,000 --> 00:04:57,000
>> Ein leið til að halda lista yfir númer raðað jafnframt leyfa

97
00:04:57,000 --> 00:04:59,000
einn til að bæta við eða flytja númer úr þessum lista

98
00:04:59,000 --> 00:05:02,000
er með því að nota eitthvað sem kallast tvöfaldur leita tré.

99
00:05:02,000 --> 00:05:05,000
Leit tvöfaldur tré er gögn uppbygging sem hefur 3 eiginleika.

100
00:05:05,000 --> 00:05:09,000
Fyrst vinstri subtree hvaða hnút eru aðeins gildi sem eru minni en

101
00:05:09,000 --> 00:05:11,000
eða jöfn gildi hnúturinn er.

102
00:05:11,000 --> 00:05:15,000
Í öðru lagi, rétt subtree á hnút inniheldur aðeins gildi sem eru hærri en

103
00:05:15,000 --> 00:05:17,000
eða jöfn gildi hnúturinn er.

104
00:05:17,000 --> 00:05:20,000
Og að lokum, bæði vinstri og hægri subtrees allra hnúður

105
00:05:20,000 --> 00:05:23,000
eru einnig tvöfaldur tré leita.

106
00:05:23,000 --> 00:05:26,000
Við skulum líta á dæmi með sömu tölur sem við notuðum áður.

107
00:05:26,000 --> 00:05:30,000
Fyrir þá sem hafa aldrei séð tölvunarfræðinemi tré áður,

108
00:05:30,000 --> 00:05:34,000
Leyfðu mér að byrja með því að segja þér að vísindi tölva tré vex niður.

109
00:05:34,000 --> 00:05:36,000
Já, ólíkt tré sem þú ert vön að,

110
00:05:36,000 --> 00:05:38,000
rót á tölvunarfræði tré er efst,

111
00:05:38,000 --> 00:05:41,000
og leyfi eru neðst.

112
00:05:41,000 --> 00:05:45,000
Hver lítill kassi er kallað hnút og hnútar eru tengdir hver öðrum með brúnum.

113
00:05:45,000 --> 00:05:48,000
Svo er rót þessa tré hnút gildi við gildi 13,

114
00:05:48,000 --> 00:05:52,000
sem hefur 2 börn hnúður með gildi 5 og 34..

115
00:05:52,000 --> 00:05:57,000
A subtree er tré, sem er mynduð með því að horfa á lið af öllu tré.

116
00:05:57,000 --> 00:06:03,000
>> Til dæmis, vinstri subtree í hnút 3 er tré búin af hnúður 0, 1 og 2.

117
00:06:03,000 --> 00:06:06,000
Svo ef við förum aftur til eiginleika leita tvöfaldur tré,

118
00:06:06,000 --> 00:06:09,000
sjáum við að hver hnútur í trénu samræmi við alla 3 eiginleika, þ.e.,

119
00:06:09,000 --> 00:06:15,000
vinstri subtree inniheldur aðeins gildi sem eru minna en eða jafnt og gildi hnúturinn er;

120
00:06:15,000 --> 00:06:16,000
rétt subtree allra hnúður

121
00:06:16,000 --> 00:06:19,000
inniheldur aðeins gildi sem eru stærri en eða jöfn gildi hnúturinn er, og

122
00:06:19,000 --> 00:06:25,000
bæði til vinstri og hægri subtrees allra hnúta eru einnig tvöfaldur leita tré.

123
00:06:25,000 --> 00:06:28,000
Þó að þessi tré lítur öðruvísi, þetta er gild tvöfaldur leita tré

124
00:06:28,000 --> 00:06:30,000
fyrir sama mengi af tölum.

125
00:06:30,000 --> 00:06:32,000
Eins og a staðreynd, there ert margir mögulegar leiðir sem þú getur búið

126
00:06:32,000 --> 00:06:35,000
gilt tvöfaldur leita tré frá þessum tölum.

127
00:06:35,000 --> 00:06:38,000
Jæja, við skulum fara aftur til fyrsta við bjuggum.

128
00:06:38,000 --> 00:06:40,000
Og hvað getum við gert við þessum trjám?

129
00:06:40,000 --> 00:06:44,000
Jæja, við getum mjög einfaldlega að finna lágmarks og hámarks gildi.

130
00:06:44,000 --> 00:06:46,000
Lágmarksgildi má finna með því að alltaf að fara til vinstri

131
00:06:46,000 --> 00:06:48,000
þangað til það eru ekki fleiri hnútar til að heimsækja.

132
00:06:48,000 --> 00:06:53,000
Hins vegar að finna hámarks einfaldlega fer bara niður til hægri á hverjum tíma.

133
00:06:54,000 --> 00:06:56,000
>> Finna önnur tala sem er ekki lágmarks-eða hámarks

134
00:06:56,000 --> 00:06:58,000
er alveg jafn auðvelt.

135
00:06:58,000 --> 00:07:00,000
Segja að við erum að leita að númer 89..

136
00:07:00,000 --> 00:07:03,000
Við athuga einfaldlega gildi hvern hnút og fara til vinstri eða hægri

137
00:07:03,000 --> 00:07:06,000
fer eftir því hvort gildið hnúturinn er minna en eða meira en

138
00:07:06,000 --> 00:07:08,000
sá sem við erum að leita að.

139
00:07:08,000 --> 00:07:11,000
Svo, byrja á the rót af 13, sjáum við að 89 er meira

140
00:07:11,000 --> 00:07:13,000
og svo förum við til hægri.

141
00:07:13,000 --> 00:07:16,000
Þá sjáum við hnút í 34, og aftur við að fara til hægri.

142
00:07:16,000 --> 00:07:20,000
89 er enn meiri en 55, þannig að við höldum áfram að fara til hægri.

143
00:07:20,000 --> 00:07:24,000
Við komum svo upp með hnút með verðmæti 144 og fara til vinstri.

144
00:07:24,000 --> 00:07:26,000
Lo og sjá, 89 er rétt þar.

145
00:07:26,000 --> 00:07:31,000
>> Annar hlutur sem við getum gert er að prenta út öll númer með því að framkvæma á inorder traversal.

146
00:07:31,000 --> 00:07:35,000
An inorder traversal þýðir að prenta allt út í vinstri subtree

147
00:07:35,000 --> 00:07:37,000
eftir prentun hnúturinn sig

148
00:07:37,000 --> 00:07:40,000
og þá á eftir að prenta allt út í rétt subtree.

149
00:07:40,000 --> 00:07:43,000
Til dæmis, við skulum taka uppáhalds tvöfaldur leita tré okkar

150
00:07:43,000 --> 00:07:46,000
og prenta út tölur í raðað röð.

151
00:07:46,000 --> 00:07:49,000
Við byrjum á the rót af 13, en áður en prentun 13 verðum við að prenta út

152
00:07:49,000 --> 00:07:51,000
allt í vinstri subtree.

153
00:07:51,000 --> 00:07:55,000
Svo við förum í 5. Við höfum enn að fara dýpra ofan í trénu þar sem við finna vinstri-mest hnút,

154
00:07:55,000 --> 00:07:57,000
sem er núll.

155
00:07:57,000 --> 00:08:00,000
Eftir prentun núll, förum við aftur upp á 1 og prenta það út.

156
00:08:00,000 --> 00:08:03,000
Þá erum við að fara til hægri subtree, sem er 2, og prenta það út.

157
00:08:03,000 --> 00:08:05,000
Nú þegar við erum búin með það subtree,

158
00:08:05,000 --> 00:08:07,000
getum við farið aftur upp í 3 og prenta það út.

159
00:08:07,000 --> 00:08:11,000
Áframhaldandi aftur upp, prenta við 5 og þá 8.

160
00:08:11,000 --> 00:08:13,000
Nú þegar við höfum lokið öllu eftir subtree,

161
00:08:13,000 --> 00:08:17,000
getum við prentað út 13 og byrja að vinna á rétt subtree.

162
00:08:17,000 --> 00:08:21,000
Við hoppa niður í 34, en áður en prentun 34 við þurfum að prenta út vinstri subtree þess.

163
00:08:21,000 --> 00:08:27,000
Þannig að við að prenta út 21, þá fáum við að prenta út 34 og fara rétt subtree þess.

164
00:08:27,000 --> 00:08:31,000
Þar sem 55 hefur engin vinstri subtree, prenta við það út og halda áfram til hægri subtree þess.

165
00:08:31,000 --> 00:08:36,000
144 hefur vinstri subtree, og svo við að prenta út 89, á eftir 144,

166
00:08:36,000 --> 00:08:39,000
og loks hægri mest hnút 233.

167
00:08:39,000 --> 00:08:44,000
There þú hafa það, allar tölur eru prentaðar út í röð frá lægstu til hæsta.

168
00:08:44,000 --> 00:08:47,000
>> Bæti einhverju við tré er tiltölulega sársaukalaus eins og heilbrigður.

169
00:08:47,000 --> 00:08:51,000
Allt sem við þurfum að gera er að tryggja að við fylgjum 3 tvöfaldur leita tré eignir

170
00:08:51,000 --> 00:08:53,000
og þá setja gildi þar er pláss.

171
00:08:53,000 --> 00:08:55,000
Segjum að við viljum að setja gildi 7.

172
00:08:55,000 --> 00:08:58,000
Síðan 7 er minna en 13, förum við til vinstri.

173
00:08:58,000 --> 00:09:01,000
En það er meira en 5, þannig að við að fara yfir til hægri.

174
00:09:01,000 --> 00:09:04,000
Þar sem það er minna en 8 og 8 er blaða hnút, bæta við 7 til vinstri barn 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Við höfum bætt við fjölda til tvöfaldur leita tré okkar.

176
00:09:09,000 --> 00:09:12,000
>> Ef við getum bætt það, að við betur í stakk búnir til að eyða hlutum eins og heilbrigður.

177
00:09:12,000 --> 00:09:14,000
Því miður fyrir okkur, að eyða er svolítið flóknara -

178
00:09:14,000 --> 00:09:16,000
ekki mikið, en bara svolítið.

179
00:09:16,000 --> 00:09:18,000
Það eru 3 mismunandi aðstæður sem við verðum að íhuga

180
00:09:18,000 --> 00:09:21,000
þegar þú eyðir þætti frá tvíundartré leit.

181
00:09:21,000 --> 00:09:24,000
First, auðveldasta málið er að þátturinn er blaða hnút.

182
00:09:24,000 --> 00:09:27,000
Í þessu tilviki, eyða við einfaldlega það og fara með viðskipti okkar.

183
00:09:27,000 --> 00:09:30,000
Segjum að við viljum eyða 7 sem við lögðum bara.

184
00:09:30,000 --> 00:09:34,000
Jæja, við finnum einfaldlega það, fjarlægja það, og það er það.

185
00:09:35,000 --> 00:09:37,000
Næsta mál er ef hnúturinn hefur aðeins 1 barn.

186
00:09:37,000 --> 00:09:40,000
Hér getum við að eyða hnút, en við verðum fyrst að ganga úr skugga um

187
00:09:40,000 --> 00:09:42,000
að tengja subtree sem er nú eftir foreldralausra

188
00:09:42,000 --> 00:09:44,000
til foreldris í hnút við eytt bara.

189
00:09:44,000 --> 00:09:47,000
Segjum að við viljum eyða 3 af trénu okkar.

190
00:09:47,000 --> 00:09:50,000
Við tökum barnið þáttur þeirrar hnút og festa það við foreldri hnút.

191
00:09:50,000 --> 00:09:54,000
Í þessu tilfelli erum við nú að festa 1 til 5.

192
00:09:54,000 --> 00:09:57,000
Þetta virkar án vandamál vegna þess að við vitum, samkvæmt leita tvíundartré eign,

193
00:09:57,000 --> 00:10:01,000
að allt í vinstri subtree af 3 var minna en 5.

194
00:10:01,000 --> 00:10:05,000
Nú er 3 subtree er gætt af, við getum eytt.

195
00:10:05,000 --> 00:10:08,000
Þriðja og síðasta málið er flóknasta.

196
00:10:08,000 --> 00:10:11,000
Þetta er raunin þegar hnúturinn við viljum að eyða á 2 börn.

197
00:10:11,000 --> 00:10:15,000
Til að gera þetta, verðum við fyrst að finna hnút sem hefur næstu stærsta gildi,

198
00:10:15,000 --> 00:10:18,000
skipti tvö, og síðan eyða hnút ræðir.

199
00:10:18,000 --> 00:10:22,000
Takið hnúturinn sem hefur næsta stærsta gildi getur ekki haft 2 börn sig

200
00:10:22,000 --> 00:10:26,000
frá vinstri barnið hennar væri betri frambjóðandi fyrir næsta stærsta.

201
00:10:26,000 --> 00:10:30,000
Því að eyða hnút með 2 börn nemur swap 2 hnúta,

202
00:10:30,000 --> 00:10:33,000
og þá að eyða er stjórnað af 1 af 2 framangreindum reglum.

203
00:10:33,000 --> 00:10:37,000
Til dæmis, segjum skulum við viljum eyða rót hnút, 13.

204
00:10:37,000 --> 00:10:39,000
The fyrstur hlutur sem við gerum er að við að finna næsta stærsta gildi í trénu

205
00:10:39,000 --> 00:10:41,000
sem í þessu tilfelli er 21.

206
00:10:41,000 --> 00:10:46,000
Við skipti síðan á 2 hnúta, að 13 lauf og 21 Mið hópur hnút.

207
00:10:46,000 --> 00:10:49,000
Nú getum við einfaldlega eytt 13.

208
00:10:50,000 --> 00:10:53,000
>> Eins benti á áðan, þá eru margar mögulegar leiðir til að gera gilt tvöfaldur leita tré.

209
00:10:53,000 --> 00:10:56,000
Því miður fyrir okkur, sumir eru verri en aðrir.

210
00:10:56,000 --> 00:10:59,000
Til dæmis, hvað gerist þegar við að byggja upp tvöfaldur leita tré

211
00:10:59,000 --> 00:11:01,000
frá raðaða lista af tölum?

212
00:11:01,000 --> 00:11:04,000
Allar tölur eru bara bætt við til hægri á hverju skrefi.

213
00:11:04,000 --> 00:11:06,000
Þegar við viljum að leita að tala,

214
00:11:06,000 --> 00:11:08,000
við höfum ekkert val en bara að líta á the réttur í hverju skrefi.

215
00:11:08,000 --> 00:11:11,000
Þetta er ekki betri en línuleg leit yfirleitt.

216
00:11:11,000 --> 00:11:13,000
Þó við munum ekki ná þeim hér, það eru hins vegar flóknari,

217
00:11:13,000 --> 00:11:16,000
gögn uppbygging sem tryggja að þetta gerist ekki.

218
00:11:16,000 --> 00:11:18,000
Hvernig sem, einn einfaldur hlutur sem hægt er að gera til að koma í veg fyrir þetta er

219
00:11:18,000 --> 00:11:21,000
að bara af handahófi uppstokkun inntak gildi.

220
00:11:21,000 --> 00:11:26,000
Það er mjög ólíklegt að með því að handahófi tækifæri sem stokkuð lista af tölum er raðað.

221
00:11:26,000 --> 00:11:29,000
Ef þetta væri raunin, spilavítum myndi ekki vera í viðskiptum lengi.

222
00:11:29,000 --> 00:11:31,000
>> There þú hafa það.

223
00:11:31,000 --> 00:11:34,000
Þú veist nú um tvöfaldur leit og tvöfaldur leita tré.

224
00:11:34,000 --> 00:11:36,000
Ég er Patrick Schmid, og þetta er CS50.

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

226
00:11:38,000 --> 00:11:43,000
Ein augljós leið væri að skanna lista frá ... [píp]

227
00:11:43,000 --> 00:11:46,000
... Fjöldi hluta ... Já

228
00:11:46,000 --> 00:11:50,000
[Hlær]

229
00:11:50,000 --> 00:11:55,000
... Senda hnút 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Það var -