1
00:00:00,000 --> 00:00:02,994
>> [MUSIC SPILLE]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Så vi har blitt inching nærmere
og nærmere den hellige gral av data

4
00:00:08,550 --> 00:00:13,050
strukturer, en som vi kan sette inn
inn, slette fra, og ser opp

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

6
00:00:15,440 --> 00:00:16,270
Høyre.

7
00:00:16,270 --> 00:00:17,280
Det er liksom i mål.

8
00:00:17,280 --> 00:00:19,720
Vi ønsker å være i stand til å gjøre
ting veldig, veldig raskt.

9
00:00:19,720 --> 00:00:22,580
>> Har vi funnet den her da
vi snakker om forsøk?

10
00:00:22,580 --> 00:00:23,670
Vel, la oss ta en titt.

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

12
00:00:25,628 --> 00:00:28,680
som håndterer kartlegging av
såkalt nøkkelverdipar,

13
00:00:28,680 --> 00:00:32,080
kartlegge noen stykke data
til noen annen del av data

14
00:00:32,080 --> 00:00:36,020
så vi vet hvor du finner
Informasjonen i strukturen.

15
00:00:36,020 --> 00:00:40,060
>> Så for matrisen, for eksempel,
Nøkkelen er element indeks eller matrise

16
00:00:40,060 --> 00:00:42,600
Plasseringen 0 eller matrisen 1 og så videre.

17
00:00:42,600 --> 00:00:46,140
Og verdien er dataene
som finnes på denne plasseringen.

18
00:00:46,140 --> 00:00:48,550
Så hva er lagret i matrisen 0?

19
00:00:48,550 --> 00:00:54,290
Hva blir lagret i matrisen en versus bare
0 og 1, som ville være tastene.

20
00:00:54,290 --> 00:00:56,360
>> Med en hash table er det
liksom den samme ideen.

21
00:00:56,360 --> 00:01:00,690
Med en hash table, har vi denne hash
funksjon som genererer hash-koder.

22
00:01:00,690 --> 00:01:03,670
Så nøkkelen er hash-kode av dataene.

23
00:01:03,670 --> 00:01:06,530
Og verdien, særlig
vi snakket om kjeding

24
00:01:06,530 --> 00:01:10,590
i videoen på hash tabeller,
er at lenket liste av data

25
00:01:10,590 --> 00:01:12,550
som hasher til at hashCode.

26
00:01:12,550 --> 00:01:14,050
Høyre.

27
00:01:14,050 --> 00:01:16,050
Hva om en annen tilnærming
denne metoden, skjønt?

28
00:01:16,050 --> 00:01:21,000
Hva om en metode der
Nøkkelen er garantert å være unik,

29
00:01:21,000 --> 00:01:25,410
i motsetning til en hash table, der vi kunne
ende opp med to deler av data

30
00:01:25,410 --> 00:01:27,200
som har samme hashCode.

31
00:01:27,200 --> 00:01:30,020
Og så må vi håndtere
at ved å enten sondering eller mer

32
00:01:30,020 --> 00:01:33,340
svis chaining å løse det problemet.

33
00:01:33,340 --> 00:01:37,520
>> Så nå kan vi garantere
at våre nøkkelen vil være unik.

34
00:01:37,520 --> 00:01:39,690
Og hva om vår verdi var
bare noe så enkelt

35
00:01:39,690 --> 00:01:44,080
som sant og usant som forteller oss om
eller ikke at opplysning

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

37
00:01:45,610 --> 00:01:48,180
En boolsk kan være så enkelt som en bit.

38
00:01:48,180 --> 00:01:52,660
Realistisk er det sannsynligvis en
byte mer sannsynlig enn en bit.

39
00:01:52,660 --> 00:01:55,410
Men det er mye mindre enn
lagring kanskje en 50-tegns streng,

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

41
00:01:57,360 --> 00:02:02,210
>> Så prøver, i likhet med hasj tabeller,
som kombinerer arrays og lenket liste,

42
00:02:02,210 --> 00:02:05,790
prøver kombinere matriser,
strukturer, og pekere

43
00:02:05,790 --> 00:02:08,509
sammen for å lagre data i
en interessant måte som er

44
00:02:08,509 --> 00:02:11,550
ganske forskjellig fra
noe vi har sett så langt.

45
00:02:11,550 --> 00:02:16,750
Nå bruker vi dataene som et veikart
å navigere denne datastrukturen.

46
00:02:16,750 --> 00:02:18,710
Og hvis vi kan følge
veikart, hvis vi kan

47
00:02:18,710 --> 00:02:22,390
Følg data fra
begynnelse til slutt, vil vi

48
00:02:22,390 --> 00:02:24,945
vet om at data
eksistere i trie.

49
00:02:24,945 --> 00:02:28,310
>> Og hvis vi ikke kan følge kartet
fra meningen å avslutte det hele tatt,

50
00:02:28,310 --> 00:02:30,600
dataene kan ikke eksistere.

51
00:02:30,600 --> 00:02:32,890
Igjen, nøklene her er
garantert å være unik.

52
00:02:32,890 --> 00:02:36,020
Og så i motsetning til en hash table, vil vi aldri
må forholde seg til kollisjoner her.

53
00:02:36,020 --> 00:02:39,090
Og ikke to stykker av data
har nøyaktig samme veikart

54
00:02:39,090 --> 00:02:40,530
hvis ikke at data er identiske.

55
00:02:40,530 --> 00:02:44,580
>> Hvis vi setter inn John, deretter
vi søker etter John.

56
00:02:44,580 --> 00:02:47,430
Det er to identiske stykker av
data, ikke sant, vi ser gjennom.

57
00:02:47,430 --> 00:02:49,880
Men ellers, noen
to stykker av data er

58
00:02:49,880 --> 00:02:52,750
garantert å ha unike veikart
gjennom denne datastruktur.

59
00:02:52,750 --> 00:02:56,210
Og vi kommer til å ta en titt på
en visuell av dette i løpet av et øyeblikk.

60
00:02:56,210 --> 00:02:58,810
>> Vi vil gjøre dette ved å prøve å
opprette en ny datastruktur,

61
00:02:58,810 --> 00:03:00,564
kartlegge følgende sentrale verdiparene.

62
00:03:00,564 --> 00:03:03,480
I dette tilfellet er vi ikke kommer til å bruke
noe så enkelt som en boolsk.

63
00:03:03,480 --> 00:03:06,200
Vi har faktisk lagrer strengen.

64
00:03:06,200 --> 00:03:08,690
Og at strengen skal
være navnet på et universitet.

65
00:03:08,690 --> 00:03:12,140
>> Og nøkkelen kommer til å bli året
da at universitetet ble grunnlagt.

66
00:03:12,140 --> 00:03:15,380
Alle år for universiteter
kommer til å være fire sifre.

67
00:03:15,380 --> 00:03:19,840
Og så vil vi bruke disse fire sifrene til
navigere gjennom denne datastrukturen.

68
00:03:19,840 --> 00:03:22,270
Og vi får se, igjen, hvordan
vi gjør det i løpet av et sekund.

69
00:03:22,270 --> 00:03:25,110
>> Ved slutten av banen,
vi får se navnet

70
00:03:25,110 --> 00:03:30,250
av universitetet som tilsvarer
til at viktige, de fire sifre.

71
00:03:30,250 --> 00:03:34,390
Den grunnleggende ideen bak en trie
er at vi har en sentral rute.

72
00:03:34,390 --> 00:03:35,640
Så tenk på det som et tre.

73
00:03:35,640 --> 00:03:39,211
Og dette er lik i rettskrivning
og i konseptet til et tre.

74
00:03:39,211 --> 00:03:41,460
Vanligvis når vi tenker på
trær i den virkelige verden,

75
00:03:41,460 --> 00:03:44,090
de har en rot som er i
bakken og de vokser oppover

76
00:03:44,090 --> 00:03:46,830
og de har avdelinger
og de har blader.

77
00:03:46,830 --> 00:03:49,450
Og i utgangspunktet ideen om
en trie er akkurat det samme,

78
00:03:49,450 --> 00:03:51,755
bortsett fra at roten er forankret
et sted i himmelen.

79
00:03:51,755 --> 00:03:53,130
Og bladene er på bunnen.

80
00:03:53,130 --> 00:03:55,750
>> Så det er litt som å ta et tre
og bare vende det opp ned.

81
00:03:55,750 --> 00:03:56,880
Men det er fortsatt grener.

82
00:03:56,880 --> 00:03:59,463
Og de ville være våre veier,
de vil være våre forbindelser

83
00:03:59,463 --> 00:04:02,220
fra roten til bladene.

84
00:04:02,220 --> 00:04:04,200
I dette tilfelle de som er
stier, disse grenene

85
00:04:04,200 --> 00:04:08,490
er merket med tall som forteller oss
hvilken vei å gå fra der vi er.

86
00:04:08,490 --> 00:04:11,800
>> Hvis vi ser en 0, går vi ned denne grenen,
hvis vi ser en 1, går vi ned denne grenen,

87
00:04:11,800 --> 00:04:12,900
og så og så videre.

88
00:04:12,900 --> 00:04:14,060
Vel, hva betyr dette?

89
00:04:14,060 --> 00:04:16,519
Vel, det betyr at
på hvert knutepunkt

90
00:04:16,519 --> 00:04:19,260
og hver node i
midten og hver gren,

91
00:04:19,260 --> 00:04:23,020
det er 10 mulige
steder som vi kan gå.

92
00:04:23,020 --> 00:04:27,690
Så det er 10 pekere
fra hvert sted.

93
00:04:27,690 --> 00:04:30,610
>> Og det er her prøver kan få en
litt skremmende for noen

94
00:04:30,610 --> 00:04:34,460
som er ikke har mye
erfaring i datavitenskap før.

95
00:04:34,460 --> 00:04:35,960
Men prøver er egentlig ganske utrolig.

96
00:04:35,960 --> 00:04:37,793
Og hvis du har
muligheten til å jobbe med dem

97
00:04:37,793 --> 00:04:40,420
og du er villig til å grave-in
og eksperimentere med dem,

98
00:04:40,420 --> 00:04:44,234
de er egentlig ganske interessant
datastrukturer å jobbe med.

99
00:04:44,234 --> 00:04:46,900
Hvis vi ønsker å sette inn et element
inn i trie, alt vi trenger å gjøre

100
00:04:46,900 --> 00:04:51,360
er å bygge riktig bane
fra roten til bladet.

101
00:04:51,360 --> 00:04:55,390
Her er hva hvert steg
den måten kan se ut.

102
00:04:55,390 --> 00:04:59,660
Vi kommer til å definere en ny data
Strukturen for en ny node som kalles en trie.

103
00:04:59,660 --> 00:05:02,560
>> Og innsiden av at data
Strukturen det er to stykker.

104
00:05:02,560 --> 00:05:05,460
Vi kommer til å lagre
navn på et universitet.

105
00:05:05,460 --> 00:05:09,410
Og vi kommer til å lagre
en rekke pekere

106
00:05:09,410 --> 00:05:12,190
til andre noder av samme type.

107
00:05:12,190 --> 00:05:14,780
Så, igjen, dette er den slags
av begrepet overalt

108
00:05:14,780 --> 00:05:18,567
vi er, vi på 10 mulige
steder vi kan gå.

109
00:05:18,567 --> 00:05:20,150
Hvis vi ser en 0, går vi ned denne grenen.

110
00:05:20,150 --> 00:05:22,690
Hvis vi ser en en, denne grenen,
og så videre og så videre og så videre.

111
00:05:22,690 --> 00:05:25,160
Hvis vi sier 9, går vi ned denne grenen.

112
00:05:25,160 --> 00:05:28,220
Så på hvert knutepunkt,
vi kan gå 10 mulige steder.

113
00:05:28,220 --> 00:05:35,740
Så hver node må inneholde 10 pekere
til andre noder, til 10 andre noder.

114
00:05:35,740 --> 00:05:39,810
>> Og dataene vi lagrer er
bare navnet på universitetet.

115
00:05:39,810 --> 00:05:41,060
Så la oss bygge en trie.

116
00:05:41,060 --> 00:05:44,860
La oss sette inn et par
av elementer i vår trie.

117
00:05:44,860 --> 00:05:46,740
Så helt på toppen,
dette er vår root node.

118
00:05:46,740 --> 00:05:49,740
Dette er trolig kommer til å være noe
du kommer til globalt olle.

119
00:05:49,740 --> 00:05:53,450
Og du kommer til globalt opprett
en peker til denne noden alltid.

120
00:05:53,450 --> 00:05:55,360
>> Du kommer til å si,
root lik, og du er

121
00:05:55,360 --> 00:05:57,580
kommer til malloc selv trie node.

122
00:05:57,580 --> 00:05:59,850
Og du aldri kommer
å røre rot igjen.

123
00:05:59,850 --> 00:06:02,300
Hver gang du vil
begynne å navigere gjennom,

124
00:06:02,300 --> 00:06:05,802
du setter en annen pekeren
lik rot, slik som trav,

125
00:06:05,802 --> 00:06:07,760
som er eksempel I
bruker i mange av mine videoer

126
00:06:07,760 --> 00:06:11,090
her på stabler og køer
og link lister og så videre.

127
00:06:11,090 --> 00:06:13,320
>> Du setter en annen peker
kalt trav for traversering.

128
00:06:13,320 --> 00:06:15,890
Og du bruker trav å navigere
gjennom datastrukturen.

129
00:06:15,890 --> 00:06:17,500
Så la oss se hvordan dette kan se ut.

130
00:06:17,500 --> 00:06:19,880
Så akkurat nå, hva
ikke en node se ut?

131
00:06:19,880 --> 00:06:22,920
Vel, akkurat som våre data
struktur erklæring antydet,

132
00:06:22,920 --> 00:06:26,906
vi har en streng, hvilken
i dette tilfellet er tom.

133
00:06:26,906 --> 00:06:27,780
Det er ingenting her.

134
00:06:27,780 --> 00:06:29,550
>> Og en rekke 10 pekere.

135
00:06:29,550 --> 00:06:31,790
Og akkurat nå, bare vi
har en node i dette trie.

136
00:06:31,790 --> 00:06:33,110
Det er ingenting annet i det.

137
00:06:33,110 --> 00:06:36,020
Så alt 10 av dem
pekere punkt til null.

138
00:06:36,020 --> 00:06:38,090
Det er det den røde indikerer.

139
00:06:38,090 --> 00:06:39,500
>> La oss sette strengen Harvard.

140
00:06:39,500 --> 00:06:41,999
La oss sette Universitetet i
Harvard inn i denne trie, som

141
00:06:41,999 --> 00:06:43,940
ble grunnlagt i år 1 636.

142
00:06:43,940 --> 00:06:48,220
Vi ønsker å bruke nøkkelen,
1636, for å fortelle oss hvor vi er

143
00:06:48,220 --> 00:06:50,140
skal lagre Harvard i trie.

144
00:06:50,140 --> 00:06:51,470
Nå, hvordan kan vi gjøre det?

145
00:06:51,470 --> 00:06:52,886
>> Det kan se ut omtrent som dette.

146
00:06:52,886 --> 00:06:54,160
Vi starter ved roten.

147
00:06:54,160 --> 00:06:56,920
Og vi har disse 10 stedene vi kan gå.

148
00:06:56,920 --> 00:06:59,900
Roten er akkurat som en hvilken som helst
annen node i trie.

149
00:06:59,900 --> 00:07:02,850
Det er 10 plasser vi kan gå herfra.

150
00:07:02,850 --> 00:07:07,215
>> Hvor skal vi sannsynligvis vil
å gå hvis nøkkelen er 1 636?

151
00:07:07,215 --> 00:07:08,340
Det er egentlig to alternativer.

152
00:07:08,340 --> 00:07:08,450
Høyre.

153
00:07:08,450 --> 00:07:10,825
Vi kan bygge ut nøkkelen
høyre til venstre og starte med seks.

154
00:07:10,825 --> 00:07:14,000
Eller vi kunne bygge nøkkelen fra
venstre til høyre og starte med en.

155
00:07:14,000 --> 00:07:16,140
>> Det er nok mer
intuitivt som et menneske

156
00:07:16,140 --> 00:07:18,110
å forstå vi vil
bare gå til venstre mot høyre.

157
00:07:18,110 --> 00:07:21,140
Og så hvis jeg ønsker å sette inn
Harvard inn i denne trie,

158
00:07:21,140 --> 00:07:23,560
Jeg ønsker sannsynligvis å starte
ved å starte ved roten,

159
00:07:23,560 --> 00:07:25,720
ser på mine 10 alternativer
foran meg, og sa

160
00:07:25,720 --> 00:07:28,700
Jeg ønsker å gå ned en bane.

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

162
00:07:29,700 --> 00:07:31,810
>> Nå er en bane for tiden null.

163
00:07:31,810 --> 00:07:35,920
Så hvis jeg ønsker å fortsette ned banen
å sette dette elementet inn i trie,

164
00:07:35,920 --> 00:07:42,040
Jeg må malloc en ny node, har en
peke der, og da er jeg god til å gå.

165
00:07:42,040 --> 00:07:46,460
>> Så jeg i utgangspunktet er på et
punkt hvor jeg står

166
00:07:46,460 --> 00:07:50,270
ved roten av treet, eller
trie og det er 10 grener.

167
00:07:50,270 --> 00:07:52,260
Men hver gren har en
gate foran den.

168
00:07:52,260 --> 00:07:53,060
Høyre.

169
00:07:53,060 --> 00:07:54,850
Fordi det er ikke noe annet er det.

170
00:07:54,850 --> 00:07:56,522
Ingen trygg passasje.

171
00:07:56,522 --> 00:07:58,980
Det betyr at det er ingenting
ned noen av disse grenene.

172
00:07:58,980 --> 00:08:02,532
Hvis jeg ønsker å begynne å bygge
noe jeg ønsker å fjerne porten.

173
00:08:02,532 --> 00:08:04,490
Jeg ønsker å fjerne porten
foran nummer en.

174
00:08:04,490 --> 00:08:05,698
Og jeg ønsker å gå ned den.

175
00:08:05,698 --> 00:08:08,060
Og jeg ønsker å bygge
et annet sted for meg å gå.

176
00:08:08,060 --> 00:08:09,470
>> Og det er det jeg har gjort her.

177
00:08:09,470 --> 00:08:11,430
Så en ikke lenger peker til null.

178
00:08:11,430 --> 00:08:13,830
Jeg har sagt det er trygt å gå ned her nå.

179
00:08:13,830 --> 00:08:15,789
Jeg bygde en annen node.

180
00:08:15,789 --> 00:08:18,330
Og når jeg kommer til det node, jeg
har en annen avgjørelse å ta.

181
00:08:18,330 --> 00:08:20,890
Hvor skal jeg gå herfra?

182
00:08:20,890 --> 00:08:22,700
>> Vel, jeg har allerede gått ned en.

183
00:08:22,700 --> 00:08:24,470
Så nå vil jeg sannsynligvis til å gå ned 6.

184
00:08:24,470 --> 00:08:24,970
Høyre.

185
00:08:24,970 --> 00:08:27,100
Igjen, jeg har 10 steder jeg kan velge.

186
00:08:27,100 --> 00:08:30,060
Så la oss nå gå ned nummer seks.

187
00:08:30,060 --> 00:08:32,280
Så jeg fjerne gate
foran nummer 6.

188
00:08:32,280 --> 00:08:33,250
Og jeg går der nede.

189
00:08:33,250 --> 00:08:34,580
Og jeg bygge en annen node.

190
00:08:34,580 --> 00:08:37,630
Og jeg har nådd et annet knutepunkt.

191
00:08:37,630 --> 00:08:40,289
>> Igjen, jeg har 10 valg
for hvor jeg kan gå.

192
00:08:40,289 --> 00:08:42,799
Jeg har flyttet fra 1 til 6.

193
00:08:42,799 --> 00:08:44,215
Så nå vil jeg trolig gå til tre.

194
00:08:44,215 --> 00:08:45,381
3, det er intet jeg kan gå.

195
00:08:45,381 --> 00:08:48,980
Så jeg må rydde veien
og bygge meg en ny plass.

196
00:08:48,980 --> 00:08:50,870
Og så fra 3, der jeg ønsker å gå gjøre?

197
00:08:50,870 --> 00:08:52,450
Jeg ønsker å gå ned 6.

198
00:08:52,450 --> 00:08:54,770
>> Og, igjen, måtte jeg
rydde vei for å gjøre det.

199
00:08:54,770 --> 00:08:59,179
Så nå har jeg brukt min nøkkel til å sette opprette
noder og begynne å bygge denne trie.

200
00:08:59,179 --> 00:09:00,220
Jeg har begynt på roten.

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

202
00:09:03,666 --> 00:09:05,540
Og nå er jeg på bunnen
der på at node.

203
00:09:05,540 --> 00:09:06,610
Og du kan være i stand til å
ser det på skjermen.

204
00:09:06,610 --> 00:09:07,735
>> Det er markert med gult.

205
00:09:07,735 --> 00:09:10,020
Det er der jeg er i dag.

206
00:09:10,020 --> 00:09:11,300
Min nøkkel er gjort.

207
00:09:11,300 --> 00:09:13,030
Jeg har brukt opp alle posisjoner i min nøkkel.

208
00:09:13,030 --> 00:09:15,040
Så jeg kan ikke gå videre.

209
00:09:15,040 --> 00:09:17,720
Så på dette punktet, alt jeg
virkelig trenger å gjøre er å si, OK.

210
00:09:17,720 --> 00:09:18,990
Det er typen som ser
ned på bakken,

211
00:09:18,990 --> 00:09:21,115
hvis du se for oss
selv som denne typen bane

212
00:09:21,115 --> 00:09:22,350
med forskjellige tilkoblinger.

213
00:09:22,350 --> 00:09:25,800
Liksom ser ned og liksom
spray maling Harvard på bakken.

214
00:09:25,800 --> 00:09:26,800
Det er navnet på denne.

215
00:09:26,800 --> 00:09:28,300
Vet det er det som er på dette stedet.

216
00:09:28,300 --> 00:09:31,870
Hvis vi begynner ved roten og vi går ned
1 og deretter 6 og deretter 3 og deretter 6,

217
00:09:31,870 --> 00:09:32,780
hvor er vi?

218
00:09:32,780 --> 00:09:35,640
Vel, hvis vi ser ned
og vi ser Harvard, deretter

219
00:09:35,640 --> 00:09:38,960
vi vet at Harvard var
grunnlagt i 1636 basert på den måten

220
00:09:38,960 --> 00:09:41,400
vi implementere dette datastruktur.

221
00:09:41,400 --> 00:09:43,177
Så det var forhåpentligvis grei.

222
00:09:43,177 --> 00:09:44,760
Vi kommer til å gjøre to flere innsettinger.

223
00:09:44,760 --> 00:09:50,060
Og forhåpentligvis vil det bidra til å
ser dette gjøres to ganger mer.

224
00:09:50,060 --> 00:09:52,210
>> Nå, la oss sette inn et annet universitet.

225
00:09:52,210 --> 00:09:54,630
La oss sette Yale inn i denne trie.

226
00:09:54,630 --> 00:09:57,037
Yale ble grunnlagt i 1701.

227
00:09:57,037 --> 00:09:58,870
Så vi vil starte på
rot, som vi alltid gjør.

228
00:09:58,870 --> 00:09:59,890
Og vi setter en traversering pekeren.

229
00:09:59,890 --> 00:10:01,624
Vi kommer til å bruke den til å bevege seg gjennom.

230
00:10:01,624 --> 00:10:03,790
Det første vi ønsker å
gjøre er å gå nedover en sti.

231
00:10:03,790 --> 00:10:05,830
Det er det første sifferet av våre viktigste.

232
00:10:05,830 --> 00:10:08,420
Heldigvis skjønt, gjør vi ikke
nødt til å gjøre noe arbeid denne gangen.

233
00:10:08,420 --> 00:10:09,919
Den en bane er allerede fjernet.

234
00:10:09,919 --> 00:10:13,520
Jeg ryddet det tidligere når jeg
ble satt inn Harvard i 1636.

235
00:10:13,520 --> 00:10:18,090
Så jeg kan trygt bevege
ned en og bare gå dit.

236
00:10:18,090 --> 00:10:20,150
Hvis kan flytte ned en.

237
00:10:20,150 --> 00:10:22,930
>> Men nå ønsker jeg å gå til syv.

238
00:10:22,930 --> 00:10:24,280
Jeg ryddet vei på seks.

239
00:10:24,280 --> 00:10:27,050
Jeg vet jeg kan trygt
fortsett nedover 6 banen.

240
00:10:27,050 --> 00:10:29,220
Men jeg trenger å gå på 7 banen.

241
00:10:29,220 --> 00:10:30,580
Så hva må jeg gjøre?

242
00:10:30,580 --> 00:10:35,070
Vel, akkurat som før, jeg trenger bare
å fjerne gate, komme seg ut av veien,

243
00:10:35,070 --> 00:10:38,740
og bygge en ny node fra 7 banen.

244
00:10:38,740 --> 00:10:40,250
Akkurat som dette.

245
00:10:40,250 --> 00:10:42,930
>> Så nå har jeg flyttet en og deretter 7.

246
00:10:42,930 --> 00:10:45,550
Og nå legger merke til, er jeg liksom
av på denne nye subbranch.

247
00:10:45,550 --> 00:10:46,050
Høyre.

248
00:10:46,050 --> 00:10:49,260
Alt annet fra 16
på, jeg bryr meg ikke om.

249
00:10:49,260 --> 00:10:50,720
Jeg gjør ikke 16 noe.

250
00:10:50,720 --> 00:10:51,750
Jeg gjør 17 ting.

251
00:10:51,750 --> 00:10:58,380
>> Så nå fra 17 på, jeg må
slags flamme nye stier her.

252
00:10:58,380 --> 00:11:00,462
Det neste sifferet min nøkkel er 0.

253
00:11:00,462 --> 00:11:01,670
Jeg tydeligvis ikke kan komme hvor som helst.

254
00:11:01,670 --> 00:11:02,628
Jeg bare bygget denne noden.

255
00:11:02,628 --> 00:11:04,550
Så jeg vet er det ingen
stier fremover herfra.

256
00:11:04,550 --> 00:11:06,370
Så jeg må lage en selv.

257
00:11:06,370 --> 00:11:09,360
>> Så jeg malloc en ny node
og har 0 poeng der.

258
00:11:09,360 --> 00:11:12,770
Og så en gang til, malloc jeg en
ny node og har ett poeng der.

259
00:11:12,770 --> 00:11:15,870
Igjen, jeg har brukt opp min nøkkel, 1701.

260
00:11:15,870 --> 00:11:18,472
Så jeg ser ned og jeg spraymaling Yale.

261
00:11:18,472 --> 00:11:19,680
Det er navnet på denne noden.

262
00:11:19,680 --> 00:11:24,660
>> Og så nå hvis jeg noen gang trenger å se om Yale
er i denne trie, begynner jeg ved roten,

263
00:11:24,660 --> 00:11:27,060
Jeg går ned 1701, og ser ned.

264
00:11:27,060 --> 00:11:30,030
Og hvis jeg ser Yale spray
malt på bakken, og deretter

265
00:11:30,030 --> 00:11:32,200
Jeg vet Yale eksisterer i denne trie.

266
00:11:32,200 --> 00:11:32,950
La oss gjøre en mer.

267
00:11:32,950 --> 00:11:36,430
La oss sette Dartmouth i denne
trie, som ble grunnlagt i 1769.

268
00:11:36,430 --> 00:11:37,750
>> Start ved roten igjen.

269
00:11:37,750 --> 00:11:39,445
Min første sifferet i min nøkkel er en.

270
00:11:39,445 --> 00:11:40,820
Jeg kan trygt flytte ned den veien.

271
00:11:40,820 --> 00:11:42,400
Det finnes allerede.

272
00:11:42,400 --> 00:11:44,040
Det neste sifferet i nøkkelen min er 7.

273
00:11:44,040 --> 00:11:45,890
Jeg kan trygt flytte ned den veien.

274
00:11:45,890 --> 00:11:47,540
Det eksisterer også.

275
00:11:47,540 --> 00:11:49,000
>> Min neste er 6.

276
00:11:49,000 --> 00:11:52,860
Herfra fra der jeg er i dag
i gult der i det midterste node,

277
00:11:52,860 --> 00:11:56,060
6 er for øyeblikket låst av.

278
00:11:56,060 --> 00:11:58,830
Hvis jeg ønsker å gå ned den veien,
Jeg har til å bygge det selv.

279
00:11:58,830 --> 00:12:02,250
Så jeg skal malloc en ny node
og har seks poeng der.

280
00:12:02,250 --> 00:12:04,250
Og så, igjen, jeg er
Lynrask nye stier her.

281
00:12:04,250 --> 00:12:10,750
>> Så jeg malloc en ny node, slik at det fra
at node-- banen tall 9-- og deretter nå

282
00:12:10,750 --> 00:12:13,584
hvis jeg reiser 1769 og jeg ser ned.

283
00:12:13,584 --> 00:12:15,500
Det er ingenting i dag
spray malt der.

284
00:12:15,500 --> 00:12:16,930
Jeg kan skrive Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Og jeg har satt inn
Dartmouth i den trie.

286
00:12:20,710 --> 00:12:23,450
>> Så det er å sette inn
ting inn i trie.

287
00:12:23,450 --> 00:12:25,384
Nå ønsker vi å søke etter ting.

288
00:12:25,384 --> 00:12:27,050
Hvordan søker vi etter ting i trie?

289
00:12:27,050 --> 00:12:29,170
Vel, det er ganske mye den samme ideen.

290
00:12:29,170 --> 00:12:33,620
Nå er vi bare bruke sifrene nøkkelen
for å se om vi kan navigere fra roten

291
00:12:33,620 --> 00:12:37,170
til der vi ønsker å gå i trie.

292
00:12:37,170 --> 00:12:41,620
>> Hvis vi treffer en blindvei på noe punkt, deretter
vi vet at dette elementet ikke kan finnes

293
00:12:41,620 --> 00:12:44,500
eller annet som bane ville
har allerede blitt fjernet.

294
00:12:44,500 --> 00:12:45,930
Hvis vi gjør det hele veien til
Til slutt, alt vi trenger å gjøre

295
00:12:45,930 --> 00:12:48,471
er å se ned og se om det er
elementet vi leter etter.

296
00:12:48,471 --> 00:12:49,335
Hvis det er, suksess.

297
00:12:49,335 --> 00:12:52,610
Hvis det ikke, mislykkes.

298
00:12:52,610 --> 00:12:54,940
>> Så la oss søke etter
Harvard i denne trie.

299
00:12:54,940 --> 00:12:56,020
Vi starter ved roten.

300
00:12:56,020 --> 00:12:58,228
Og, igjen, vi kommer til å
skape en traversering peker

301
00:12:58,228 --> 00:12:59,390
å gjøre våre beveger seg for oss.

302
00:12:59,390 --> 00:13:02,080
Fra roten vi vet at
første stedet vi trenger å gå er en,

303
00:13:02,080 --> 00:13:03,390
kan vi gjøre det?

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

305
00:13:03,982 --> 00:13:04,690
Hvis trygt eksisterer.

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

307
00:13:06,660 --> 00:13:08,440
>> Nå, det neste stedet vi trenger å gå er 6.

308
00:13:08,440 --> 00:13:10,557
Eksisterer den 6 sti herfra?

309
00:13:10,557 --> 00:13:11,140
Ja, det gjør det.

310
00:13:11,140 --> 00:13:12,690
Vi kan gå ned 6 banen.

311
00:13:12,690 --> 00:13:13,905
Og vi ender opp her.

312
00:13:13,905 --> 00:13:16,130
>> Kan vi gå ned tre stien herfra?

313
00:13:16,130 --> 00:13:18,450
Vel, som det viser seg,
ja, det finnes også.

314
00:13:18,450 --> 00:13:20,790
Og kan vi få på seks sti herfra?

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

316
00:13:21,982 --> 00:13:24,002
>> Vi har ikke helt svarte
spørsmålet ennå.

317
00:13:24,002 --> 00:13:25,710
Det er fortsatt en mer
trinn, som nå er

318
00:13:25,710 --> 00:13:28,520
vi trenger å se ned og
se om det er actually--

319
00:13:28,520 --> 00:13:32,660
hvis vi leter etter Harvard, er at
hva vi finner når vi utmatte nøkkelen?

320
00:13:32,660 --> 00:13:35,430
I eksempelet bruker vi her,
årene er alltid fire sifre.

321
00:13:35,430 --> 00:13:40,280
Men du kanskje bruker eksempelet der
du lagrer en ordbok med ord.

322
00:13:40,280 --> 00:13:44,060
>> Og så i stedet for å ha 10 pekere
for min plassering, kan du ha 26.

323
00:13:44,060 --> 00:13:46,040
Én for hver bokstav i alfabetet.

324
00:13:46,040 --> 00:13:50,350
Og er det noen ord som balltre,
som er en undergruppe av batch, f.eks.

325
00:13:50,350 --> 00:13:53,511
Og så selv om du kommer til
enden av nøkkelen, og du ser ned,

326
00:13:53,511 --> 00:13:55,260
du kan ikke se hva
du leter etter.

327
00:13:55,260 --> 00:13:58,500
>> Så har du alltid å traversere
hele banen og deretter

328
00:13:58,500 --> 00:14:01,540
hvis du var vellykket stand
å krysse hele banen,

329
00:14:01,540 --> 00:14:03,440
se ned og gjøre en endelig bekreftelse.

330
00:14:03,440 --> 00:14:05,120
Er det det jeg leter etter?

331
00:14:05,120 --> 00:14:07,740
Vel, jeg ser ned etter start
ved toppen og går 1.636.

332
00:14:07,740 --> 00:14:08,240
Jeg ser ned.

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

334
00:14:09,400 --> 00:14:11,689
Så, ja, lyktes jeg.

335
00:14:11,689 --> 00:14:13,980
Hva om det jeg leter etter
er ikke i trie, skjønt.

336
00:14:13,980 --> 00:14:17,200
Hva om jeg leter etter Princeton,
som ble grunnlagt i 1746.

337
00:14:17,200 --> 00:14:20,875
Og så 1 746 blir min nøkkel
å navigere gjennom trie.

338
00:14:20,875 --> 00:14:22,040
Vel, jeg begynner ved roten.

339
00:14:22,040 --> 00:14:24,760
Og det første stedet jeg vil ha
å går nedover en sti.

340
00:14:24,760 --> 00:14:25,590
Kan jeg gjøre det?

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

342
00:14:26,490 --> 00:14:28,730
>> Kan jeg gå ned 7 sti derfra?

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

344
00:14:29,230 --> 00:14:30,750
Det finnes også.

345
00:14:30,750 --> 00:14:32,460
Men kan jeg gå ned fire sti herfra?

346
00:14:32,460 --> 00:14:35,550
Det er som å stille spørsmålet, kan
Jeg går ned den lille firkanten

347
00:14:35,550 --> 00:14:37,114
som jeg har uthevet i gult?

348
00:14:37,114 --> 00:14:38,030
Det er ingenting der.

349
00:14:38,030 --> 00:14:38,610
Høyre.

350
00:14:38,610 --> 00:14:41,310
>> Det er ingen vei videre nedover fire bane.

351
00:14:41,310 --> 00:14:46,480
Hvis Princeton var i dette trie, at fire
ville ha blitt ryddet for oss allerede.

352
00:14:46,480 --> 00:14:49,130
Og så på dette punktet
Vi har nådd en blindvei.

353
00:14:49,130 --> 00:14:50,250
Vi kan ikke gå videre.

354
00:14:50,250 --> 00:14:53,440
Og så kan vi si, definitivt, nei.

355
00:14:53,440 --> 00:14:56,760
Princeton finnes ikke i dette trie.

356
00:14:56,760 --> 00:14:58,860
>> Så hva betyr alt dette?

357
00:14:58,860 --> 00:14:59,360
Høyre.

358
00:14:59,360 --> 00:15:01,000
Det er mye som skjer her.

359
00:15:01,000 --> 00:15:02,500
Det finnes pekere over alt.

360
00:15:02,500 --> 00:15:04,249
Og, som du kan se
bare fra diagrammet,

361
00:15:04,249 --> 00:15:07,010
det er mye av noder som
er slags flyr rundt.

362
00:15:07,010 --> 00:15:13,480
Men legg merke til hver gang vi ønsket å
sjekke om noe var i trie,

363
00:15:13,480 --> 00:15:15,000
vi bare måtte gjøre 4 trekk.

364
00:15:15,000 --> 00:15:17,208
>> Hver gang vi ønsket å
sette noe i trie,

365
00:15:17,208 --> 00:15:20,440
vi har å gjøre 4 trekk, muligens
mallocing noen ting underveis.

366
00:15:20,440 --> 00:15:23,482
Men som vi så når vi satt inn
Dartmouth i den trie,

367
00:15:23,482 --> 00:15:25,940
noen ganger noen av banen
kan allerede være ryddet for oss.

368
00:15:25,940 --> 00:15:30,520
Og slik som vår trie blir større og
større, har vi mindre arbeid hver gang

369
00:15:30,520 --> 00:15:32,270
for å sette inn nye ting
fordi vi allerede har

370
00:15:32,270 --> 00:15:35,746
bygget mye av den mellomliggende
grener langs veien.

371
00:15:35,746 --> 00:15:38,370
Hvis vi bare trenger å se på
4 ting, er fire bare en konstant.

372
00:15:38,370 --> 00:15:41,750
Vi er slags nærmer
konstant tid innsetting

373
00:15:41,750 --> 00:15:44,501
og konstant tid oppslag.

374
00:15:44,501 --> 00:15:47,500
Ulempen er selvfølgelig være at
dette trie, som du kan sikkert fortelle,

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

376
00:15:49,030 --> 00:15:51,040
Hver og en av disse nodene
tar opp mye plass.

377
00:15:51,040 --> 00:15:52,090
>> Men det er kompromisset.

378
00:15:52,090 --> 00:15:55,260
Hvis vi ønsker virkelig rask
innsetting, virkelig rask sletting,

379
00:15:55,260 --> 00:15:59,630
og veldig rask oppslag, må vi
har mye data som flyr rundt.

380
00:15:59,630 --> 00:16:03,590
Vi må sette av mye plass
og minne for den datastrukturen

381
00:16:03,590 --> 00:16:04,290
å eksistere.

382
00:16:04,290 --> 00:16:05,415
>> Og så det er kompromisset.

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

384
00:16:07,310 --> 00:16:09,560
Vi har kanskje funnet ut at
hellige gral av datastrukturer

385
00:16:09,560 --> 00:16:12,264
med rask innsetting,
sletting, og oppslag.

386
00:16:12,264 --> 00:16:14,430
Og kanskje dette vil være en
passende datastrukturen

387
00:16:14,430 --> 00:16:18,890
til bruk for den informasjonen
vi prøver å lagre.

388
00:16:18,890 --> 00:16:21,860
Jeg er Doug Lloyd, dette er CS50.

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