1
00:00:00,000 --> 00:00:02,994
>> [MUSIK SPELA]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Så vi har inching närmare
och närmare den heliga graal av data

4
00:00:08,550 --> 00:00:13,050
strukturer, som vi kan sätta in
in, radera från, och slå upp

5
00:00:13,050 --> 00:00:15,440
i konstant tid.

6
00:00:15,440 --> 00:00:16,270
Höger.

7
00:00:16,270 --> 00:00:17,280
Det är typ av målet.

8
00:00:17,280 --> 00:00:19,720
Vi vill kunna göra
saker mycket, mycket snabbt.

9
00:00:19,720 --> 00:00:22,580
>> Har vi hittade det här när
vi pratar om försök?

10
00:00:22,580 --> 00:00:23,670
Nåväl, låt oss ta en titt.

11
00:00:23,670 --> 00:00:25,628
Så vi har sett flera
olika datastrukturer

12
00:00:25,628 --> 00:00:28,680
att hantera mappningen av
så kallad nyckel-par,

13
00:00:28,680 --> 00:00:32,080
kartläggning viss bit data
till någon annan bit data

14
00:00:32,080 --> 00:00:36,020
så vi vet var man kan hitta
uppgifter i strukturen.

15
00:00:36,020 --> 00:00:40,060
>> Så för matris, till exempel, den
Nyckeln är elementet index eller array

16
00:00:40,060 --> 00:00:42,600
läge 0 eller matrisen en och så vidare.

17
00:00:42,600 --> 00:00:46,140
Och värdet är data
som existerar på den platsen.

18
00:00:46,140 --> 00:00:48,550
Så vad som lagras i uppsättningen 0?

19
00:00:48,550 --> 00:00:54,290
Vad lagras i uppsättningen 1 kontra bara
0 och 1, vilket skulle vara nycklarna.

20
00:00:54,290 --> 00:00:56,360
>> Med en hash-tabell är det
slags samma idé.

21
00:00:56,360 --> 00:01:00,690
Med en hash bord, har vi denna hash
funktion som genererar hash-koder.

22
00:01:00,690 --> 00:01:03,670
Så nyckeln är hash-kod av uppgifterna.

23
00:01:03,670 --> 00:01:06,530
Och värdet, särskilt
Vi pratade om kedja

24
00:01:06,530 --> 00:01:10,590
i videon på hashtabeller,
är att länkad lista data

25
00:01:10,590 --> 00:01:12,550
som hashar till den hashkod.

26
00:01:12,550 --> 00:01:14,050
Höger.

27
00:01:14,050 --> 00:01:16,050
Vad sägs om en annan metod
denna metod, men?

28
00:01:16,050 --> 00:01:21,000
Vad sägs om en metod där
nyckeln är garanterad att vara unik,

29
00:01:21,000 --> 00:01:25,410
till skillnad från en hash-tabell, där vi kunde
sluta med två datadelar

30
00:01:25,410 --> 00:01:27,200
har samma hashkod.

31
00:01:27,200 --> 00:01:30,020
Och då måste vi ta itu med
att genom antingen sondering eller mer

32
00:01:30,020 --> 00:01:33,340
företrädesvis kedja för att åtgärda problemet.

33
00:01:33,340 --> 00:01:37,520
>> Så nu kan vi garantera
att vår nyckel kommer att vara unik.

34
00:01:37,520 --> 00:01:39,690
Och vad händer om vårt värde var
bara något som lätt

35
00:01:39,690 --> 00:01:44,080
så sant och falskt som berättar om
eller inte denna del av information

36
00:01:44,080 --> 00:01:45,610
existerar i strukturen?

37
00:01:45,610 --> 00:01:48,180
Ett booleskt kan vara så enkelt som en bit.

38
00:01:48,180 --> 00:01:52,660
Realistiskt är det förmodligen en
BYTE mer sannolikt än en bit.

39
00:01:52,660 --> 00:01:55,410
Men det är mycket mindre än
lagring kanske en 50-teckensträng,

40
00:01:55,410 --> 00:01:57,360
till exempel.

41
00:01:57,360 --> 00:02:02,210
>> Så försök, liknande hash tabeller,
som kombinerar arrayer och länkad lista,

42
00:02:02,210 --> 00:02:05,790
försöker kombinera arrayer,
strukturer, och pekare

43
00:02:05,790 --> 00:02:08,509
tillsammans för att lagra data i
ett intressant sätt som är

44
00:02:08,509 --> 00:02:11,550
ganska annorlunda från
något vi har sett hittills.

45
00:02:11,550 --> 00:02:16,750
Nu använder vi uppgifterna som en färdplan
att navigera denna datastruktur.

46
00:02:16,750 --> 00:02:18,710
Och om vi kan följa
färdplanen, om vi kan

47
00:02:18,710 --> 00:02:22,390
följ data från
början till slut, vi ska

48
00:02:22,390 --> 00:02:24,945
veta om dessa uppgifter
existerar i trie.

49
00:02:24,945 --> 00:02:28,310
>> Och om vi inte kan följa kartan
från betyder att sluta på alla,

50
00:02:28,310 --> 00:02:30,600
data kan inte existera.

51
00:02:30,600 --> 00:02:32,890
Återigen, nycklarna här är
garanterat att vara unik.

52
00:02:32,890 --> 00:02:36,020
Och så till skillnad från en hash-tabell, vi ska aldrig
måste ta itu med kollisioner här.

53
00:02:36,020 --> 00:02:39,090
Och ingen två bitar av uppgifter
har exakt samma färdplan

54
00:02:39,090 --> 00:02:40,530
såvida dessa uppgifter är identiska.

55
00:02:40,530 --> 00:02:44,580
>> Om vi ​​sätter John, sedan
vi söker för John.

56
00:02:44,580 --> 00:02:47,430
Det är två identiska bitar av
uppgifter, rätt, vi letar igenom.

57
00:02:47,430 --> 00:02:49,880
Men annars, alla
två bitar av data

58
00:02:49,880 --> 00:02:52,750
garanterat att ha unika färdplaner
genom denna datastruktur.

59
00:02:52,750 --> 00:02:56,210
Och vi kommer att ta en titt på
en visuell av detta på bara ett ögonblick.

60
00:02:56,210 --> 00:02:58,810
>> Vi gör detta genom att försöka
skapa en ny datastruktur,

61
00:02:58,810 --> 00:03:00,564
kartläggning av följande nyckelpar värde.

62
00:03:00,564 --> 00:03:03,480
I det här fallet, vi kommer inte att använda
något så enkelt som en Boolean.

63
00:03:03,480 --> 00:03:06,200
Vi faktiskt kommer att lagra strängen.

64
00:03:06,200 --> 00:03:08,690
Och det sträng kommer att
vara namnet på ett universitet.

65
00:03:08,690 --> 00:03:12,140
>> Och nyckeln kommer att bli året
när det universitetet grundades.

66
00:03:12,140 --> 00:03:15,380
Alla år för universiteten
kommer att vara fyra siffror.

67
00:03:15,380 --> 00:03:19,840
Och så vi kommer att använda dessa fyra siffrorna till
navigera genom denna datastruktur.

68
00:03:19,840 --> 00:03:22,270
Och vi får se, återigen, hur
vi gör det på bara en sekund.

69
00:03:22,270 --> 00:03:25,110
>> Vid slutet av banan,
vi får se namnet

70
00:03:25,110 --> 00:03:30,250
av universitetet som motsvarar
till nyckeln dessa fyra siffror.

71
00:03:30,250 --> 00:03:34,390
Den grundläggande idén bakom en trie
är att vi har en central rutt.

72
00:03:34,390 --> 00:03:35,640
Så tänk på det som ett träd.

73
00:03:35,640 --> 00:03:39,211
Och det är lika i stavning
och koncept som ett träd.

74
00:03:39,211 --> 00:03:41,460
Generellt när vi tänker på
träd i den verkliga världen,

75
00:03:41,460 --> 00:03:44,090
de har en rot som är i
mark och de växer uppåt

76
00:03:44,090 --> 00:03:46,830
och de har filialer
och de har blad.

77
00:03:46,830 --> 00:03:49,450
Och i princip idén om
en trie är exakt densamma,

78
00:03:49,450 --> 00:03:51,755
med undantag av att rot är förankrad
någonstans på himlen.

79
00:03:51,755 --> 00:03:53,130
Och bladen är i botten.

80
00:03:53,130 --> 00:03:55,750
>> Så det är ungefär som att ta ett träd
och bara vända den upp och ner.

81
00:03:55,750 --> 00:03:56,880
Men det finns fortfarande grenar.

82
00:03:56,880 --> 00:03:59,463
Och de skulle vara våra vägar,
de kommer att vara våra kontakter

83
00:03:59,463 --> 00:04:02,220
från roten till bladen.

84
00:04:02,220 --> 00:04:04,200
I det här fallet, de
vägar, de grenar

85
00:04:04,200 --> 00:04:08,490
är märkta med siffror som berättar
vilken väg att gå från där vi är.

86
00:04:08,490 --> 00:04:11,800
>> Om vi ​​ser en 0, vi går ner denna gren,
om vi ser en 1, vi går ner denna gren,

87
00:04:11,800 --> 00:04:12,900
och så och så vidare.

88
00:04:12,900 --> 00:04:14,060
Tja, vad innebär det?

89
00:04:14,060 --> 00:04:16,519
Tja, innebär det att
vid varje förbindelsepunkten

90
00:04:16,519 --> 00:04:19,260
och varje nod i
mitten och varje gren,

91
00:04:19,260 --> 00:04:23,020
Det finns 10 möjliga
platser som vi kan gå.

92
00:04:23,020 --> 00:04:27,690
Så det finns 10 pekare
från varje plats.

93
00:04:27,690 --> 00:04:30,610
>> Och det är där försök kan få en
lite skrämmande för någon

94
00:04:30,610 --> 00:04:34,460
som är inte har en hel del
erfarenhet av datavetenskap innan.

95
00:04:34,460 --> 00:04:35,960
Men försök är verkligen ganska häftigt.

96
00:04:35,960 --> 00:04:37,793
Och om du har
möjlighet att arbeta med dem

97
00:04:37,793 --> 00:04:40,420
och du är villig att gräva in
och experimentera med dem,

98
00:04:40,420 --> 00:04:44,234
de är egentligen ganska intressant
datastrukturer att arbeta med.

99
00:04:44,234 --> 00:04:46,900
Om vi ​​vill infoga ett element
i trie, allt vi behöver göra

100
00:04:46,900 --> 00:04:51,360
är att bygga den rätta vägen
från roten till bladet.

101
00:04:51,360 --> 00:04:55,390
Här är vad varje steg längs
hur kan se ut.

102
00:04:55,390 --> 00:04:59,660
Vi kommer att definiera ett nytt data
struktur för en ny nod som kallas en trie.

103
00:04:59,660 --> 00:05:02,560
>> Och inne av dessa uppgifter
struktur finns två stycken.

104
00:05:02,560 --> 00:05:05,460
Vi kommer att lagra
namn på ett universitet.

105
00:05:05,460 --> 00:05:09,410
Och vi kommer att lagra
en array av pekare

106
00:05:09,410 --> 00:05:12,190
till andra noder av samma typ.

107
00:05:12,190 --> 00:05:14,780
Så, återigen, det är den sortens
av begreppet överallt

108
00:05:14,780 --> 00:05:18,567
vi är, vi på 10 möjliga
platser vi kan gå.

109
00:05:18,567 --> 00:05:20,150
Om vi ​​ser en 0, vi går ner denna gren.

110
00:05:20,150 --> 00:05:22,690
Om vi ​​ser en 1, denna gren,
och så vidare och så vidare och så vidare.

111
00:05:22,690 --> 00:05:25,160
Om vi ​​säger 9, vi går ner denna gren.

112
00:05:25,160 --> 00:05:28,220
Så vid varje knutpunkt,
vi kan gå 10 möjliga platser.

113
00:05:28,220 --> 00:05:35,740
Så varje nod måste innehålla 10 pekare
till andra noder, till 10 andra noder.

114
00:05:35,740 --> 00:05:39,810
>> Och data vi lagrar är
bara namnet på universitetet.

115
00:05:39,810 --> 00:05:41,060
Så låt oss bygga en trie.

116
00:05:41,060 --> 00:05:44,860
Låt oss sätta ett par
artiklar i vår trie.

117
00:05:44,860 --> 00:05:46,740
Så högst upp,
detta är vår rotnoden.

118
00:05:46,740 --> 00:05:49,740
Detta är förmodligen kommer att bli något
du kommer att globalt deklarera.

119
00:05:49,740 --> 00:05:53,450
Och du kommer att globalt upprätthålla
en pekare till denna nod alltid.

120
00:05:53,450 --> 00:05:55,360
>> Du kommer att säga,
rot lika, och du är

121
00:05:55,360 --> 00:05:57,580
kommer att malloc själv trie nod.

122
00:05:57,580 --> 00:05:59,850
Och du kommer aldrig
röra rot igen.

123
00:05:59,850 --> 00:06:02,300
Varje gång du vill
börja navigera igenom,

124
00:06:02,300 --> 00:06:05,802
du ställa in en annan pekare
lika med roten, såsom trav,

125
00:06:05,802 --> 00:06:07,760
vilket är det exempel jag
användning i många av mina videor

126
00:06:07,760 --> 00:06:11,090
här på stackar och köer
och länklistor och så vidare.

127
00:06:11,090 --> 00:06:13,320
>> Du anger en annan pekare
kallas trav för traverse.

128
00:06:13,320 --> 00:06:15,890
Och du använder trav för att navigera
genom datastrukturen.

129
00:06:15,890 --> 00:06:17,500
Så låt oss se hur det kan se ut.

130
00:06:17,500 --> 00:06:19,880
Så just nu, vad
gör en nod ut?

131
00:06:19,880 --> 00:06:22,920
Jo, precis som våra data
struktur förklaring anges,

132
00:06:22,920 --> 00:06:26,906
vi har en sträng, som
i detta fall är tom.

133
00:06:26,906 --> 00:06:27,780
Det finns inget här.

134
00:06:27,780 --> 00:06:29,550
>> Och en mängd 10 pekare.

135
00:06:29,550 --> 00:06:31,790
Och just nu, bara vi
har en nod i denna trie.

136
00:06:31,790 --> 00:06:33,110
Det finns inget annat i den.

137
00:06:33,110 --> 00:06:36,020
Så alla 10 av dem
pekare peka på null.

138
00:06:36,020 --> 00:06:38,090
Det är vad den röda indikerar.

139
00:06:38,090 --> 00:06:39,500
>> Låt oss sätta strängen Harvard.

140
00:06:39,500 --> 00:06:41,999
Låt oss sätta universitet
Harvard in i denna trie, vilket

141
00:06:41,999 --> 00:06:43,940
grundades år 1636.

142
00:06:43,940 --> 00:06:48,220
Vi vill använda nyckeln,
1636, för att tala om för oss där vi är

143
00:06:48,220 --> 00:06:50,140
kommer att Harvard lagra i trie.

144
00:06:50,140 --> 00:06:51,470
Nu, hur kan vi göra det?

145
00:06:51,470 --> 00:06:52,886
>> Det kan se ut så här.

146
00:06:52,886 --> 00:06:54,160
Vi börjar vid roten.

147
00:06:54,160 --> 00:06:56,920
Och vi har dessa 10 platser vi kan gå.

148
00:06:56,920 --> 00:06:59,900
Roten är precis som alla
annan nod i trie.

149
00:06:59,900 --> 00:07:02,850
Det finns 10 platser vi kan gå härifrån.

150
00:07:02,850 --> 00:07:07,215
>> Var gör vi förmodligen vill
att gå om nyckeln är 1636?

151
00:07:07,215 --> 00:07:08,340
Det finns egentligen två alternativ.

152
00:07:08,340 --> 00:07:08,450
Höger.

153
00:07:08,450 --> 00:07:10,825
Vi kan bygga nyckeln från
höger till vänster och börja med 6.

154
00:07:10,825 --> 00:07:14,000
Eller vi kunde bygga nyckeln från
vänster till höger och börjar med ett.

155
00:07:14,000 --> 00:07:16,140
>> Det är nog mer
intuitivt som en människa

156
00:07:16,140 --> 00:07:18,110
att förstå att vi kommer
bara gå till vänster till höger.

157
00:07:18,110 --> 00:07:21,140
Och så om jag vill infoga
Harvard in i denna trie,

158
00:07:21,140 --> 00:07:23,560
Jag vill nog börja
genom att börja vid roten,

159
00:07:23,560 --> 00:07:25,720
titta på mina 10 alternativ
framför mig, och säger

160
00:07:25,720 --> 00:07:28,700
Jag vill gå ner en väg.

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

162
00:07:29,700 --> 00:07:31,810
>> Nu är en väg för närvarande null.

163
00:07:31,810 --> 00:07:35,920
Så om jag vill fortsätta den vägen
att införa detta element i trie,

164
00:07:35,920 --> 00:07:42,040
Jag måste malloc en ny nod, har en
peka där, och så är jag bra att gå.

165
00:07:42,040 --> 00:07:46,460
>> Så jag är i grund och botten på en
punkt där jag står

166
00:07:46,460 --> 00:07:50,270
vid roten av trädet eller
trie och det finns 10 kontor.

167
00:07:50,270 --> 00:07:52,260
Men varje gren har en
grind framför den.

168
00:07:52,260 --> 00:07:53,060
Höger.

169
00:07:53,060 --> 00:07:54,850
Eftersom det finns inget annat finns.

170
00:07:54,850 --> 00:07:56,522
Ingen säker passage.

171
00:07:56,522 --> 00:07:58,980
Det innebär att det finns inget
ner någon av dessa grenar.

172
00:07:58,980 --> 00:08:02,532
Om jag vill börja bygga
något, jag vill ta bort grinden.

173
00:08:02,532 --> 00:08:04,490
Jag vill ta bort grinden
framför nummer ett.

174
00:08:04,490 --> 00:08:05,698
Och jag vill gå ner det.

175
00:08:05,698 --> 00:08:08,060
Och jag vill bygga
en annan plats för mig att gå.

176
00:08:08,060 --> 00:08:09,470
>> Och det är vad jag har gjort här.

177
00:08:09,470 --> 00:08:11,430
Så 1 inte längre pekar på noll.

178
00:08:11,430 --> 00:08:13,830
Jag har sagt att det är säkert att gå här nere nu.

179
00:08:13,830 --> 00:08:15,789
Jag byggde en annan nod.

180
00:08:15,789 --> 00:08:18,330
Och när jag kommer till denna nod, jag
har ett annat beslut att göra.

181
00:08:18,330 --> 00:08:20,890
Vart ska jag gå härifrån?

182
00:08:20,890 --> 00:08:22,700
>> Tja, jag har redan gått ner 1.

183
00:08:22,700 --> 00:08:24,470
Så nu vill jag nog att gå ner 6.

184
00:08:24,470 --> 00:08:24,970
Höger.

185
00:08:24,970 --> 00:08:27,100
Återigen, jag har 10 platser som jag kan välja.

186
00:08:27,100 --> 00:08:30,060
Så låt oss nu gå ner nummer 6.

187
00:08:30,060 --> 00:08:32,280
Så jag rensa porten
framför nummer 6.

188
00:08:32,280 --> 00:08:33,250
Och jag går där nere.

189
00:08:33,250 --> 00:08:34,580
Och jag bygga en annan nod.

190
00:08:34,580 --> 00:08:37,630
Och jag har nått en annan knutpunkt.

191
00:08:37,630 --> 00:08:40,289
>> Återigen, jag har 10 val
för där jag kan gå.

192
00:08:40,289 --> 00:08:42,799
Jag har flyttat 1-6.

193
00:08:42,799 --> 00:08:44,215
Så nu vill jag nog att gå till tre.

194
00:08:44,215 --> 00:08:45,381
3, det finns ingenstans jag kan gå.

195
00:08:45,381 --> 00:08:48,980
Så jag måste bana väg
och bygga mig en ny plats.

196
00:08:48,980 --> 00:08:50,870
Och sedan från 3, där jag vill gå?

197
00:08:50,870 --> 00:08:52,450
Jag vill gå ner 6.

198
00:08:52,450 --> 00:08:54,770
>> Och återigen, jag var tvungen att
bana väg att göra det.

199
00:08:54,770 --> 00:08:59,179
Så nu har jag använt min nyckel för att infoga skapa
noder och börja bygga denna trie.

200
00:08:59,179 --> 00:09:00,220
Jag har börjat vid roten.

201
00:09:00,220 --> 00:09:03,666
Jag har gått ned 1636.

202
00:09:03,666 --> 00:09:05,540
Och nu är jag på botten
där på den noden.

203
00:09:05,540 --> 00:09:06,610
Och du skulle kunna
se den på skärmen.

204
00:09:06,610 --> 00:09:07,735
>> Det är gulmarkerad.

205
00:09:07,735 --> 00:09:10,020
Det är där jag är för närvarande.

206
00:09:10,020 --> 00:09:11,300
Min nyckel sker.

207
00:09:11,300 --> 00:09:13,030
Jag har uttömt varje position i min nyckel.

208
00:09:13,030 --> 00:09:15,040
Så jag kan inte gå längre.

209
00:09:15,040 --> 00:09:17,720
Så på denna punkt, allt jag
verkligen behöver göra är att säga, OK.

210
00:09:17,720 --> 00:09:18,990
Det är ungefär som att titta
ner i marken,

211
00:09:18,990 --> 00:09:21,115
om du föreställa
själv som denna typ av väg

212
00:09:21,115 --> 00:09:22,350
med olika anslutningar.

213
00:09:22,350 --> 00:09:25,800
Sorts tittar ner och typ av
sprutmålning Harvard på marken.

214
00:09:25,800 --> 00:09:26,800
Det är namnet på denna.

215
00:09:26,800 --> 00:09:28,300
Vet att det är vad som finns på den här platsen.

216
00:09:28,300 --> 00:09:31,870
Om vi ​​börjar vid roten och vi går ner
1 och sedan 6 och sedan tre och sedan 6,

217
00:09:31,870 --> 00:09:32,780
Vart är vi?

218
00:09:32,780 --> 00:09:35,640
Tja, om vi tittar ner
och vi ser Harvard, då

219
00:09:35,640 --> 00:09:38,960
Vi vet att Harvard var
grundat 1636 baserat på vägen

220
00:09:38,960 --> 00:09:41,400
vi genomföra denna datastruktur.

221
00:09:41,400 --> 00:09:43,177
Så det var förhoppningsvis okomplicerad.

222
00:09:43,177 --> 00:09:44,760
Vi kommer att göra ytterligare två insättningar.

223
00:09:44,760 --> 00:09:50,060
Och förhoppningsvis kommer att bidra till att
se detta gjort ytterligare två gånger.

224
00:09:50,060 --> 00:09:52,210
>> Nu ska vi sätta ett annat universitet.

225
00:09:52,210 --> 00:09:54,630
Låt oss sätta Yale i denna trie.

226
00:09:54,630 --> 00:09:57,037
Yale grundades 1701.

227
00:09:57,037 --> 00:09:58,870
Så vi börjar på
rot, som vi alltid gör.

228
00:09:58,870 --> 00:09:59,890
Och vi sätter ett genomgångs pekare.

229
00:09:59,890 --> 00:10:01,624
Vi kommer att använda det för att gå igenom.

230
00:10:01,624 --> 00:10:03,790
Det första vi vill
göra är att gå ner en väg.

231
00:10:03,790 --> 00:10:05,830
Det är den första siffran i vår nyckel.

232
00:10:05,830 --> 00:10:08,420
Lyckligtvis, men gör vi inte
måste göra något arbete den här gången.

233
00:10:08,420 --> 00:10:09,919
1 väg har redan raderats.

234
00:10:09,919 --> 00:10:13,520
Jag rensas det tidigare när jag
var att sätta in Harvard vid 1636.

235
00:10:13,520 --> 00:10:18,090
Så jag kan säkert flytta
ned 1 och bara åka dit.

236
00:10:18,090 --> 00:10:20,150
Om det inte går att flytta ner en.

237
00:10:20,150 --> 00:10:22,930
>> Men nu vill jag gå till 7.

238
00:10:22,930 --> 00:10:24,280
Jag banat väg vid 6.

239
00:10:24,280 --> 00:10:27,050
Jag vet att jag kan säkert
fortsätta nedför 6 bana.

240
00:10:27,050 --> 00:10:29,220
Men jag måste fortsätta på 7 väg.

241
00:10:29,220 --> 00:10:30,580
Så vad behöver jag göra?

242
00:10:30,580 --> 00:10:35,070
Jo, precis som förut, jag behöver bara
att rensa porten, få ur vägen,

243
00:10:35,070 --> 00:10:38,740
och bygga en ny nod från 7 väg.

244
00:10:38,740 --> 00:10:40,250
Precis som denna.

245
00:10:40,250 --> 00:10:42,930
>> Så nu har jag flyttat en och sedan 7.

246
00:10:42,930 --> 00:10:45,550
Och nu märker jag är typ
av denna nya delförgrening.

247
00:10:45,550 --> 00:10:46,050
Höger.

248
00:10:46,050 --> 00:10:49,260
Allt annat 16
på, jag bryr mig inte om.

249
00:10:49,260 --> 00:10:50,720
Jag gör 16 någonting.

250
00:10:50,720 --> 00:10:51,750
Jag gör 17 saker.

251
00:10:51,750 --> 00:10:58,380
>> Så nu från 17, jag måste
sorts flamma nya spår här.

252
00:10:58,380 --> 00:11:00,462
Nästa siffra min nyckel är 0.

253
00:11:00,462 --> 00:11:01,670
Jag uppenbarligen inte kan komma någonstans.

254
00:11:01,670 --> 00:11:02,628
Jag byggde just denna nod.

255
00:11:02,628 --> 00:11:04,550
Så jag vet att det finns ingen
vägar framåt härifrån.

256
00:11:04,550 --> 00:11:06,370
Så jag måste göra en själv.

257
00:11:06,370 --> 00:11:09,360
>> Så jag malloc en ny nod
och har 0 poäng där.

258
00:11:09,360 --> 00:11:12,770
Och sedan en gång till, malloc jag
ny nod och har en poäng där.

259
00:11:12,770 --> 00:11:15,870
Återigen, jag har uttömt min nyckel, 1701.

260
00:11:15,870 --> 00:11:18,472
Så jag ser ner och jag sprayfärg Yale.

261
00:11:18,472 --> 00:11:19,680
Det är namnet på denna nod.

262
00:11:19,680 --> 00:11:24,660
>> Och så nu om jag någonsin behöver se om Yale
är i detta trie, jag börjar vid roten,

263
00:11:24,660 --> 00:11:27,060
Jag går ner 1701, och tittar ner.

264
00:11:27,060 --> 00:11:30,030
Och om jag ser Yale sprut
målade på marken, då

265
00:11:30,030 --> 00:11:32,200
Jag vet Yale finns i denna trie.

266
00:11:32,200 --> 00:11:32,950
Låt oss göra en till.

267
00:11:32,950 --> 00:11:36,430
Låt oss sätta Dartmouth i detta
Trie, som grundades 1769.

268
00:11:36,430 --> 00:11:37,750
>> Börja vid roten igen.

269
00:11:37,750 --> 00:11:39,445
Min första siffran i min nyckel är en.

270
00:11:39,445 --> 00:11:40,820
Jag kan säkert gå den vägen.

271
00:11:40,820 --> 00:11:42,400
Det finns redan.

272
00:11:42,400 --> 00:11:44,040
Nästa siffra i min nyckel är 7.

273
00:11:44,040 --> 00:11:45,890
Jag kan säkert gå den vägen.

274
00:11:45,890 --> 00:11:47,540
Den finns också.

275
00:11:47,540 --> 00:11:49,000
>> Min nästa är 6.

276
00:11:49,000 --> 00:11:52,860
Härifrån, från där jag är för närvarande
i gult där i den mellersta noden,

277
00:11:52,860 --> 00:11:56,060
6 är för närvarande låst av.

278
00:11:56,060 --> 00:11:58,830
Om jag vill gå den vägen,
Jag måste bygga den själv.

279
00:11:58,830 --> 00:12:02,250
Så jag ska malloc en ny nod
och har sex poäng där.

280
00:12:02,250 --> 00:12:04,250
Och sedan, återigen, jag är
flammande nya spår här.

281
00:12:04,250 --> 00:12:10,750
>> Så jag malloc en ny nod så att från
att node-- tåglägesidentitet 9-- och sedan nu

282
00:12:10,750 --> 00:12:13,584
om jag reser 1769, och jag tittar ner.

283
00:12:13,584 --> 00:12:15,500
Det finns inget för närvarande
Spraya målade där.

284
00:12:15,500 --> 00:12:16,930
Jag kan skriva Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Och jag har insatt
Dartmouth in i trie.

286
00:12:20,710 --> 00:12:23,450
>> Så det är att sätta in
saker i trie.

287
00:12:23,450 --> 00:12:25,384
Nu vill vi att leta efter saker.

288
00:12:25,384 --> 00:12:27,050
Hur ska vi söka efter saker i trie?

289
00:12:27,050 --> 00:12:29,170
Tja, det är ganska mycket samma idé.

290
00:12:29,170 --> 00:12:33,620
Nu har vi bara använda siffrorna i nyckeln
för att se om vi kan navigera från roten

291
00:12:33,620 --> 00:12:37,170
där vi vill gå i trie.

292
00:12:37,170 --> 00:12:41,620
>> Om vi ​​träffar en återvändsgränd vid något tillfälle, då
Vi vet att denna omständighet inte kan före

293
00:12:41,620 --> 00:12:44,500
annars den vägen skulle
har redan raderats.

294
00:12:44,500 --> 00:12:45,930
Om vi ​​gör det hela vägen till
slutet, allt vi behöver göra

295
00:12:45,930 --> 00:12:48,471
är att titta ner och se om det är
elementet vi letar efter.

296
00:12:48,471 --> 00:12:49,335
Om det är, framgång.

297
00:12:49,335 --> 00:12:52,610
Om det inte misslyckas.

298
00:12:52,610 --> 00:12:54,940
>> Så låt oss söka efter
Harvard i denna trie.

299
00:12:54,940 --> 00:12:56,020
Vi börjar vid roten.

300
00:12:56,020 --> 00:12:58,228
Och, återigen, vi kommer att
skapa en genomgångs pekare

301
00:12:58,228 --> 00:12:59,390
att göra våra rörelser för oss.

302
00:12:59,390 --> 00:13:02,080
Från roten vet vi att
första vi måste gå är en,

303
00:13:02,080 --> 00:13:03,390
kan vi göra det?

304
00:13:03,390 --> 00:13:03,982
Ja vi kan.

305
00:13:03,982 --> 00:13:04,690
Om ett säkert sätt finns.

306
00:13:04,690 --> 00:13:06,660
Vi kan åka dit.

307
00:13:06,660 --> 00:13:08,440
>> Nu, nästa plats som vi måste gå är 6.

308
00:13:08,440 --> 00:13:10,557
Har 6 vägen existerar härifrån?

309
00:13:10,557 --> 00:13:11,140
Ja, det gör det.

310
00:13:11,140 --> 00:13:12,690
Vi kan gå ner 6 väg.

311
00:13:12,690 --> 00:13:13,905
Och vi hamna här.

312
00:13:13,905 --> 00:13:16,130
>> Kan vi gå ner i tre väg härifrån?

313
00:13:16,130 --> 00:13:18,450
Tja, som det visar sig,
ja, finns det också.

314
00:13:18,450 --> 00:13:20,790
Och kan vi få på 6 väg härifrån?

315
00:13:20,790 --> 00:13:21,982
Ja vi kan.

316
00:13:21,982 --> 00:13:24,002
>> Vi har inte riktigt svarat
frågan än.

317
00:13:24,002 --> 00:13:25,710
Det finns fortfarande ett mer
steg, som nu är

318
00:13:25,710 --> 00:13:28,520
Vi måste titta ner och
se om det är actually--

319
00:13:28,520 --> 00:13:32,660
Om vi ​​letar efter Harvard, är att
vad vi hittar när vi uttömmer nyckeln?

320
00:13:32,660 --> 00:13:35,430
I exemplet vi använder här,
åren är alltid fyra siffror.

321
00:13:35,430 --> 00:13:40,280
Men du kanske ska använda exempel där
du lagrar en ordbok av ord.

322
00:13:40,280 --> 00:13:44,060
>> Och så i stället för att ha 10 pekare
för min plats, kanske du har 26.

323
00:13:44,060 --> 00:13:46,040
En för varje bokstav i alfabetet.

324
00:13:46,040 --> 00:13:50,350
Och det finns några ord som slagträ,
vilket är en delmängd av sats, till exempel.

325
00:13:50,350 --> 00:13:53,511
Och så även om du kommer till
änden av nyckeln och du tittar ner,

326
00:13:53,511 --> 00:13:55,260
du kanske inte se vad
du letar efter.

327
00:13:55,260 --> 00:13:58,500
>> Så du alltid måste passera
hela vägen och sedan

328
00:13:58,500 --> 00:14:01,540
om du var framgångsrikt kunna
att korsa hela banan,

329
00:14:01,540 --> 00:14:03,440
titta ner och göra en slutlig bekräftelse.

330
00:14:03,440 --> 00:14:05,120
Är det vad jag letar efter?

331
00:14:05,120 --> 00:14:07,740
Tja, jag tittar ner efter start
upptill och gå 1636.

332
00:14:07,740 --> 00:14:08,240
Jag tittar ner.

333
00:14:08,240 --> 00:14:09,400
Jag ser Harvard.

334
00:14:09,400 --> 00:14:11,689
Så, ja, lyckades jag.

335
00:14:11,689 --> 00:14:13,980
Tänk om vad jag letar efter
är inte i trie, dock.

336
00:14:13,980 --> 00:14:17,200
Vad händer om jag letar efter Princeton,
som grundades år 1746.

337
00:14:17,200 --> 00:14:20,875
Och så 1746 blir min nyckel
att navigera genom trie.

338
00:14:20,875 --> 00:14:22,040
Tja, jag börjar vid roten.

339
00:14:22,040 --> 00:14:24,760
Och det första jag vill
till går ner en väg.

340
00:14:24,760 --> 00:14:25,590
Kan jag göra det?

341
00:14:25,590 --> 00:14:26,490
Ja det kan jag.

342
00:14:26,490 --> 00:14:28,730
>> Kan jag gå ner i 7 väg därifrån?

343
00:14:28,730 --> 00:14:29,230
Ja, jag kan.

344
00:14:29,230 --> 00:14:30,750
Som existerar också.

345
00:14:30,750 --> 00:14:32,460
Men kan jag gå ner i fyra väg härifrån?

346
00:14:32,460 --> 00:14:35,550
Det är som att ställa frågan, kan
Jag fortsätter ner det lilla torget

347
00:14:35,550 --> 00:14:37,114
att jag har markerat i gult?

348
00:14:37,114 --> 00:14:38,030
Det finns inget där.

349
00:14:38,030 --> 00:14:38,610
Höger.

350
00:14:38,610 --> 00:14:41,310
>> Det finns inget sätt framåt ned 4 väg.

351
00:14:41,310 --> 00:14:46,480
Om Princeton var i denna trie att 4
skulle ha rensats för oss redan.

352
00:14:46,480 --> 00:14:49,130
Och så på denna punkt
Vi har nått en återvändsgränd.

353
00:14:49,130 --> 00:14:50,250
Vi kan inte gå längre.

354
00:14:50,250 --> 00:14:53,440
Och så att vi kan säga, definitivt, nej.

355
00:14:53,440 --> 00:14:56,760
Princeton existerar inte i denna trie.

356
00:14:56,760 --> 00:14:58,860
>> Så vad betyder då allt detta?

357
00:14:58,860 --> 00:14:59,360
Höger.

358
00:14:59,360 --> 00:15:01,000
Det är mycket som händer här.

359
00:15:01,000 --> 00:15:02,500
Det finns pekare överallt.

360
00:15:02,500 --> 00:15:04,249
Och, som ni kan se
bara från diagrammet

361
00:15:04,249 --> 00:15:07,010
det finns en hel del noder som
är typ att flyga runt.

362
00:15:07,010 --> 00:15:13,480
Men märker varje gång vi ville
kontrollera om något var i trie,

363
00:15:13,480 --> 00:15:15,000
vi bara var tvungna att göra 4 drag.

364
00:15:15,000 --> 00:15:17,208
>> Varje gång vi ville
infoga något i trie,

365
00:15:17,208 --> 00:15:20,440
Vi måste göra 4 rör sig, möjligen
mallocing några saker längs vägen.

366
00:15:20,440 --> 00:15:23,482
Men som vi såg när vi införas
Dartmouth in i trie,

367
00:15:23,482 --> 00:15:25,940
ibland en del av banan
kanske redan rensas för oss.

368
00:15:25,940 --> 00:15:30,520
Och så vår trie blir större och
större, vi har att göra mindre arbete varje gång

369
00:15:30,520 --> 00:15:32,270
att infoga nya saker
eftersom vi har redan

370
00:15:32,270 --> 00:15:35,746
byggt en hel del av den mellanliggande
grenar längs vägen.

371
00:15:35,746 --> 00:15:38,370
Om vi ​​bara har någonsin att titta på
4 saker, är 4 bara en konstant.

372
00:15:38,370 --> 00:15:41,750
Vi verkligen typ av närmar
konstant tid insättning

373
00:15:41,750 --> 00:15:44,501
och konstant tid lookup.

374
00:15:44,501 --> 00:15:47,500
Kompromissen är naturligtvis är att
Detta trie, som ni kan nog säga,

375
00:15:47,500 --> 00:15:49,030
är enorm.

376
00:15:49,030 --> 00:15:51,040
Var och en av dessa noder
tar upp en hel del utrymme.

377
00:15:51,040 --> 00:15:52,090
>> Men det är kompromissen.

378
00:15:52,090 --> 00:15:55,260
Om vi ​​vill verkligen snabb
insättning, riktigt snabb radering,

379
00:15:55,260 --> 00:15:59,630
och riktigt snabb sökning, måste vi
har en hel del uppgifter som flyger runt.

380
00:15:59,630 --> 00:16:03,590
Vi måste avsätta en hel del utrymme
och minne för den datastruktur

381
00:16:03,590 --> 00:16:04,290
Att finnas.

382
00:16:04,290 --> 00:16:05,415
>> Och så det är kompromissen.

383
00:16:05,415 --> 00:16:07,310
Men det ser ut som vi
kanske har hittat det.

384
00:16:07,310 --> 00:16:09,560
Vi kanske har funnit att
heliga graal datastrukturer

385
00:16:09,560 --> 00:16:12,264
med snabb insättning,
radering och sökning.

386
00:16:12,264 --> 00:16:14,430
Och kanske detta kommer att bli ett
lämplig datastruktur

387
00:16:14,430 --> 00:16:18,890
att använda för den information
vi försöker att lagra.

388
00:16:18,890 --> 00:16:21,860
Jag är Doug Lloyd, är detta CS50.

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