1
00:00:00,000 --> 00:00:02,994
>> [Speel van musiek]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: So het ons stapsgewijze nader
en nader die heilige graal van data

4
00:00:08,550 --> 00:00:13,050
strukture, een wat ons kan voeg
in, verwyder uit, en kyk op

5
00:00:13,050 --> 00:00:15,440
in konstante tyd.

6
00:00:15,440 --> 00:00:16,270
Reg.

7
00:00:16,270 --> 00:00:17,280
Dit is soort van die doel te bereik.

8
00:00:17,280 --> 00:00:19,720
Ons wil in staat wees om te doen
dinge baie, baie vinnig.

9
00:00:19,720 --> 00:00:22,580
>> Het ons hier wanneer dit gevind
ons praat oor drieë?

10
00:00:22,580 --> 00:00:23,670
Wel, laat ons neem 'n blik.

11
00:00:23,670 --> 00:00:25,628
So het ons 'n paar gesien
verskillende data strukture

12
00:00:25,628 --> 00:00:28,680
wat hanteer die kartering van
sogenaamde sleutel waarde pare

13
00:00:28,680 --> 00:00:32,080
kartering 'n stuk van data
aan 'n ander stuk data

14
00:00:32,080 --> 00:00:36,020
sodat ons weet waar om te vind
inligting in die struktuur.

15
00:00:36,020 --> 00:00:40,060
>> So vir skikking, byvoorbeeld, die
sleutel is die element indeks of array

16
00:00:40,060 --> 00:00:42,600
plek 0 of 1 verskeidenheid en so aan.

17
00:00:42,600 --> 00:00:46,140
En die waarde is die data
wat bestaan ​​op die plek.

18
00:00:46,140 --> 00:00:48,550
So, wat gestoor word in die rigting 0?

19
00:00:48,550 --> 00:00:54,290
Wat is gestoor in verskeidenheid 1 versus net
0 en 1, wat sou wees die sleutels.

20
00:00:54,290 --> 00:00:56,360
>> Met 'n hash tafel is dit
soort van dieselfde idee.

21
00:00:56,360 --> 00:01:00,690
Met 'n hash tafel, ons het hierdie hash
funksie wat hash kodes genereer.

22
00:01:00,690 --> 00:01:03,670
So het die sleutel is om die hash-kode van die data.

23
00:01:03,670 --> 00:01:06,530
En die waarde, veral
Ons het gepraat oor chaining

24
00:01:06,530 --> 00:01:10,590
in die video op hash tabelle,
is dat gekoppel lys van data

25
00:01:10,590 --> 00:01:12,550
dat hashes om daardie hashcode.

26
00:01:12,550 --> 00:01:14,050
Reg.

27
00:01:14,050 --> 00:01:16,050
Wat van 'n ander benadering
hierdie metode, hoewel?

28
00:01:16,050 --> 00:01:21,000
Wat van 'n metode waar die
sleutel is gewaarborg om uniek te wees,

29
00:01:21,000 --> 00:01:25,410
Anders as 'n hash tafel, waar ons kon
eindig met twee stukke data

30
00:01:25,410 --> 00:01:27,200
met dieselfde hashcode.

31
00:01:27,200 --> 00:01:30,020
En dan het ons te make met
wat deur óf indringende of meer

32
00:01:30,020 --> 00:01:33,340
verkieslik chaining om daardie probleem op te los.

33
00:01:33,340 --> 00:01:37,520
>> So nou kan ons waarborg
dat ons sleutel uniek wees.

34
00:01:37,520 --> 00:01:39,690
En wat as ons waarde was
net iets so maklik

35
00:01:39,690 --> 00:01:44,080
as ware en valse wat ons vertel of
of daardie stukkie inligting

36
00:01:44,080 --> 00:01:45,610
bestaan ​​in die struktuur?

37
00:01:45,610 --> 00:01:48,180
A Boole kan so eenvoudig soos 'n bietjie wees.

38
00:01:48,180 --> 00:01:52,660
Realisties is dit waarskynlik 'n
byte meer geneig as 'n bietjie.

39
00:01:52,660 --> 00:01:55,410
Maar dit is 'n baie kleiner as
stoor miskien 'n 50-karakter string,

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

41
00:01:57,360 --> 00:02:02,210
>> So drieë, soortgelyk aan tafels hash,
wat kombineer skikkings en geskakelde lys,

42
00:02:02,210 --> 00:02:05,790
drieë kombineer skikkings,
strukture en wenke

43
00:02:05,790 --> 00:02:08,509
saam om data te stoor in
'n interessante manier wat

44
00:02:08,509 --> 00:02:11,550
mooi anders
enigiets wat ons tot dusver gesien het.

45
00:02:11,550 --> 00:02:16,750
Nou gebruik ons ​​die data as 'n draaiboek
hierdie data struktuur navigeer.

46
00:02:16,750 --> 00:02:18,710
En as ons kan volg
die draaiboek, as ons kan

47
00:02:18,710 --> 00:02:22,390
volg die data van
begin tot einde, sal ons

48
00:02:22,390 --> 00:02:24,945
weet of dat die data
bestaan ​​in die Trie.

49
00:02:24,945 --> 00:02:28,310
>> En as ons nie kan volg die kaart
van betekenis aan die einde nie,

50
00:02:28,310 --> 00:02:30,600
die data kan nie bestaan ​​nie.

51
00:02:30,600 --> 00:02:32,890
Weereens, die sleutels hier is
gewaarborg om uniek te wees.

52
00:02:32,890 --> 00:02:36,020
En so in teenstelling met 'hash tafel, sal ons nooit
te doen het met botsings hier.

53
00:02:36,020 --> 00:02:39,090
En geen twee stukke data
presies dieselfde draaiboek

54
00:02:39,090 --> 00:02:40,530
tensy daardie data is identies.

55
00:02:40,530 --> 00:02:44,580
>> As ons voeg John, dan
Ons soek John.

56
00:02:44,580 --> 00:02:47,430
Dit is twee identiese stukke
data, reg, ons is op soek deur.

57
00:02:47,430 --> 00:02:49,880
Maar andersins, enige
twee stukke data is

58
00:02:49,880 --> 00:02:52,750
gewaarborg om unieke padkaarte het
deur middel van hierdie data-struktuur.

59
00:02:52,750 --> 00:02:56,210
En ons gaan om 'n blik op te neem
'n visuele van hierdie in net 'n oomblik.

60
00:02:56,210 --> 00:02:58,810
>> Ons sal dit doen deur te probeer om
skep 'n nuwe data struktuur,

61
00:02:58,810 --> 00:03:00,564
kartering van die volgende sleutel waarde pare.

62
00:03:00,564 --> 00:03:03,480
In hierdie geval, is ons nie gaan gebruik
iets so eenvoudig soos 'n Boole.

63
00:03:03,480 --> 00:03:06,200
Ons sal eintlik die string te stoor.

64
00:03:06,200 --> 00:03:08,690
En dat string gaan
wees die naam van 'n universiteit.

65
00:03:08,690 --> 00:03:12,140
>> En die sleutel gaan die jaar wees
wanneer daardie universiteit gestig.

66
00:03:12,140 --> 00:03:15,380
Alle jaar vir universiteite
gaan vier syfers.

67
00:03:15,380 --> 00:03:19,840
En so sal ons die vier syfers te gebruik
opgevolg deur hierdie data struktuur.

68
00:03:19,840 --> 00:03:22,270
En ons sal sien, weer, hoe
ons dit doen in net 'n sekonde.

69
00:03:22,270 --> 00:03:25,110
>> Aan die einde van die pad,
ons sal die naam te sien

70
00:03:25,110 --> 00:03:30,250
van die universiteit wat ooreenstem
dat die sleutel, die vier syfers.

71
00:03:30,250 --> 00:03:34,390
Die basiese idee agter 'n Trie
is ons 'n sentrale roete.

72
00:03:34,390 --> 00:03:35,640
So dink oor dit soos 'n boom.

73
00:03:35,640 --> 00:03:39,211
En dit is soortgelyk in spelling
en in die konsep om 'n boom.

74
00:03:39,211 --> 00:03:41,460
Algemeen wanneer ons dink oor
bome in die werklike wêreld,

75
00:03:41,460 --> 00:03:44,090
hulle het 'n wortel wat in die
grond en hulle opwaartse groei

76
00:03:44,090 --> 00:03:46,830
en hulle het takke
en hulle het die blare.

77
00:03:46,830 --> 00:03:49,450
En basies die idee van
'n Trie is presies dieselfde,

78
00:03:49,450 --> 00:03:51,755
behalwe dat die wortel geanker
iewers in die lug.

79
00:03:51,755 --> 00:03:53,130
En die blare is aan die onderkant.

80
00:03:53,130 --> 00:03:55,750
>> So dit is soort van soos die neem van 'n boom
en net daarby dit onderstebo.

81
00:03:55,750 --> 00:03:56,880
Maar daar is nog takke.

82
00:03:56,880 --> 00:03:59,463
En dié sal wees om ons paaie,
diegene sal wees om ons verbindings

83
00:03:59,463 --> 00:04:02,220
uit die wortel van die blare.

84
00:04:02,220 --> 00:04:04,200
In hierdie geval, die
paaie, daardie takke

85
00:04:04,200 --> 00:04:08,490
gemerk met syfers wat ons vertel
watter pad om te gaan van waar ons is.

86
00:04:08,490 --> 00:04:11,800
>> As ons sien 'n 0, sal ons aftrek hierdie tak,
as ons sien 'n 1, sal ons aftrek hierdie tak,

87
00:04:11,800 --> 00:04:12,900
en so en so aan.

88
00:04:12,900 --> 00:04:14,060
Wel, wat beteken dit?

89
00:04:14,060 --> 00:04:16,519
Wel, dit beteken dat
by elke kruising punt

90
00:04:16,519 --> 00:04:19,260
en elke node in die
middel en elke loot,

91
00:04:19,260 --> 00:04:23,020
daar is 10 moontlike
plekke wat ons kan gaan.

92
00:04:23,020 --> 00:04:27,690
So is daar 10 wenke
uit elke plek.

93
00:04:27,690 --> 00:04:30,610
>> En dit is waar drieë n kan kry
bietjie intimiderend vir iemand

94
00:04:30,610 --> 00:04:34,460
wie is nie 'n baie
ervaring in rekenaarwetenskap voor.

95
00:04:34,460 --> 00:04:35,960
Maar drieë is regtig mooi awesome.

96
00:04:35,960 --> 00:04:37,793
En as jy die
kans om te werk met hulle

97
00:04:37,793 --> 00:04:40,420
en jy bereid is om te grawe in-is
en eksperimenteer met hulle,

98
00:04:40,420 --> 00:04:44,234
hulle is regtig baie interessant
data strukture te werk.

99
00:04:44,234 --> 00:04:46,900
As ons wil hê om 'n element te voeg
in die Trie, al wat ons nodig het om te doen

100
00:04:46,900 --> 00:04:51,360
is die bou van die korrekte pad
uit die wortel van die blaar.

101
00:04:51,360 --> 00:04:55,390
Hier is wat elke stap langs
die pad lyk.

102
00:04:55,390 --> 00:04:59,660
Ons gaan 'n nuwe data definieer
struktuur vir 'n nuwe node genoem Trie.

103
00:04:59,660 --> 00:05:02,560
>> En binnekant van die data
struktuur is daar twee stukke.

104
00:05:02,560 --> 00:05:05,460
Ons gaan na die winkel
naam van 'n universiteit.

105
00:05:05,460 --> 00:05:09,410
En ons gaan om te slaan
'n verskeidenheid van wenke

106
00:05:09,410 --> 00:05:12,190
na ander nodes van dieselfde soort.

107
00:05:12,190 --> 00:05:14,780
So, weer, dit is dat die soort
van die konsep van oral

108
00:05:14,780 --> 00:05:18,567
ons is, het ons by 10 moontlike
plekke wat ons kan gaan.

109
00:05:18,567 --> 00:05:20,150
As ons sien 'n 0, sal ons aftrek hierdie tak.

110
00:05:20,150 --> 00:05:22,690
As ons sien 'n 1, die tak,
en so aan en so aan en so aan.

111
00:05:22,690 --> 00:05:25,160
As ons sê 9, sal ons aftrek hierdie tak.

112
00:05:25,160 --> 00:05:28,220
So by elke kruising punt,
ons kan gaan 10 moontlike plekke.

113
00:05:28,220 --> 00:05:35,740
So elke node het 10 wenke bevat
na ander nodes, tot 10 ander nodes.

114
00:05:35,740 --> 00:05:39,810
>> En die data wat ons stoor is
net die naam van die universiteit.

115
00:05:39,810 --> 00:05:41,060
So laat bou 'n Trie.

116
00:05:41,060 --> 00:05:44,860
Kom ons voeg 'n paar
van items in ons Trie.

117
00:05:44,860 --> 00:05:46,740
So op die heel boonste,
dit is ons wortel node.

118
00:05:46,740 --> 00:05:49,740
Dit is waarskynlik gaan om iets te wees
jy gaan om te verklaar wêreldwyd.

119
00:05:49,740 --> 00:05:53,450
En jy gaan globaal handhaaf
'n verwysing na hierdie node altyd.

120
00:05:53,450 --> 00:05:55,360
>> Jy gaan om te sê,
wortel gelyk, en jy is

121
00:05:55,360 --> 00:05:57,580
gaan jouself malloc Trie knoop.

122
00:05:57,580 --> 00:05:59,850
En jy gaan nooit
om weer wortel raak.

123
00:05:59,850 --> 00:06:02,300
Elke keer as jy wil
begin opgevolg deur,

124
00:06:02,300 --> 00:06:05,802
jy 'n ander wyser stel
gelyk aan die wortel, soos trav,

125
00:06:05,802 --> 00:06:07,760
wat is die voorbeeld wat ek
gebruik in baie van my video's

126
00:06:07,760 --> 00:06:11,090
hier op stapels en toue
en 'n skakel lyste en so aan.

127
00:06:11,090 --> 00:06:13,320
>> Jy stel 'n ander wyser
genoem trav vir traversal.

128
00:06:13,320 --> 00:06:15,890
En jy trav gebruik om te navigeer
deur die data-struktuur.

129
00:06:15,890 --> 00:06:17,500
So laat ons sien hoe dit kan lyk.

130
00:06:17,500 --> 00:06:19,880
So nou, wat
nie 'n knoop lyk?

131
00:06:19,880 --> 00:06:22,920
Wel, net soos ons data
struktuur verklaring aangedui,

132
00:06:22,920 --> 00:06:26,906
ons het 'n string, wat
in hierdie geval is leeg.

133
00:06:26,906 --> 00:06:27,780
Daar is niks hier.

134
00:06:27,780 --> 00:06:29,550
>> En 'n verskeidenheid van 10 wenke.

135
00:06:29,550 --> 00:06:31,790
En nou, ons net
het 1 node in hierdie Trie.

136
00:06:31,790 --> 00:06:33,110
Daar is niks anders in dit.

137
00:06:33,110 --> 00:06:36,020
So al 10 van die
wysers punt om null.

138
00:06:36,020 --> 00:06:38,090
Dit is wat die rooi dui.

139
00:06:38,090 --> 00:06:39,500
>> Kom ons plaas die string Harvard.

140
00:06:39,500 --> 00:06:41,999
Kom ons plaas die Universiteit van
Harvard in hierdie Trie, wat

141
00:06:41,999 --> 00:06:43,940
is gestig in die jaar 1636.

142
00:06:43,940 --> 00:06:48,220
Ons wil die sleutel te gebruik,
1636, om ons te vertel waar ons

143
00:06:48,220 --> 00:06:50,140
gaan om te slaan Harvard in die Trie.

144
00:06:50,140 --> 00:06:51,470
Nou, hoe kan ons dit doen?

145
00:06:51,470 --> 00:06:52,886
>> Dit mag dalk iets soos hierdie.

146
00:06:52,886 --> 00:06:54,160
Ons begin by die wortel.

147
00:06:54,160 --> 00:06:56,920
En ons het hierdie 10 plekke wat ons kan gaan.

148
00:06:56,920 --> 00:06:59,900
Die wortel is net soos enige
ander node van die Trie.

149
00:06:59,900 --> 00:07:02,850
Daar is 10 plekke wat ons kan gaan van hier af.

150
00:07:02,850 --> 00:07:07,215
>> Waar moet ons waarskynlik wil
om te gaan as die sleutel is 1636?

151
00:07:07,215 --> 00:07:08,340
Daar is regtig twee opsies.

152
00:07:08,340 --> 00:07:08,450
Reg.

153
00:07:08,450 --> 00:07:10,825
Ons kan die sleutel van die bou
regs na links en begin met 6.

154
00:07:10,825 --> 00:07:14,000
Of ons kan die sleutel van die bou
links na regs en begin met 1.

155
00:07:14,000 --> 00:07:16,140
>> Dit is waarskynlik meer
intuïtief as 'n mens

156
00:07:16,140 --> 00:07:18,110
om ons verstaan ​​sal
gaan net links na regs.

157
00:07:18,110 --> 00:07:21,140
En so as ek wil voeg
Harvard in hierdie Trie,

158
00:07:21,140 --> 00:07:23,560
Ek wil waarskynlik om te begin
deur te begin by die wortel,

159
00:07:23,560 --> 00:07:25,720
op soek na my 10 opsies
in die voorkant van my en sê:

160
00:07:25,720 --> 00:07:28,700
Ek wil om te gaan die 1 pad.

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

162
00:07:29,700 --> 00:07:31,810
>> Nou, 1 pad is tans null.

163
00:07:31,810 --> 00:07:35,920
So as ek wil om voort te gaan neer dat die pad
hierdie element voeg in die Trie,

164
00:07:35,920 --> 00:07:42,040
Ek het na 'n nuwe node malloc, het 1
wys daar en dan is ek goed om te gaan.

165
00:07:42,040 --> 00:07:46,460
>> So ek basies is op 'n
punt waar ek staan

166
00:07:46,460 --> 00:07:50,270
aan die wortel van die boom of die
Trie en daar is 10 takke.

167
00:07:50,270 --> 00:07:52,260
Maar elke tak het 'n
hek in die voorkant van dit.

168
00:07:52,260 --> 00:07:53,060
Reg.

169
00:07:53,060 --> 00:07:54,850
Want daar is niks anders daar is.

170
00:07:54,850 --> 00:07:56,522
Geen veilige gang.

171
00:07:56,522 --> 00:07:58,980
Dit beteken dat daar niks
down enige van daardie takke.

172
00:07:58,980 --> 00:08:02,532
As ek wil begin bou
iets, ek wil die hek te verwyder.

173
00:08:02,532 --> 00:08:04,490
Ek wil na die hek te verwyder
in die voorkant van nommer 1.

174
00:08:04,490 --> 00:08:05,698
En ek wil loop nie.

175
00:08:05,698 --> 00:08:08,060
En ek wil bou
'n ander plek vir my om te gaan.

176
00:08:08,060 --> 00:08:09,470
>> En dit is wat ek hier gedoen het.

177
00:08:09,470 --> 00:08:11,430
So 1 nie meer punte aan null.

178
00:08:11,430 --> 00:08:13,830
Ek het gesê dit is veilig om hier af te gaan nou.

179
00:08:13,830 --> 00:08:15,789
Ek gebou 'n ander knoop.

180
00:08:15,789 --> 00:08:18,330
En toe ek by daardie node, ek
het 'n ander besluit te maak.

181
00:08:18,330 --> 00:08:20,890
Waar gaan ek om te gaan van hier af?

182
00:08:20,890 --> 00:08:22,700
>> Wel, ek het al in die 1 weg.

183
00:08:22,700 --> 00:08:24,470
So nou wil ek waarskynlik om af te gaan die 6.

184
00:08:24,470 --> 00:08:24,970
Reg.

185
00:08:24,970 --> 00:08:27,100
Weereens, ek het 10 plekke wat ek kan kies.

186
00:08:27,100 --> 00:08:30,060
So laat gaan nou af nommer 6.

187
00:08:30,060 --> 00:08:32,280
So ek duidelik die hek
in die voorkant van nommer 6.

188
00:08:32,280 --> 00:08:33,250
En ek loop daar.

189
00:08:33,250 --> 00:08:34,580
En ek bou 'n ander knoop.

190
00:08:34,580 --> 00:08:37,630
En ek het 'n ander punt aansluiting bereik.

191
00:08:37,630 --> 00:08:40,289
>> Weereens, ek het 10 keuses
want waar ek kan gaan.

192
00:08:40,289 --> 00:08:42,799
Ek het verskuif van 1 tot 6.

193
00:08:42,799 --> 00:08:44,215
So nou wil ek waarskynlik om te gaan na 3.

194
00:08:44,215 --> 00:08:45,381
3, daar is nêrens ek kan gaan.

195
00:08:45,381 --> 00:08:48,980
So ek het die pad te vee
en die bou van myself 'n nuwe ruimte.

196
00:08:48,980 --> 00:08:50,870
En dan van 3, waar ek wil gaan?

197
00:08:50,870 --> 00:08:52,450
Ek wil om te 6 gaan.

198
00:08:52,450 --> 00:08:54,770
>> En weer, moes ek
duidelik die manier om dit te doen.

199
00:08:54,770 --> 00:08:59,179
So nou het ek my sleutel gebruik om te skep voeg
nodes en begin om hierdie Trie bou.

200
00:08:59,179 --> 00:09:00,220
Ek het begin by die wortel.

201
00:09:00,220 --> 00:09:03,666
Ek het af 1636 weg.

202
00:09:03,666 --> 00:09:05,540
En nou is ek aan die onderkant
daar op daardie knoop.

203
00:09:05,540 --> 00:09:06,610
En jy kan in staat wees om
sien dit op jou skerm.

204
00:09:06,610 --> 00:09:07,735
>> Dit is uitgelig in geel.

205
00:09:07,735 --> 00:09:10,020
Dit is waar ek tans is.

206
00:09:10,020 --> 00:09:11,300
My sleutel gedoen word.

207
00:09:11,300 --> 00:09:13,030
Ek het elke posisie in my sleutel uitgeput is.

208
00:09:13,030 --> 00:09:15,040
So ek kan nie verder gaan.

209
00:09:15,040 --> 00:09:17,720
So op hierdie punt, al wat ek
regtig nodig het om te doen is sê, OK.

210
00:09:17,720 --> 00:09:18,990
Dit is soort van soos soek
af na die grond,

211
00:09:18,990 --> 00:09:21,115
as jy behels
jouself as hierdie soort van pad

212
00:09:21,115 --> 00:09:22,350
met verskillende verbindings.

213
00:09:22,350 --> 00:09:25,800
Soort van kyk af en soort
spuit verf Harvard op die grond.

214
00:09:25,800 --> 00:09:26,800
Dit is die naam van hierdie.

215
00:09:26,800 --> 00:09:28,300
Weet dit is wat by hierdie plek.

216
00:09:28,300 --> 00:09:31,870
As ons begin by die wortel en ons het afgekom
1 en dan 6 en dan 3 en dan 6,

217
00:09:31,870 --> 00:09:32,780
waar is ons?

218
00:09:32,780 --> 00:09:35,640
Wel, as ons kyk neer
en ons sien Harvard, dan

219
00:09:35,640 --> 00:09:38,960
ons weet dat Harvard was
gestig in 1636 op grond van die manier

220
00:09:38,960 --> 00:09:41,400
ons die implementering van hierdie data-struktuur.

221
00:09:41,400 --> 00:09:43,177
So dit was hopelik eenvoudig.

222
00:09:43,177 --> 00:09:44,760
Ons gaan twee invoegings te doen.

223
00:09:44,760 --> 00:09:50,060
En hopelik sal dit help om
sien dit gedoen twee keer meer.

224
00:09:50,060 --> 00:09:52,210
>> Nou, laat ons voeg 'n ander universiteit.

225
00:09:52,210 --> 00:09:54,630
Kom ons voeg Yale in hierdie Trie.

226
00:09:54,630 --> 00:09:57,037
Yale is gestig in 1701.

227
00:09:57,037 --> 00:09:58,870
So ons sal begin by die
wortel, soos ons altyd doen.

228
00:09:58,870 --> 00:09:59,890
En ons het 'n traversal wyser.

229
00:09:59,890 --> 00:10:01,624
Ons gaan om dit te gebruik om deur te beweeg.

230
00:10:01,624 --> 00:10:03,790
Die eerste ding wat ons wil
doen is gaan in die 1 pad.

231
00:10:03,790 --> 00:10:05,830
Dit is die eerste syfer van ons sleutel.

232
00:10:05,830 --> 00:10:08,420
Gelukkig, al is, ons doen nie
moet enige werk hierdie keer doen.

233
00:10:08,420 --> 00:10:09,919
Die 1 pad is reeds skoongemaak.

234
00:10:09,919 --> 00:10:13,520
Ek het voorheen toe ek skoongemaak dit
is die inbring Harvard by 1636.

235
00:10:13,520 --> 00:10:18,090
So ek kan veilig te beweeg
down 1 en net daar te gaan.

236
00:10:18,090 --> 00:10:20,150
As kan af beweeg die 1.

237
00:10:20,150 --> 00:10:22,930
>> Nou, al is, ek wil gaan na 7.

238
00:10:22,930 --> 00:10:24,280
Ek die weg gebaan op 6.

239
00:10:24,280 --> 00:10:27,050
Ek weet ek kan veilig
voort in die 6 pad.

240
00:10:27,050 --> 00:10:29,220
Maar ek moet voortgaan op die pad 7.

241
00:10:29,220 --> 00:10:30,580
So, wat moet ek doen?

242
00:10:30,580 --> 00:10:35,070
Wel, net soos voorheen, ek moet net
om die hek te verwyder, te kry uit die pad,

243
00:10:35,070 --> 00:10:38,740
en die bou van 'n nuwe node uit die 7 pad.

244
00:10:38,740 --> 00:10:40,250
Net soos hierdie.

245
00:10:40,250 --> 00:10:42,930
>> So nou het ek verhuis 1 en dan 7.

246
00:10:42,930 --> 00:10:45,550
En nou sien, ek is soort
van hierdie nuwe subbranch.

247
00:10:45,550 --> 00:10:46,050
Reg.

248
00:10:46,050 --> 00:10:49,260
Alles anders uit 16
op, weet ek nie omgee.

249
00:10:49,260 --> 00:10:50,720
Ek is nie 16 om iets te doen.

250
00:10:50,720 --> 00:10:51,750
Ek doen 17 dinge.

251
00:10:51,750 --> 00:10:58,380
>> So, nou van 17 op, ek het om te
soort van brand hier nuwe paaie.

252
00:10:58,380 --> 00:11:00,462
Die volgende syfer my sleutel is 0.

253
00:11:00,462 --> 00:11:01,670
Ek kan duidelik nie oral te kry.

254
00:11:01,670 --> 00:11:02,628
Ek het net het hierdie knoop.

255
00:11:02,628 --> 00:11:04,550
So ek weet daar is geen
paaie vorentoe van hier.

256
00:11:04,550 --> 00:11:06,370
So ek het om self een te maak.

257
00:11:06,370 --> 00:11:09,360
>> So ek malloc 'n nuwe node
en het 0 punt is daar.

258
00:11:09,360 --> 00:11:12,770
En dan nog een keer, ek het 'n malloc
nuwe knoop en een punt is daar.

259
00:11:12,770 --> 00:11:15,870
Weereens, ek het my sleutel, 1701 uitgeput is.

260
00:11:15,870 --> 00:11:18,472
So ek kyk af en ek spuitverf Yale.

261
00:11:18,472 --> 00:11:19,680
Dit is die naam van hierdie knoop.

262
00:11:19,680 --> 00:11:24,660
>> En so nou as ek ooit nodig het om te kyk of Yale
is in hierdie Trie, begin ek by die wortel,

263
00:11:24,660 --> 00:11:27,060
Ek gaan af 1701, en kyk af.

264
00:11:27,060 --> 00:11:30,030
En as ek sien Yale spuit
geverf op die grond, dan

265
00:11:30,030 --> 00:11:32,200
Ek weet Yale bestaan ​​in hierdie Trie.

266
00:11:32,200 --> 00:11:32,950
Kom ons doen 'n meer.

267
00:11:32,950 --> 00:11:36,430
Kom ons voeg Dartmouth in hierdie
Trie, wat is gestig in 1769.

268
00:11:36,430 --> 00:11:37,750
>> Begin by die wortel weer.

269
00:11:37,750 --> 00:11:39,445
My eerste syfer van my sleutel is 1.

270
00:11:39,445 --> 00:11:40,820
Ek kan veilig beweeg neer dat die pad.

271
00:11:40,820 --> 00:11:42,400
Wat reeds bestaan.

272
00:11:42,400 --> 00:11:44,040
Die volgende syfer van my sleutel is 7.

273
00:11:44,040 --> 00:11:45,890
Ek kan veilig beweeg neer dat die pad.

274
00:11:45,890 --> 00:11:47,540
Dit bestaan ​​ook.

275
00:11:47,540 --> 00:11:49,000
>> My volgende is 6.

276
00:11:49,000 --> 00:11:52,860
Van hier, waar ek tans is
geel daar in daardie middel knoop,

277
00:11:52,860 --> 00:11:56,060
6 is tans gesluit het.

278
00:11:56,060 --> 00:11:58,830
As ek wil om te gaan dat die pad,
Ek het dit self te bou.

279
00:11:58,830 --> 00:12:02,250
So ek sal 'n nuwe node malloc
en 6 punt is daar.

280
00:12:02,250 --> 00:12:04,250
En dan, weer, ek is
brandende nuwe paaie hier.

281
00:12:04,250 --> 00:12:10,750
>> So ek malloc 'n nuwe node sodat uit
dat node-- pad getal 9-- en dan nou

282
00:12:10,750 --> 00:12:13,584
As ek reis 1769, en ek kyk af.

283
00:12:13,584 --> 00:12:15,500
Daar is niks wat tans
spuit daar geverf.

284
00:12:15,500 --> 00:12:16,930
Ek kan skryf Dartmouth.

285
00:12:16,930 --> 00:12:20,710
En ek het ingevoeg
DARTMOUTH in die Trie.

286
00:12:20,710 --> 00:12:23,450
>> So dit is die invoeging
dinge in die Trie.

287
00:12:23,450 --> 00:12:25,384
Nou wil ons om te soek na dinge.

288
00:12:25,384 --> 00:12:27,050
Hoe weet ons soek vir dinge in die Trie?

289
00:12:27,050 --> 00:12:29,170
Wel, dit is pretty much dieselfde idee.

290
00:12:29,170 --> 00:12:33,620
Nou het ons net die gebruik van die syfers van die belangrikste
om te sien of ons kan navigeer van die wortel

291
00:12:33,620 --> 00:12:37,170
waar ons wil gaan in die Trie.

292
00:12:37,170 --> 00:12:41,620
>> As ons druk 'n doodloopstraat by enige punt, dan
ons weet dat daardie element nie kan bestaan

293
00:12:41,620 --> 00:12:44,500
of anders dat die pad sou
reeds skoongemaak.

294
00:12:44,500 --> 00:12:45,930
As ons dit al die pad na
die einde, al wat ons nodig het om te doen

295
00:12:45,930 --> 00:12:48,471
is neersien en kyk of dit is
die element wat ons soek.

296
00:12:48,471 --> 00:12:49,335
As dit is, sukses.

297
00:12:49,335 --> 00:12:52,610
As dit is nie, misluk.

298
00:12:52,610 --> 00:12:54,940
>> So laat soek
Harvard in hierdie Trie.

299
00:12:54,940 --> 00:12:56,020
Ons begin by die wortel.

300
00:12:56,020 --> 00:12:58,228
En weer, ons gaan
skep 'n traversal wyser

301
00:12:58,228 --> 00:12:59,390
ons beweeg vir ons doen.

302
00:12:59,390 --> 00:13:02,080
Uit die wortel weet ons dat die
eerste plek moet ons gaan, is 1,

303
00:13:02,080 --> 00:13:03,390
kan ons dit doen?

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

305
00:13:03,982 --> 00:13:04,690
As veilig bestaan.

306
00:13:04,690 --> 00:13:06,660
Ons kan daar te gaan.

307
00:13:06,660 --> 00:13:08,440
>> Nou, die volgende plek wat ons nodig het om te gaan is 6.

308
00:13:08,440 --> 00:13:10,557
Maak die pad 6 bestaan ​​van hier af?

309
00:13:10,557 --> 00:13:11,140
Ja, dit doen nie.

310
00:13:11,140 --> 00:13:12,690
Ons kan gaan in die 6 pad.

311
00:13:12,690 --> 00:13:13,905
En ons eindig hier op.

312
00:13:13,905 --> 00:13:16,130
>> Kan ons gaan af in die pad 3 van hier af?

313
00:13:16,130 --> 00:13:18,450
Wel, as dit blyk,
Ja, wat te bestaan.

314
00:13:18,450 --> 00:13:20,790
En ons kan kry op die pad 6 van hier af?

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

316
00:13:21,982 --> 00:13:24,002
>> Ons het nie heeltemal beantwoord
nog die vraag.

317
00:13:24,002 --> 00:13:25,710
Daar is nog een
stap, wat nou

318
00:13:25,710 --> 00:13:28,520
ons nodig het om te kyk af en
sien of dit is actually--

319
00:13:28,520 --> 00:13:32,660
As ons kyk na Harvard, is dat
wat ons vind nadat ons die uitlaat van die sleutel?

320
00:13:32,660 --> 00:13:35,430
In die voorbeeld is ons hier in met,
die jaar is altyd vier syfers.

321
00:13:35,430 --> 00:13:40,280
Maar jy kan met behulp van die voorbeeld waar
jy stoor 'n woordeboek van woorde.

322
00:13:40,280 --> 00:13:44,060
>> En so in plaas van om 10 wenke
vir my plek, kan jy 26.

323
00:13:44,060 --> 00:13:46,040
Een vir elke letter van die alfabet.

324
00:13:46,040 --> 00:13:50,350
En daar is 'n paar woorde soos bat,
wat is 'n subset van joernaal, byvoorbeeld.

325
00:13:50,350 --> 00:13:53,511
En dus selfs as jy die
einde van die sleutel en jy kyk af,

326
00:13:53,511 --> 00:13:55,260
jy dalk nie sien wat
jy soek.

327
00:13:55,260 --> 00:13:58,500
>> So het jy altyd om oor te steek
die hele pad en dan

328
00:13:58,500 --> 00:14:01,540
as jy suksesvol kan
om die hele pad deurkruis,

329
00:14:01,540 --> 00:14:03,440
neersien en doen een finale bevestiging.

330
00:14:03,440 --> 00:14:05,120
Is dit wat ek soek?

331
00:14:05,120 --> 00:14:07,740
Wel, kyk ek af na die begin
aan die bokant en gaan 1636.

332
00:14:07,740 --> 00:14:08,240
Ek kyk af.

333
00:14:08,240 --> 00:14:09,400
Ek sien Harvard.

334
00:14:09,400 --> 00:14:11,689
So, ja, daarin geslaag Ek.

335
00:14:11,689 --> 00:14:13,980
Wat gebeur as wat ek is op soek na
is nie in die Trie, al is.

336
00:14:13,980 --> 00:14:17,200
Wat gebeur as ek is op soek na Princeton,
wat is gestig in 1746.

337
00:14:17,200 --> 00:14:20,875
En so 1746 word my sleutel
om te opgevolg deur die Trie.

338
00:14:20,875 --> 00:14:22,040
Wel, ek begin by die wortel.

339
00:14:22,040 --> 00:14:24,760
En die eerste plek wil ek
om af gaan die 1 pad.

340
00:14:24,760 --> 00:14:25,590
Kan ek dit doen?

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

342
00:14:26,490 --> 00:14:28,730
>> Kan ek gaan af in die pad van daar 7?

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

344
00:14:29,230 --> 00:14:30,750
Wat bestaan ​​ook.

345
00:14:30,750 --> 00:14:32,460
Maar ek kan gaan in die 4 pad van hier af?

346
00:14:32,460 --> 00:14:35,550
Dit is soos die vraag te vra, kan
Ek gaan sit wat min vierkante

347
00:14:35,550 --> 00:14:37,114
dat ek in geel uitgelig?

348
00:14:37,114 --> 00:14:38,030
Daar is niks.

349
00:14:38,030 --> 00:14:38,610
Reg.

350
00:14:38,610 --> 00:14:41,310
>> Daar is geen pad vorentoe in die 4 pad.

351
00:14:41,310 --> 00:14:46,480
As Princeton was in hierdie Trie, wat 4
sou gewees het reeds skoongemaak vir ons.

352
00:14:46,480 --> 00:14:49,130
En so op hierdie punt
ons het 'n doodloopstraat bereik.

353
00:14:49,130 --> 00:14:50,250
Ons kan nie verder gaan nie.

354
00:14:50,250 --> 00:14:53,440
En so kan ons sê, finaal, no.

355
00:14:53,440 --> 00:14:56,760
Princeton bestaan ​​nie in hierdie Trie.

356
00:14:56,760 --> 00:14:58,860
>> So, wat beteken dit alles?

357
00:14:58,860 --> 00:14:59,360
Reg.

358
00:14:59,360 --> 00:15:01,000
Daar is 'n baie gaan op hier.

359
00:15:01,000 --> 00:15:02,500
Daar is aanduidings oor die hele plek.

360
00:15:02,500 --> 00:15:04,249
En, soos jy kan sien
net uit die diagram,

361
00:15:04,249 --> 00:15:07,010
daar is 'n baie nodes wat
is soort van vlieg rond.

362
00:15:07,010 --> 00:15:13,480
Maar let elke keer as ons wou
kyk of daar iets was in die Trie,

363
00:15:13,480 --> 00:15:15,000
ons het net 4 beweeg te maak.

364
00:15:15,000 --> 00:15:17,208
>> Elke keer as ons wou
iets invoeg in die Trie,

365
00:15:17,208 --> 00:15:20,440
ons het tot 4 beweeg te maak, moontlik
mallocing paar dinge langs die pad.

366
00:15:20,440 --> 00:15:23,482
Maar soos ons gesien het toe ons plaas
DARTMOUTH in die Trie,

367
00:15:23,482 --> 00:15:25,940
soms 'n paar van die pad
dalk reeds skoongemaak vir ons.

368
00:15:25,940 --> 00:15:30,520
En so ons Trie kry groter en
groter, ons het minder werk elke keer te doen

369
00:15:30,520 --> 00:15:32,270
om nuwe dinge te voeg
want ons het reeds

370
00:15:32,270 --> 00:15:35,746
het 'n groot deel van die intermediêre
takke langs die pad.

371
00:15:35,746 --> 00:15:38,370
As ons net ooit om te kyk na
4 dinge, 4 is net 'n konstante.

372
00:15:38,370 --> 00:15:41,750
Ons is regtig soort van nader
konstante tyd invoeging

373
00:15:41,750 --> 00:15:44,501
en konstante tyd lookup.

374
00:15:44,501 --> 00:15:47,500
Die nadeel, natuurlik, is dat
hierdie Trie, soos jy kan waarskynlik sê,

375
00:15:47,500 --> 00:15:49,030
is groot.

376
00:15:49,030 --> 00:15:51,040
Elkeen van hierdie nodes
neem 'n baie ruimte.

377
00:15:51,040 --> 00:15:52,090
>> Maar dit is die nadeel.

378
00:15:52,090 --> 00:15:55,260
As ons wil regtig vinnig
inplanting, regtig vinnig te skrap,

379
00:15:55,260 --> 00:15:59,630
en regtig vinnig lookup, moet ons
het 'n baie data vlieg rond.

380
00:15:59,630 --> 00:16:03,590
Ons het ter syde te stel 'n baie ruimte
en geheue vir daardie data struktuur

381
00:16:03,590 --> 00:16:04,290
om te bestaan.

382
00:16:04,290 --> 00:16:05,415
>> En so dit is die nadeel.

383
00:16:05,415 --> 00:16:07,310
Maar dit lyk asof ons
kan dit gevind.

384
00:16:07,310 --> 00:16:09,560
Ons kon gevind dat
heilige graal van data strukture

385
00:16:09,560 --> 00:16:12,264
met 'n vinnige inplanting,
skrap, en soek.

386
00:16:12,264 --> 00:16:14,430
En miskien sal dit wees 'n
toepaslike data struktuur

387
00:16:14,430 --> 00:16:18,890
te gebruik vir enige inligting
ons probeer om die winkel.

388
00:16:18,890 --> 00:16:21,860
Ek is Doug Lloyd, dit is cs50.

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