1
00:00:00,000 --> 00:00:02,994
>> [TÓNLIST spila]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Þannig að við höfum verið að fikra nær
og nær að Gral gögnum

4
00:00:08,550 --> 00:00:13,050
mannvirki, einn sem við getum sett
í, eyða úr og líta upp

5
00:00:13,050 --> 00:00:15,440
í föstu tíma.

6
00:00:15,440 --> 00:00:16,270
Hægri.

7
00:00:16,270 --> 00:00:17,280
Það er tegund af markinu.

8
00:00:17,280 --> 00:00:19,720
Við viljum vera fær um að gera
það mjög, mjög fljótt.

9
00:00:19,720 --> 00:00:22,580
>> Höfum við fundið það hér þegar
við erum að tala um reynir?

10
00:00:22,580 --> 00:00:23,670
Jæja, við skulum taka a líta.

11
00:00:23,670 --> 00:00:25,628
Þannig að við höfum séð nokkur
mismunandi gögn uppbygging

12
00:00:25,628 --> 00:00:28,680
sem annast kortlagningu
svokölluð lykill-gildi par,

13
00:00:28,680 --> 00:00:32,080
kortleggja nokkur stykki af gögn
að einhverju öðru stykki af gögn

14
00:00:32,080 --> 00:00:36,020
svo við vitum hvar á að finna
Upplýsingar í uppbyggingu.

15
00:00:36,020 --> 00:00:40,060
>> Svo fyrir array, til dæmis, að
lykill er þáttur vísitölu eða array

16
00:00:40,060 --> 00:00:42,600
staðsetningu 0 eða fylki 1 og svo framvegis.

17
00:00:42,600 --> 00:00:46,140
Og gildi eru gögnin
sem er til staðar á þeim stað.

18
00:00:46,140 --> 00:00:48,550
Svo hvað er geymt í array 0?

19
00:00:48,550 --> 00:00:54,290
Hvað er geymt í array 1 á móti bara
0 og 1, sem væri lykillinn.

20
00:00:54,290 --> 00:00:56,360
>> Með kjötkássa borð það er
tegund af sömu hugmynd.

21
00:00:56,360 --> 00:01:00,690
Með kjötkássa borð, höfum við þetta kjötkássa
fall sem býr til kjötkássa kóða.

22
00:01:00,690 --> 00:01:03,670
Svo er lykillinn kjötkássa kóða gögnum.

23
00:01:03,670 --> 00:01:06,530
Og verðmæti, sérstaklega
við töluðum um chaining

24
00:01:06,530 --> 00:01:10,590
í vídeó á kjötkássa matskeið,
er að tengist listi af gögnum

25
00:01:10,590 --> 00:01:12,550
sem kjötkássa þeirri Tætifall.

26
00:01:12,550 --> 00:01:14,050
Hægri.

27
00:01:14,050 --> 00:01:16,050
Hvað um aðra nálgun
Þessi aðferð, þó?

28
00:01:16,050 --> 00:01:21,000
Hvað um aðferð þar sem
Lykillinn er tryggt að vera einstakt,

29
00:01:21,000 --> 00:01:25,410
ólíkt kjötkássa borð, þar sem við gátum
endað með tvö stykki af gögnum

30
00:01:25,410 --> 00:01:27,200
hafa sömu Tætifall.

31
00:01:27,200 --> 00:01:30,020
Og þá verðum við að takast á við
að með því að annað hvort leit eða fleiri

32
00:01:30,020 --> 00:01:33,340
helst læsa að laga þessi vandamál.

33
00:01:33,340 --> 00:01:37,520
>> Svo nú getum við tryggt
sem lykill okkar mun vera einstakt.

34
00:01:37,520 --> 00:01:39,690
Og hvað ef gildi okkar var
bara eitthvað sem auðvelt

35
00:01:39,690 --> 00:01:44,080
eins satt og ósatt sem segir okkur hvort
eða ekki stykki af upplýsingar

36
00:01:44,080 --> 00:01:45,610
er í uppbyggingu?

37
00:01:45,610 --> 00:01:48,180
A Boolean gæti verið eins einfalt og a hluti.

38
00:01:48,180 --> 00:01:52,660
Raunhæft er það líklega
Byte líklegri en smá.

39
00:01:52,660 --> 00:01:55,410
En það er miklu minni en
geyma kannski 50 staf band,

40
00:01:55,410 --> 00:01:57,360
til dæmis.

41
00:01:57,360 --> 00:02:02,210
>> Svo reynir, svipað kjötkássa borð,
sem sameina fylki og tengda listanum,

42
00:02:02,210 --> 00:02:05,790
reynir sameina fylki,
mannvirki og ábendingum

43
00:02:05,790 --> 00:02:08,509
saman til að geyma gögn í
áhugaverð leið sem er

44
00:02:08,509 --> 00:02:11,550
nokkuð frábrugðin
eitthvað sem við höfum séð hingað til.

45
00:02:11,550 --> 00:02:16,750
Nú notum við gögn sem vegamaður
að sigla þessa gögn uppbygging.

46
00:02:16,750 --> 00:02:18,710
Og ef við getum fylgst
sem vegamaður, ef við getum

47
00:02:18,710 --> 00:02:22,390
fylgja gögn frá
upphafi til enda, við munum

48
00:02:22,390 --> 00:02:24,945
vita hvort þessi gögn
eru í Trie.

49
00:02:24,945 --> 00:02:28,310
>> Og ef við getum ekki fylgt kortinu
frá þýðir að enda á alla,

50
00:02:28,310 --> 00:02:30,600
gögn geta ekki til.

51
00:02:30,600 --> 00:02:32,890
Aftur, eru lykillinn hér
tryggt að vera einstakt.

52
00:02:32,890 --> 00:02:36,020
Og svo ólíkt kjötkássa borð, munum við aldrei
að takast á við árekstra hér.

53
00:02:36,020 --> 00:02:39,090
Og engar tvær stykki af gögnum
hafa nákvæmlega sömu vegamaður

54
00:02:39,090 --> 00:02:40,530
nema að gögn séu eins.

55
00:02:40,530 --> 00:02:44,580
>> Ef við setjum John, þá
við að leita að John.

56
00:02:44,580 --> 00:02:47,430
Það er tvær samskonar stykki af
gögn, rétt, við erum að leita í gegnum.

57
00:02:47,430 --> 00:02:49,880
En annars, hvaða
tvö stykki af gögn eru

58
00:02:49,880 --> 00:02:52,750
tryggt að hafa einstaka roadmaps
í gegnum þetta gagnagrind.

59
00:02:52,750 --> 00:02:56,210
Og við erum að fara að kíkja á
sjón af þessu í bara smá stund.

60
00:02:56,210 --> 00:02:58,810
>> Við munum gera það með því að reyna að
búa til nýja gögn uppbygging,

61
00:02:58,810 --> 00:03:00,564
kortleggja á eftirfarandi gildi pör.

62
00:03:00,564 --> 00:03:03,480
Í þessu tilfelli erum við ekki að fara að nota
eitthvað eins einfalt og Boolean.

63
00:03:03,480 --> 00:03:06,200
Við reyndar mun geyma band.

64
00:03:06,200 --> 00:03:08,690
Og það band er að fara að
veri nafn háskóla.

65
00:03:08,690 --> 00:03:12,140
>> Og lykillinn er að fara að vera ár
þegar að Háskólinn var stofnaður.

66
00:03:12,140 --> 00:03:15,380
Öll ár til háskóla
eru að fara að vera fjórir stafir.

67
00:03:15,380 --> 00:03:19,840
Og svo við munum nota þessar fjórar tölur til
rata um gögn uppbygging.

68
00:03:19,840 --> 00:03:22,270
Og við munum sjá, aftur, hvernig
við gerum það í bara annað.

69
00:03:22,270 --> 00:03:25,110
>> Í lok leið,
við munum sjá nafn

70
00:03:25,110 --> 00:03:30,250
háskólans sem svarar
við takkann, þessir fjórir tölustafir.

71
00:03:30,250 --> 00:03:34,390
Grunnhugmyndin á bak við Trie
er að við höfum miðlæga bláæð.

72
00:03:34,390 --> 00:03:35,640
Svo hugsa um það eins og tré.

73
00:03:35,640 --> 00:03:39,211
Og þetta er svipað í stafsetningu
og í hugtak til tré.

74
00:03:39,211 --> 00:03:41,460
Almennt þegar við hugsum um
tré í hinum raunverulega heimi,

75
00:03:41,460 --> 00:03:44,090
þeir hafa rót sem er í
jörð og þeir vaxa upp

76
00:03:44,090 --> 00:03:46,830
og þeir hafa útibú
og þeir hafa leyfi.

77
00:03:46,830 --> 00:03:49,450
Og í rauninni er hugmyndin um
a Trie er nákvæmlega það sama,

78
00:03:49,450 --> 00:03:51,755
nema að rót er fest
einhvers staðar á himni.

79
00:03:51,755 --> 00:03:53,130
Og blöðin eru neðst.

80
00:03:53,130 --> 00:03:55,750
>> Svo það er góður af eins og að taka tré
og bara snúa henni á hvolf.

81
00:03:55,750 --> 00:03:56,880
En það eru samt útibú.

82
00:03:56,880 --> 00:03:59,463
Og þeir væri ferli okkar,
þá verður tengingar okkar

83
00:03:59,463 --> 00:04:02,220
frá rót til laufum.

84
00:04:02,220 --> 00:04:04,200
Í þessu tilviki, þá
slóðir, þá útibú

85
00:04:04,200 --> 00:04:08,490
eru merktar með tölustöfum sem segja okkur
sem leið til að fara þar sem við erum.

86
00:04:08,490 --> 00:04:11,800
>> Ef við sjáum 0, við förum niður þessa grein,
ef við sjáum 1, við förum niður þessa grein,

87
00:04:11,800 --> 00:04:12,900
og svo og svo framvegis.

88
00:04:12,900 --> 00:04:14,060
Jæja, hvað þýðir þetta?

89
00:04:14,060 --> 00:04:16,519
Jæja, það þýðir að
á hverjum mótum stað

90
00:04:16,519 --> 00:04:19,260
og hver hnútur í
miðju og hvert útibú,

91
00:04:19,260 --> 00:04:23,020
það eru 10 mögulegt
stöðum sem við getum farið.

92
00:04:23,020 --> 00:04:27,690
Þannig að það eru 10 ábendingar
frá hverjum stað.

93
00:04:27,690 --> 00:04:30,610
>> Og þetta er þar reynir getur fengið
svolítið erfið fyrir einhvern

94
00:04:30,610 --> 00:04:34,460
sem er ekki með mikið af
reynslu í tölvunarfræði áður.

95
00:04:34,460 --> 00:04:35,960
En reynir eru í raun nokkuð ógnvekjandi.

96
00:04:35,960 --> 00:04:37,793
Og ef þú hefur
tækifæri til að vinna með þeim

97
00:04:37,793 --> 00:04:40,420
og þú ert tilbúin til að grafa í
og tilraunir með þá,

98
00:04:40,420 --> 00:04:44,234
þeir eru í raun alveg áhugavert
gögn uppbygging til að vinna með.

99
00:04:44,234 --> 00:04:46,900
Ef við viljum að setja stak
í Trie, allt sem við þurfum að gera

100
00:04:46,900 --> 00:04:51,360
er að byggja rétta slóð
frá rót til blaða.

101
00:04:51,360 --> 00:04:55,390
Hér er það sem hvert skref meðfram
hvernig gæti litið út.

102
00:04:55,390 --> 00:04:59,660
Við erum að fara að skilgreina ný gögn
uppbygging fyrir nýjan hnút kallast Trie.

103
00:04:59,660 --> 00:05:02,560
>> Og inni í því gögn
uppbygging eru tvö stykki.

104
00:05:02,560 --> 00:05:05,460
Við erum að fara til að geyma
Heiti háskóla.

105
00:05:05,460 --> 00:05:09,410
Og við erum að fara að geyma
fjölbreytta ábendingum

106
00:05:09,410 --> 00:05:12,190
öðrum hnúður af sömu gerð.

107
00:05:12,190 --> 00:05:14,780
Svo aftur, þetta er þessi tegund
af hugmyndinni um alls staðar

108
00:05:14,780 --> 00:05:18,567
við erum, við erum á 10 hægt
stöðum við getum farið.

109
00:05:18,567 --> 00:05:20,150
Ef við sjáum 0, við förum niður þessa grein.

110
00:05:20,150 --> 00:05:22,690
Ef við sjáum 1, þetta útibú,
og svo framvegis og svo framvegis og svo framvegis.

111
00:05:22,690 --> 00:05:25,160
Ef við segjum 9, við förum niður þessa grein.

112
00:05:25,160 --> 00:05:28,220
Svo á hverjum mótum lið,
getum við farið 10 mögulegum stöðum.

113
00:05:28,220 --> 00:05:35,740
Svo hefur hver hnútur að innihalda 10 ábendingum
öðrum hnúður, til 10 annarra hnúta.

114
00:05:35,740 --> 00:05:39,810
>> Og gögn sem við erum að geyma er
bara nafn skólans.

115
00:05:39,810 --> 00:05:41,060
Svo skulum byggja Trie.

116
00:05:41,060 --> 00:05:44,860
Skulum setja nokkrar
efna og hluta í Trie okkar.

117
00:05:44,860 --> 00:05:46,740
Svo á the mjög toppur,
þetta er hnút rót okkar.

118
00:05:46,740 --> 00:05:49,740
Þetta er líklega að fara að vera eitthvað
þú ert að fara að á heimsvísu, það boðum.

119
00:05:49,740 --> 00:05:53,450
Og þú ert að fara að á heimsvísu viðhalda
bendi til þessa hnút alltaf.

120
00:05:53,450 --> 00:05:55,360
>> Þú ert að fara að segja,
rót jafngildir, og þú ert

121
00:05:55,360 --> 00:05:57,580
fara að malloc þér Trie hnút.

122
00:05:57,580 --> 00:05:59,850
Og þú ert aldrei að fara
að snerta rót aftur.

123
00:05:59,850 --> 00:06:02,300
Í hvert skipti sem þú vilt að
byrja siglingar í gegnum,

124
00:06:02,300 --> 00:06:05,802
þú Aðra músina
jafn rót, svo sem Trav,

125
00:06:05,802 --> 00:06:07,760
sem er dæmi sem ég
nota í mörgum myndböndum mínum

126
00:06:07,760 --> 00:06:11,090
hér á stöflum og biðröðum
og tengja listar og svo framvegis.

127
00:06:11,090 --> 00:06:13,320
>> Þú Aðra músina
kallað Trav fyrir traversal.

128
00:06:13,320 --> 00:06:15,890
Og þú notar Trav að sigla
gegnum gögn uppbygging.

129
00:06:15,890 --> 00:06:17,500
Þannig að við skulum sjá hvernig þetta gæti litið.

130
00:06:17,500 --> 00:06:19,880
Svo núna, hvað
er hnúturinn líta út?

131
00:06:19,880 --> 00:06:22,920
Jæja, eins og gögn okkar
uppbyggingu yfirlýsingu fram,

132
00:06:22,920 --> 00:06:26,906
við höfum band, sem
í þessu tilfelli er tóm.

133
00:06:26,906 --> 00:06:27,780
Það er ekkert hér.

134
00:06:27,780 --> 00:06:29,550
>> Og fjölda 10 ábendingum.

135
00:06:29,550 --> 00:06:31,790
Og núna, aðeins við
hafa 1 hnút í þessum Trie.

136
00:06:31,790 --> 00:06:33,110
Það er ekkert annað í henni.

137
00:06:33,110 --> 00:06:36,020
Svo allt 10 af þeim
ábendingum benda á núll.

138
00:06:36,020 --> 00:06:38,090
Það er það sem rauður gefur til kynna.

139
00:06:38,090 --> 00:06:39,500
>> Skulum setja band Harvard.

140
00:06:39,500 --> 00:06:41,999
Skulum setja Háskóli
Harvard í þessa Trie, sem

141
00:06:41,999 --> 00:06:43,940
var stofnað árið 1636.

142
00:06:43,940 --> 00:06:48,220
Við viljum nota takkann,
1636, til að segja okkur hvar við erum

143
00:06:48,220 --> 00:06:50,140
að geyma Harvard í Trie.

144
00:06:50,140 --> 00:06:51,470
Nú, hvernig getum við gert það?

145
00:06:51,470 --> 00:06:52,886
>> Það gæti litið eitthvað svona.

146
00:06:52,886 --> 00:06:54,160
Við byrjum á rót.

147
00:06:54,160 --> 00:06:56,920
Og við höfum þessar 10 staði sem við getum farið.

148
00:06:56,920 --> 00:06:59,900
Rótin er bara eins og allir
annað hnút á Trie.

149
00:06:59,900 --> 00:07:02,850
Það eru 10 staðir sem við getum farið héðan.

150
00:07:02,850 --> 00:07:07,215
>> Hvert viljum við sennilega
að fara ef lykillinn er 1636?

151
00:07:07,215 --> 00:07:08,340
Það er í raun tveir valkostir.

152
00:07:08,340 --> 00:07:08,450
Hægri.

153
00:07:08,450 --> 00:07:10,825
Við getum byggt lykil af
hægri til vinstri og byrja með 6.

154
00:07:10,825 --> 00:07:14,000
Eða við gætum byggt lykil af
frá vinstri til hægri og byrja með 1.

155
00:07:14,000 --> 00:07:16,140
>> Það er líklega meira
innsæi sem manneskju

156
00:07:16,140 --> 00:07:18,110
að skilja við munum
bara fara til vinstri til hægri.

157
00:07:18,110 --> 00:07:21,140
Og svo ef ég vil setja
Harvard í þessa Trie,

158
00:07:21,140 --> 00:07:23,560
Ég vil líklega að byrja
með því að byrja á rót,

159
00:07:23,560 --> 00:07:25,720
horfa á 10 valkostum mínum
fyrir framan mig, og sagði

160
00:07:25,720 --> 00:07:28,700
Ég vil fara niður 1 braut.

161
00:07:28,700 --> 00:07:29,700
OK.

162
00:07:29,700 --> 00:07:31,810
>> Nú, 1 leið er nú null.

163
00:07:31,810 --> 00:07:35,920
Þannig að ef ég vil halda áfram niður þennan veg
að setja þennan þátt í Trie,

164
00:07:35,920 --> 00:07:42,040
Ég verð að malloc nýja hnút, hafa 1
benda þar, og þá er ég góður að fara.

165
00:07:42,040 --> 00:07:46,460
>> Þannig að ég er í grundvallaratriðum á a
lið þar sem ég stend

166
00:07:46,460 --> 00:07:50,270
á rót trésins eða á
Trie og það eru 10 útibú.

167
00:07:50,270 --> 00:07:52,260
En hvert útibú hefur
hliðið fyrir framan það.

168
00:07:52,260 --> 00:07:53,060
Hægri.

169
00:07:53,060 --> 00:07:54,850
Vegna þess að það er ekkert annað er þarna.

170
00:07:54,850 --> 00:07:56,522
Engin örugga leið.

171
00:07:56,522 --> 00:07:58,980
Það þýðir að það er ekkert
niður eitthvað af þessum greinum.

172
00:07:58,980 --> 00:08:02,532
Ef ég vil byrja að byggja
eitthvað, ég vil fjarlægja hliðið.

173
00:08:02,532 --> 00:08:04,490
Mig langar að fjarlægja hliðið
framan númer 1.

174
00:08:04,490 --> 00:08:05,698
Og ég vil ganga niður að.

175
00:08:05,698 --> 00:08:08,060
Og ég vil að byggja
annar staður fyrir mig að fara.

176
00:08:08,060 --> 00:08:09,470
>> Og það er það sem ég hef gert hér.

177
00:08:09,470 --> 00:08:11,430
Svo 1 ekki lengur bendir á núll.

178
00:08:11,430 --> 00:08:13,830
Ég hef sagt að það er óhætt að fara niður hér núna.

179
00:08:13,830 --> 00:08:15,789
Ég byggði annað hnút.

180
00:08:15,789 --> 00:08:18,330
Og þegar ég fæ að hnút, ég
hafa annað ákvörðun að gera.

181
00:08:18,330 --> 00:08:20,890
Hvert er ég að fara að fara héðan?

182
00:08:20,890 --> 00:08:22,700
>> Jæja, ég hef nú þegar farið niður 1.

183
00:08:22,700 --> 00:08:24,470
Svo nú vil ég sennilega að fara niður 6.

184
00:08:24,470 --> 00:08:24,970
Hægri.

185
00:08:24,970 --> 00:08:27,100
Aftur, ég hef 10 staði ég get valið.

186
00:08:27,100 --> 00:08:30,060
Svo skulum við fara núna niður númer 6.

187
00:08:30,060 --> 00:08:32,280
Svo ég hreinsa hliðið
fyrir framan númer 6.

188
00:08:32,280 --> 00:08:33,250
Og ég geng þarna niðri.

189
00:08:33,250 --> 00:08:34,580
Og ég byggja annan hnút.

190
00:08:34,580 --> 00:08:37,630
Og ég hef náð annað mótum lið.

191
00:08:37,630 --> 00:08:40,289
>> Aftur, ég hef 10 val
fyrir þar sem ég get farið.

192
00:08:40,289 --> 00:08:42,799
Ég hef flutt frá 1 til 6.

193
00:08:42,799 --> 00:08:44,215
Svo nú vil ég líklega að fara í 3.

194
00:08:44,215 --> 00:08:45,381
3, það er hvergi ég get farið.

195
00:08:45,381 --> 00:08:48,980
Svo ég verð að ryðja brautina
og byggja mér nýtt rúm.

196
00:08:48,980 --> 00:08:50,870
Og þá frá 3, þar sem ég vil fara?

197
00:08:50,870 --> 00:08:52,450
Ég vil fara niður 6.

198
00:08:52,450 --> 00:08:54,770
>> Og aftur, ég þurfti að
hreinsa leið til að gera það.

199
00:08:54,770 --> 00:08:59,179
Svo nú hef ég notað lykil til að setja búa
hnútar og byrja að byggja þessa Trie.

200
00:08:59,179 --> 00:09:00,220
Ég hef byrjað á rót.

201
00:09:00,220 --> 00:09:03,666
Ég hef farið niður 1636.

202
00:09:03,666 --> 00:09:05,540
Og nú er ég neðst
þar á hnút.

203
00:09:05,540 --> 00:09:06,610
Og þú might vera fær til
sjá það á skjánum.

204
00:09:06,610 --> 00:09:07,735
>> Það er auðkenndur með gulum.

205
00:09:07,735 --> 00:09:10,020
Það er þar sem ég er nú.

206
00:09:10,020 --> 00:09:11,300
Lykill er gert.

207
00:09:11,300 --> 00:09:13,030
Ég hef búinn hvert stöðu lykillinn minn.

208
00:09:13,030 --> 00:09:15,040
Svo ég get ekki farið lengra.

209
00:09:15,040 --> 00:09:17,720
Svo á þessum tímapunkti, allt sem ég
þarf virkilega að gera er að segja, OK.

210
00:09:17,720 --> 00:09:18,990
Það er góður af eins og að leita
niður á jörðina,

211
00:09:18,990 --> 00:09:21,115
ef þú ert envisioning
sjálfur eins þessa tegund af braut

212
00:09:21,115 --> 00:09:22,350
með mismunandi tengingar.

213
00:09:22,350 --> 00:09:25,800
Raða af að horfa niður og svoleiðis
úða mála Harvard á jörðinni.

214
00:09:25,800 --> 00:09:26,800
Það er nafnið á þessu.

215
00:09:26,800 --> 00:09:28,300
Veit það er það sem er á þessum stað.

216
00:09:28,300 --> 00:09:31,870
Ef við byrjum á rót og við förum niður
1 og síðan 6 og síðan 3 og þá 6,

217
00:09:31,870 --> 00:09:32,780
hvar erum við?

218
00:09:32,780 --> 00:09:35,640
Jæja, ef við lítum niður
og við sjáum Harvard, þá

219
00:09:35,640 --> 00:09:38,960
við vitum að Harvard var
stofnað árið 1636 byggt á leiðinni

220
00:09:38,960 --> 00:09:41,400
við erum að innleiða þessa gögn uppbygging.

221
00:09:41,400 --> 00:09:43,177
Svo það var vonandi einfalt.

222
00:09:43,177 --> 00:09:44,760
Við erum að fara að gera tvær ísetningar.

223
00:09:44,760 --> 00:09:50,060
Og vonandi að það mun hjálpa til
sjá þetta gert tvisvar í viðbót.

224
00:09:50,060 --> 00:09:52,210
>> Nú, við skulum setja annað háskóla.

225
00:09:52,210 --> 00:09:54,630
Skulum setja Yale inn í þennan Trie.

226
00:09:54,630 --> 00:09:57,037
Yale var stofnað árið 1701.

227
00:09:57,037 --> 00:09:58,870
Þannig að við munum byrja á því
rót, eins og við gerum alltaf.

228
00:09:58,870 --> 00:09:59,890
Og við setjum upp Traversal músina.

229
00:09:59,890 --> 00:10:01,624
Við erum að fara að nota það til að fara í gegnum.

230
00:10:01,624 --> 00:10:03,790
The fyrstur hlutur sem við viljum
gera er að fara niður á 1 braut.

231
00:10:03,790 --> 00:10:05,830
Það er fyrsta talan lykill okkar.

232
00:10:05,830 --> 00:10:08,420
Sem betur fer, þó, er það ekki
þarft að gera allir vinna í þetta sinn.

233
00:10:08,420 --> 00:10:09,919
The 1 leið hefur þegar verið eytt.

234
00:10:09,919 --> 00:10:13,520
Ég ruddi það áður þegar ég
var að setja Harvard á 1636.

235
00:10:13,520 --> 00:10:18,090
Svo ég get örugglega færa
niður 1 og bara fara þangað.

236
00:10:18,090 --> 00:10:20,150
Ef hægt að færa niður 1.

237
00:10:20,150 --> 00:10:22,930
>> Nú, þó, ég vil fara til 7.

238
00:10:22,930 --> 00:10:24,280
Ég ruddi brautina á 6.

239
00:10:24,280 --> 00:10:27,050
Ég veit að ég get örugglega
áfram niður 6 braut.

240
00:10:27,050 --> 00:10:29,220
En ég þarf að halda áfram á 7 braut.

241
00:10:29,220 --> 00:10:30,580
Svo hvað þarf ég að gera?

242
00:10:30,580 --> 00:10:35,070
Jæja, bara eins og áður, ég þarf bara
að hreinsa hliðið, fá út af the vegur,

243
00:10:35,070 --> 00:10:38,740
og byggja nýja hnút úr 7 braut.

244
00:10:38,740 --> 00:10:40,250
Bara svona.

245
00:10:40,250 --> 00:10:42,930
>> Svo nú er ég hef flutt á 1 og síðan 7.

246
00:10:42,930 --> 00:10:45,550
Og nú eftir, ég er svona
af á þessum nýja subbranch.

247
00:10:45,550 --> 00:10:46,050
Hægri.

248
00:10:46,050 --> 00:10:49,260
Allt annað frá 16
á, ég hugsa ekki um.

249
00:10:49,260 --> 00:10:50,720
Ég ætla ekki að gera 16 neitt.

250
00:10:50,720 --> 00:10:51,750
Ég er að gera 17 efni.

251
00:10:51,750 --> 00:10:58,380
>> Svo nú úr 17 á, ég verð að
konar ótroðnar slóðir hér.

252
00:10:58,380 --> 00:11:00,462
Næsta stafa lykillinn minn er 0.

253
00:11:00,462 --> 00:11:01,670
Ég greinilega getur ekki fá neitt.

254
00:11:01,670 --> 00:11:02,628
Ég byggði bara þennan hnút.

255
00:11:02,628 --> 00:11:04,550
Þannig að ég veit að það er engin
slóðir áfram héðan.

256
00:11:04,550 --> 00:11:06,370
Svo ég verð að gera einn sjálfur.

257
00:11:06,370 --> 00:11:09,360
>> Svo ég malloc nýja hnút
og hafa 0 tímapunkti.

258
00:11:09,360 --> 00:11:12,770
Og svo er eitt skipti, malloc I a
Ný hnút og hafa eitt stig þar.

259
00:11:12,770 --> 00:11:15,870
Aftur, ég hef búinn lykil, 1701.

260
00:11:15,870 --> 00:11:18,472
Svo ég lít niður og ég úða mála Yale.

261
00:11:18,472 --> 00:11:19,680
Það er nafn þessarar hnút.

262
00:11:19,680 --> 00:11:24,660
>> Og svo nú ef ég þarf alltaf að sjá hvort Yale
er í þessum Trie, byrja ég á rót,

263
00:11:24,660 --> 00:11:27,060
Ég fer niður 1701, og líta niður.

264
00:11:27,060 --> 00:11:30,030
Og ef ég sé Yale úða
máluð á jörðu, þá

265
00:11:30,030 --> 00:11:32,200
Ég veit Yale til í þessum Trie.

266
00:11:32,200 --> 00:11:32,950
Við skulum gera eitt.

267
00:11:32,950 --> 00:11:36,430
Skulum setja Dartmouth í þetta
Trie, sem var stofnað árið 1769.

268
00:11:36,430 --> 00:11:37,750
>> Byrja á rót aftur.

269
00:11:37,750 --> 00:11:39,445
Fyrsta stafa minn lykillinn minn er 1.

270
00:11:39,445 --> 00:11:40,820
Ég get örugglega fara niður þennan veg.

271
00:11:40,820 --> 00:11:42,400
Það er nú þegar til.

272
00:11:42,400 --> 00:11:44,040
Næsta stafa af lykillinn minn er 7.

273
00:11:44,040 --> 00:11:45,890
Ég get örugglega fara niður þennan veg.

274
00:11:45,890 --> 00:11:47,540
Það er eins og heilbrigður.

275
00:11:47,540 --> 00:11:49,000
>> Næsta minn er 6.

276
00:11:49,000 --> 00:11:52,860
Héðan frá þar sem ég er núna að
í gulu þarna í miðjum hnút,

277
00:11:52,860 --> 00:11:56,060
6 er nú læst burt.

278
00:11:56,060 --> 00:11:58,830
Ef ég vil fara niður þennan veg,
Ég verð að byggja það sjálfur.

279
00:11:58,830 --> 00:12:02,250
Þannig að ég ætla malloc nýja hnút
og hafa 6 stig þar.

280
00:12:02,250 --> 00:12:04,250
Og þá aftur, ég er
logi nýjar slóðir hér.

281
00:12:04,250 --> 00:12:10,750
>> Svo ég malloc nýja hnút þannig að frá
sem node-- slóð tala 9-- og þá nú

282
00:12:10,750 --> 00:12:13,584
ef ég ferðast 1769, og ég lít niður.

283
00:12:13,584 --> 00:12:15,500
Það er ekkert eins
úða mála þar.

284
00:12:15,500 --> 00:12:16,930
Ég get skrifað Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Og ég hef sett
Dartmouth í Trie.

286
00:12:20,710 --> 00:12:23,450
>> Svo er það að setja
það voru Trie.

287
00:12:23,450 --> 00:12:25,384
Nú viljum við að leita að hlutum.

288
00:12:25,384 --> 00:12:27,050
Hvernig eigum við að leita að hlutum í Trie?

289
00:12:27,050 --> 00:12:29,170
Jæja, það er ansi mikið það sama.

290
00:12:29,170 --> 00:12:33,620
Nú notum bara tölustafi takkann
til að sjá hvort við getum sigla frá rót

291
00:12:33,620 --> 00:12:37,170
þar sem við viljum fara í Trie.

292
00:12:37,170 --> 00:12:41,620
>> Ef við högg dauður endi á hverjum stað, þá
við vitum að þessi þáttur er ekki til staðar

293
00:12:41,620 --> 00:12:44,500
eða annað sem leið myndi
hafa þegar verið eytt.

294
00:12:44,500 --> 00:12:45,930
Ef við tökum það alla leið til
enda, allt sem við þurfum að gera

295
00:12:45,930 --> 00:12:48,471
er að líta niður og sjá hvort það er
þátturinn sem við erum að leita að.

296
00:12:48,471 --> 00:12:49,335
Ef það er, velgengni.

297
00:12:49,335 --> 00:12:52,610
Ef það er ekki, mistakast.

298
00:12:52,610 --> 00:12:54,940
>> Svo skulum leita
Harvard í þessu Trie.

299
00:12:54,940 --> 00:12:56,020
Við byrjum á rót.

300
00:12:56,020 --> 00:12:58,228
Og aftur, við erum að fara að
búa til Traversal músina

301
00:12:58,228 --> 00:12:59,390
að gera hreyfingar okkar fyrir okkur.

302
00:12:59,390 --> 00:13:02,080
Frá rót og við vitum að
Fyrsti staðurinn sem við þurfum að fara er 1,

303
00:13:02,080 --> 00:13:03,390
getum við gert það?

304
00:13:03,390 --> 00:13:03,982
Já við getum.

305
00:13:03,982 --> 00:13:04,690
Ef örugglega til.

306
00:13:04,690 --> 00:13:06,660
Við getum farið þangað.

307
00:13:06,660 --> 00:13:08,440
>> Nú er næsta stað sem við þurfum að fara er 6.

308
00:13:08,440 --> 00:13:10,557
Er 6 leið til hér?

309
00:13:10,557 --> 00:13:11,140
Já, er það.

310
00:13:11,140 --> 00:13:12,690
Við getum farið niður 6 braut.

311
00:13:12,690 --> 00:13:13,905
Og við á endanum hér.

312
00:13:13,905 --> 00:13:16,130
>> Við getum farið niður 3 leið frá hér?

313
00:13:16,130 --> 00:13:18,450
Jæja, eins og það kemur í ljós,
já, það er til líka.

314
00:13:18,450 --> 00:13:20,790
Og við getum fengið á 6 leið frá hér?

315
00:13:20,790 --> 00:13:21,982
Já við getum.

316
00:13:21,982 --> 00:13:24,002
>> Við höfum ekki alveg svarað
spurningin enn.

317
00:13:24,002 --> 00:13:25,710
Það er enn eitt
skref, sem er nú

318
00:13:25,710 --> 00:13:28,520
við þurfum að líta niður og
sjá hvort það er actually--

319
00:13:28,520 --> 00:13:32,660
ef við erum að leita að Harvard, er að
hvað er að finna eftir að við útblástur takkann?

320
00:13:32,660 --> 00:13:35,430
Í dæminu sem við erum að nota hér,
árin eru alltaf fjórir tölustafir.

321
00:13:35,430 --> 00:13:40,280
En þú gætir verið að nota td þegar
þú ert að geyma orðabók yfir orð.

322
00:13:40,280 --> 00:13:44,060
>> Og svo í stað þess að hafa 10 ábendingum
fyrir staðsetningu mína, þú might hafa 26.

323
00:13:44,060 --> 00:13:46,040
Einn fyrir hvern staf í stafrófinu.

324
00:13:46,040 --> 00:13:50,350
Og það eru nokkur orð eins og kylfu,
sem er hluti af lotu, til dæmis.

325
00:13:50,350 --> 00:13:53,511
Og svo jafnvel ef þú færð til
endir af the lykill og þú lítur niður,

326
00:13:53,511 --> 00:13:55,260
þú getur ekki séð hvað
þú ert að leita að.

327
00:13:55,260 --> 00:13:58,500
>> Þannig að þú þarft alltaf að fara yfir
allt leið og þá

328
00:13:58,500 --> 00:14:01,540
ef þú værir með góðum árangri fær
til að fara yfir allt leið,

329
00:14:01,540 --> 00:14:03,440
líta niður og gera eitt endanlega staðfestingu.

330
00:14:03,440 --> 00:14:05,120
Er það það sem ég er að leita að?

331
00:14:05,120 --> 00:14:07,740
Jæja, ég lít niður eftir að byrja
efst og fara 1636.

332
00:14:07,740 --> 00:14:08,240
Ég lít niður.

333
00:14:08,240 --> 00:14:09,400
Ég sé Harvard.

334
00:14:09,400 --> 00:14:11,689
Svo, já, tók ég.

335
00:14:11,689 --> 00:14:13,980
Hvað ef það sem ég er að leita að
er ekki í Trie, þó.

336
00:14:13,980 --> 00:14:17,200
Hvað ef ég er að leita að Princeton,
sem var stofnað árið 1746.

337
00:14:17,200 --> 00:14:20,875
Og svo 1746 verður lykillinn minn
að fletta í gegnum Trie.

338
00:14:20,875 --> 00:14:22,040
Jæja, byrja ég á rót.

339
00:14:22,040 --> 00:14:24,760
Og í fyrsta sæti sem ég vil
að fer niður 1 braut.

340
00:14:24,760 --> 00:14:25,590
Get ég gert það?

341
00:14:25,590 --> 00:14:26,490
Já ég get.

342
00:14:26,490 --> 00:14:28,730
>> Get ég farið niður 7 leið þaðan?

343
00:14:28,730 --> 00:14:29,230
Já, ég get.

344
00:14:29,230 --> 00:14:30,750
Sem er til staðar líka.

345
00:14:30,750 --> 00:14:32,460
En get ég farið niður 4 leið frá hér?

346
00:14:32,460 --> 00:14:35,550
Það er eins og að spyrja spurningu, getur
Ég að halda áfram niður að lítill ferningur

347
00:14:35,550 --> 00:14:37,114
sem ég hef bent á gula?

348
00:14:37,114 --> 00:14:38,030
Það er ekkert þar.

349
00:14:38,030 --> 00:14:38,610
Hægri.

350
00:14:38,610 --> 00:14:41,310
>> Það er engin leið fram niður 4 braut.

351
00:14:41,310 --> 00:14:46,480
Ef Princeton var í þessum Trie, sem 4
hefði verið eytt fyrir okkur nú þegar.

352
00:14:46,480 --> 00:14:49,130
Og svo á þessum tímapunkti
við höfum náð dauðum enda.

353
00:14:49,130 --> 00:14:50,250
Við getum ekki farið lengra.

354
00:14:50,250 --> 00:14:53,440
Og svo við getum sagt, endanlega, nr.

355
00:14:53,440 --> 00:14:56,760
Princeton er ekki til í þessum Trie.

356
00:14:56,760 --> 00:14:58,860
>> Svo hvað þýðir þetta allt þýðir?

357
00:14:58,860 --> 00:14:59,360
Hægri.

358
00:14:59,360 --> 00:15:01,000
Það er mikið um að vera hér.

359
00:15:01,000 --> 00:15:02,500
Það er ábendingum um allan stað.

360
00:15:02,500 --> 00:15:04,249
Og, eins og þú sérð
bara af myndinni,

361
00:15:04,249 --> 00:15:07,010
það er mikið af hnúður sem
eru eins konar fljúga í kring.

362
00:15:07,010 --> 00:15:13,480
En taka hvert skipti sem við vildum að
athuga hvort eitthvað var í Trie,

363
00:15:13,480 --> 00:15:15,000
við þurftum aðeins að gera 4 hreyfingar.

364
00:15:15,000 --> 00:15:17,208
>> Í hvert skipti sem við vildum að
setja eitthvað í Trie,

365
00:15:17,208 --> 00:15:20,440
við verðum að gera 4 færist hugsanlega
mallocing smá dót á leiðinni.

366
00:15:20,440 --> 00:15:23,482
En eins og við sáum þegar við bætist
Dartmouth í Trie,

367
00:15:23,482 --> 00:15:25,940
stundum sumir af þeirri braut
gæti þegar verið eytt fyrir okkur.

368
00:15:25,940 --> 00:15:30,520
Og svo eins og Trie okkar fær stærri og
stærri, höfum við gert minna vinna í hvert skipti

369
00:15:30,520 --> 00:15:32,270
að setja nýja hluti
vegna þess að við höfum nú þegar

370
00:15:32,270 --> 00:15:35,746
byggt mikið af millistig
Útibú leiðinni.

371
00:15:35,746 --> 00:15:38,370
Ef við höfum bara alltaf að horfa á
4 hlutir, 4 er bara stöðug.

372
00:15:38,370 --> 00:15:41,750
Við raunverulega eru konar nálgast
stöðug tími innsetningu

373
00:15:41,750 --> 00:15:44,501
og stöðug tími útlit.

374
00:15:44,501 --> 00:15:47,500
The tradeoff, að sjálfsögðu, að vera að
þetta Trie, eins og þú geta sennilega sagt,

375
00:15:47,500 --> 00:15:49,030
er mikil.

376
00:15:49,030 --> 00:15:51,040
Hver einn af þessum hnúður
tekur upp mikið pláss.

377
00:15:51,040 --> 00:15:52,090
>> En það er tradeoff.

378
00:15:52,090 --> 00:15:55,260
Ef við viljum virkilega fljótur
innsetning, mjög fljótur eyðingu,

379
00:15:55,260 --> 00:15:59,630
og mjög fljótur útlit, verðum við að
hafa mikið af gögnum að fljúga í kring.

380
00:15:59,630 --> 00:16:03,590
Við verðum að leggja til hliðar mikið pláss
og minni fyrir það gögn uppbygging

381
00:16:03,590 --> 00:16:04,290
að vera til.

382
00:16:04,290 --> 00:16:05,415
>> Og svo er að tradeoff.

383
00:16:05,415 --> 00:16:07,310
En það lítur út eins og við
gæti hafa fundið það.

384
00:16:07,310 --> 00:16:09,560
Við gætum hafa komist að því að
Gral gögn uppbygging

385
00:16:09,560 --> 00:16:12,264
með fljótur ísetningu
eyðingu, og útlit.

386
00:16:12,264 --> 00:16:14,430
Og kannski þetta verður
viðeigandi gögn uppbygging

387
00:16:14,430 --> 00:16:18,890
að nota fyrir hvaða upplýsingar
við erum að reyna að geyma.

388
00:16:18,890 --> 00:16:21,860
Ég er Doug Lloyd, þetta er CS50.

389
00:16:21,860 --> 00:16:23,433