1
00:00:00,000 --> 00:00:02,994
>> [Musik spiller]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Så vi har været udtørrede tættere
og tættere at hellige gral af data

4
00:00:08,550 --> 00:00:13,050
strukturer, som vi kan indsætte
ind, slette fra, og se op

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

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

7
00:00:16,270 --> 00:00:17,280
Det er en slags målet.

8
00:00:17,280 --> 00:00:19,720
Vi ønsker at være i stand til at gøre
tingene meget, meget hurtigt.

9
00:00:19,720 --> 00:00:22,580
>> Har vi fandt det her, når
vi taler om forsøg?

10
00:00:22,580 --> 00:00:23,670
Nå, lad os tage et kig.

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

12
00:00:25,628 --> 00:00:28,680
at håndtere kortlægning af
såkaldte nøgleværdipar,

13
00:00:28,680 --> 00:00:32,080
kortlægning nogle stykke data
til en anden stykke data

14
00:00:32,080 --> 00:00:36,020
så vi ved, hvor man kan finde
oplysninger i strukturen.

15
00:00:36,020 --> 00:00:40,060
>> Så for array, for eksempel
Nøglen er elementet indeks eller matrix

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

17
00:00:42,600 --> 00:00:46,140
Og værdien er dataene
der eksisterer på dette sted.

18
00:00:46,140 --> 00:00:48,550
Så hvad der er gemt i arrayet 0?

19
00:00:48,550 --> 00:00:54,290
Hvad der er gemt i arrayet 1 versus blot
0 og 1, som ville være nøglerne.

20
00:00:54,290 --> 00:00:56,360
>> Med en hash tabel er det
slags den samme idé.

21
00:00:56,360 --> 00:01:00,690
Med en hash tabel, har vi denne hash
funktion, der genererer hash-koder.

22
00:01:00,690 --> 00:01:03,670
Så det vigtigste er hash koden for de data.

23
00:01:03,670 --> 00:01:06,530
Og værdien, især
vi talte om at kæde

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

25
00:01:10,590 --> 00:01:12,550
der hashes til denne hashCode.

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

27
00:01:14,050 --> 00:01:16,050
Hvad med en anden tilgang
denne metode, selvom?

28
00:01:16,050 --> 00:01:21,000
Hvad med en metode, hvor
nøglen er garanteret at være unikke,

29
00:01:21,000 --> 00:01:25,410
i modsætning til en hash tabel, hvor vi kunne
ender med to stykker data

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

31
00:01:27,200 --> 00:01:30,020
Og så er vi nødt til at beskæftige sig med
at ved enten sondering eller derover

32
00:01:30,020 --> 00:01:33,340
helst kæde at løse dette problem.

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

34
00:01:37,520 --> 00:01:39,690
Og hvad hvis vores værdi var
bare noget så nemt

35
00:01:39,690 --> 00:01:44,080
som sandt og falsk, der fortæller os, om
eller ikke at stykke oplysninger

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

37
00:01:45,610 --> 00:01:48,180
En boolesk kunne være så simpelt som en smule.

38
00:01:48,180 --> 00:01:52,660
Realistisk er det sandsynligvis en
byte mere sandsynligt end en smule.

39
00:01:52,660 --> 00:01:55,410
Men det er meget mindre end
lagring måske en streng 50 tegn,

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

41
00:01:57,360 --> 00:02:02,210
>> Så forsøg, svarende til hash tabeller,
som kombinerer arrays og linkede liste,

42
00:02:02,210 --> 00:02:05,790
forsøger kombinere arrays,
strukturer, og henvisninger

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

44
00:02:08,509 --> 00:02:11,550
temmelig forskellig fra
noget vi har set hidtil.

45
00:02:11,550 --> 00:02:16,750
Nu bruger vi data som en køreplan
at navigere denne datastruktur.

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

47
00:02:18,710 --> 00:02:22,390
Følg data fra
begyndelsen til slutningen, vi får

48
00:02:22,390 --> 00:02:24,945
vide, om disse data
findes i trie.

49
00:02:24,945 --> 00:02:28,310
>> Og hvis vi ikke kan følge kortet
fra hvilket betyder at ende på alle,

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

51
00:02:30,600 --> 00:02:32,890
Igen nøglerne her
garanteret at være unik.

52
00:02:32,890 --> 00:02:36,020
Og så i modsætning en hash tabel, vil vi aldrig
har at gøre med kollisioner her.

53
00:02:36,020 --> 00:02:39,090
Og ikke to stykker data
har nøjagtig samme køreplan

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

55
00:02:40,530 --> 00:02:44,580
>> Hvis vi indsætter John, derefter
Vi søger efter John.

56
00:02:44,580 --> 00:02:47,430
Det er to identiske stykker
data, højre, vi kigger igennem.

57
00:02:47,430 --> 00:02:49,880
Men ellers enhver
to stykker af data

58
00:02:49,880 --> 00:02:52,750
garanteret at have unikke køreplaner
gennem denne datastruktur.

59
00:02:52,750 --> 00:02:56,210
Og vi kommer til at tage et kig på
en visuel af denne på blot et øjeblik.

60
00:02:56,210 --> 00:02:58,810
>> Vi vil gøre dette ved at forsøge at
oprette en ny datastruktur,

61
00:02:58,810 --> 00:03:00,564
kortlægning følgende centrale værdi par.

62
00:03:00,564 --> 00:03:03,480
I dette tilfælde er vi ikke kommer til at bruge
noget så simpelt som en boolesk.

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

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

65
00:03:08,690 --> 00:03:12,140
>> Og nøglen bliver året
når at universitetet blev grundlagt.

66
00:03:12,140 --> 00:03:15,380
Alle år for universiteterne
vil være fire cifre.

67
00:03:15,380 --> 00:03:19,840
Og så vi vil bruge disse fire cifre til
navigere gennem denne datastruktur.

68
00:03:19,840 --> 00:03:22,270
Og vi vil se igen, hvordan
vi gør det på bare et sekund.

69
00:03:22,270 --> 00:03:25,110
>> Ved enden af ​​stien,
vi vil se navnet

70
00:03:25,110 --> 00:03:30,250
af universitetets, der svarer
til denne nøgle, de fire cifre.

71
00:03:30,250 --> 00:03:34,390
Den grundlæggende idé bag en trie
er, at vi har en central rute.

72
00:03:34,390 --> 00:03:35,640
Så tænker over det som et træ.

73
00:03:35,640 --> 00:03:39,211
Og det er ens i stavemåde
og koncept til et træ.

74
00:03:39,211 --> 00:03:41,460
Generelt, når vi tænker på
træer i den virkelige verden,

75
00:03:41,460 --> 00:03:44,090
de har en rod, der er i
jorden og de vokser opad

76
00:03:44,090 --> 00:03:46,830
og de har afdelinger
og de har blade.

77
00:03:46,830 --> 00:03:49,450
Og dybest set ideen om
en trie er nøjagtig den samme,

78
00:03:49,450 --> 00:03:51,755
bortset fra at roden er forankret
et eller andet sted på himlen.

79
00:03:51,755 --> 00:03:53,130
Og bladene er i bunden.

80
00:03:53,130 --> 00:03:55,750
>> Så det er lidt ligesom at tage et træ
og bare flippe det på hovedet.

81
00:03:55,750 --> 00:03:56,880
Men der er stadig grene.

82
00:03:56,880 --> 00:03:59,463
Og de ville være vore veje,
dem vil være vores forbindelser

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

84
00:04:02,220 --> 00:04:04,200
I dette tilfælde, der
stier, disse filialer

85
00:04:04,200 --> 00:04:08,490
er mærket med tal, der fortæller os
hvilken vej at gå fra hvor vi er.

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

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

88
00:04:12,900 --> 00:04:14,060
Nå, hvad betyder det?

89
00:04:14,060 --> 00:04:16,519
Tja, det betyder, at
ved hvert forbindelsespunkt

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

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

92
00:04:23,020 --> 00:04:27,690
Så der er 10 pejlemærker
fra hvert sted.

93
00:04:27,690 --> 00:04:30,610
>> Og det er her, forsøger kan få en
lille smule skræmmende for nogen

94
00:04:30,610 --> 00:04:34,460
der er ikke har en masse
erfaring i datalogi før.

95
00:04:34,460 --> 00:04:35,960
Men forsøger er virkelig temmelig awesome.

96
00:04:35,960 --> 00:04:37,793
Og hvis du har den
chance for at arbejde med dem

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

98
00:04:40,420 --> 00:04:44,234
de er virkelig ganske interessant
datastrukturer at arbejde med.

99
00:04:44,234 --> 00:04:46,900
Hvis vi ønsker at indsætte et element
ind i trie, alt, hvad vi behøver at gøre

100
00:04:46,900 --> 00:04:51,360
er bygget den korrekte sti
fra roden til bladet.

101
00:04:51,360 --> 00:04:55,390
Her er, hvad hvert skridt langs
den måde kunne se ud.

102
00:04:55,390 --> 00:04:59,660
Vi kommer til at definere en ny data
struktur for et nyt knudepunkt kaldes en trie.

103
00:04:59,660 --> 00:05:02,560
>> Og inde i, at data
struktur er der to stykker.

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

105
00:05:05,460 --> 00:05:09,410
Og vi kommer til at gemme
et array af pointere

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

107
00:05:12,190 --> 00:05:14,780
Så igen, det er den slags
af begrebet overalt

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

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

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

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

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

113
00:05:28,220 --> 00:05:35,740
Så hver node skal indeholde 10 pejlemærker
til andre knudepunkter, til 10 andre knudepunkter.

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

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

116
00:05:41,060 --> 00:05:44,860
Lad os indsætte et par
af elementer i vores trie.

117
00:05:44,860 --> 00:05:46,740
Så på toppen,
dette er vores rod node.

118
00:05:46,740 --> 00:05:49,740
Dette er sandsynligvis vil være noget
du kommer til globalt erklære.

119
00:05:49,740 --> 00:05:53,450
Og du kommer til globalt at opretholde
en pointer til denne node altid.

120
00:05:53,450 --> 00:05:55,360
>> Du kommer til at sige,
rod lig, og du er

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

122
00:05:57,580 --> 00:05:59,850
Og du aldrig kommer
at røre root igen.

123
00:05:59,850 --> 00:06:02,300
Hver gang, du ønsker at
begynde at navigere igennem,

124
00:06:02,300 --> 00:06:05,802
du indstille en anden pointer
lig med rod, såsom trav,

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

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

127
00:06:11,090 --> 00:06:13,320
>> Du sætter en anden pointer
kaldt trav til traversal.

128
00:06:13,320 --> 00:06:15,890
Og du bruger trav til at navigere
gennem datastrukturen.

129
00:06:15,890 --> 00:06:17,500
Så lad os se, hvordan det kan se ud.

130
00:06:17,500 --> 00:06:19,880
Så lige nu, hvad
gør en node ud?

131
00:06:19,880 --> 00:06:22,920
Nå, lige som vores data
struktur erklæring angivet,

132
00:06:22,920 --> 00:06:26,906
vi har en streng, der
i dette tilfælde er tom.

133
00:06:26,906 --> 00:06:27,780
Der er ikke noget her.

134
00:06:27,780 --> 00:06:29,550
>> Og en vifte af 10 pointere.

135
00:06:29,550 --> 00:06:31,790
Og lige nu kun vi,
har 1 node i denne trie.

136
00:06:31,790 --> 00:06:33,110
Der er ikke noget andet i det.

137
00:06:33,110 --> 00:06:36,020
Så alle 10 af dem
pointere point til null.

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

139
00:06:38,090 --> 00:06:39,500
>> Lad os indsætte strengen Harvard.

140
00:06:39,500 --> 00:06:41,999
Lad os indsætte Universitet
Harvard ind i denne trie, som

141
00:06:41,999 --> 00:06:43,940
blev grundlagt i år 1636.

142
00:06:43,940 --> 00:06:48,220
Vi ønsker at bruge nøglen,
1636, for at fortælle os, hvor vi er

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

144
00:06:50,140 --> 00:06:51,470
Nu, hvordan kan vi gøre det?

145
00:06:51,470 --> 00:06:52,886
>> Det kunne se sådan ud.

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

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

148
00:06:56,920 --> 00:06:59,900
Roden er ligesom enhver
andet knudepunkt af trie.

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

150
00:07:02,850 --> 00:07:07,215
>> Hvor vil vi sikkert gerne
at gå, hvis nøglen er 1636?

151
00:07:07,215 --> 00:07:08,340
Der er virkelig to muligheder.

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

153
00:07:08,450 --> 00:07:10,825
Vi kan bygge nøglen fra
højre til venstre og starte med 6.

154
00:07:10,825 --> 00:07:14,000
Eller vi kunne bygge nøglen fra
venstre til højre og begynder med 1.

155
00:07:14,000 --> 00:07:16,140
>> Det er sandsynligvis mere
intuitiv som menneske

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

157
00:07:18,110 --> 00:07:21,140
Og så hvis jeg ønsker at indsætte
Harvard ind i denne trie,

158
00:07:21,140 --> 00:07:23,560
Jeg sandsynligvis ønsker at starte
ved at starte ved roden,

159
00:07:23,560 --> 00:07:25,720
ser på mine 10 indstillinger
foran mig, og siger

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

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

162
00:07:29,700 --> 00:07:31,810
>> Nu 1 sti er i øjeblikket null.

163
00:07:31,810 --> 00:07:35,920
Så hvis jeg ønsker at fortsætte den vej
at indsætte dette element i trie,

164
00:07:35,920 --> 00:07:42,040
Jeg er nødt til malloc en ny node, have 1
pege der, og så er jeg god til at gå.

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

166
00:07:46,460 --> 00:07:50,270
ved roden af ​​træet eller
Trie og der er 10 filialer.

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

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

169
00:07:53,060 --> 00:07:54,850
Fordi der ikke er noget andet der er.

170
00:07:54,850 --> 00:07:56,522
Ingen sikker passage.

171
00:07:56,522 --> 00:07:58,980
Det betyder, at der ikke er noget
ned nogen af ​​disse filialer.

172
00:07:58,980 --> 00:08:02,532
Hvis jeg ønsker at begynde at bygge
noget, jeg ønsker at fjerne porten.

173
00:08:02,532 --> 00:08:04,490
Jeg vil fjerne porten
foran nummer 1.

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

175
00:08:05,698 --> 00:08:08,060
Og jeg ønsker at opbygge
et andet sted for mig at gå.

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

177
00:08:09,470 --> 00:08:11,430
Så 1 ikke længere peger til null.

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

179
00:08:13,830 --> 00:08:15,789
Jeg byggede en anden node.

180
00:08:15,789 --> 00:08:18,330
Og når jeg kommer til det knudepunkt, jeg
har en anden beslutning om at gøre.

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

182
00:08:20,890 --> 00:08:22,700
>> Tja, jeg har allerede gået ned 1.

183
00:08:22,700 --> 00:08:24,470
Så nu har jeg nok ønsker at gå ned i 6.

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

185
00:08:24,970 --> 00:08:27,100
Igen, jeg har 10 steder jeg kan vælge.

186
00:08:27,100 --> 00:08:30,060
Så lad os nu gå ned nummer 6.

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

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

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

190
00:08:34,580 --> 00:08:37,630
Og jeg har nået en anden krydset punkt.

191
00:08:37,630 --> 00:08:40,289
>> Igen, jeg har 10 valgmuligheder
til, 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å nu har jeg nok ønsker at gå til 3.

194
00:08:44,215 --> 00:08:45,381
3, der er ingen steder jeg kan gå.

195
00:08:45,381 --> 00:08:48,980
Så jeg er nødt til at bane vejen
og bygge mig en ny plads.

196
00:08:48,980 --> 00:08:50,870
Og derefter fra 3, hvor gør jeg ønsker at gå?

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

198
00:08:52,450 --> 00:08:54,770
>> Og igen, jeg var nødt til at
bane vejen for at gøre det.

199
00:08:54,770 --> 00:08:59,179
Så nu har jeg brugt min nøgle til at indsætte skabe
knudepunkter og begynde at bygge denne trie.

200
00:08:59,179 --> 00:09:00,220
Jeg er begyndt ved roden.

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

202
00:09:03,666 --> 00:09:05,540
Og nu er jeg på bunden
der på denne node.

203
00:09:05,540 --> 00:09:06,610
Og du kan være i stand til at
se det på din skærm.

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

205
00:09:07,735 --> 00:09:10,020
Det er, hvor jeg i øjeblikket er.

206
00:09:10,020 --> 00:09:11,300
Min nøgle er færdig.

207
00:09:11,300 --> 00:09:13,030
Jeg har opbrugt hver position i min nøgle.

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

209
00:09:15,040 --> 00:09:17,720
Så på dette punkt, alt hvad jeg
virkelig skal gøre er at sige, OK.

210
00:09:17,720 --> 00:09:18,990
Det er lidt ligesom at kigge
ned på jorden,

211
00:09:18,990 --> 00:09:21,115
hvis du forestille
dig selv som denne slags vej

212
00:09:21,115 --> 00:09:22,350
med forskellige forbindelser.

213
00:09:22,350 --> 00:09:25,800
Slags ser ned og sortering af
sprøjtemaling Harvard på jorden.

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

215
00:09:26,800 --> 00:09:28,300
Ved det er, hvad der er på denne placering.

216
00:09:28,300 --> 00:09:31,870
Hvis vi starter ved roden, og vi går ned
1 og derefter 6 og derefter 3 og derefter 6,

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

218
00:09:32,780 --> 00:09:35,640
Tja, hvis vi ser ned
og vi ser Harvard, så

219
00:09:35,640 --> 00:09:38,960
vi ved, at Harvard var
grundlagt i 1636 baseret på den måde

220
00:09:38,960 --> 00:09:41,400
vi gennemføre denne datastruktur.

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

222
00:09:43,177 --> 00:09:44,760
Vi kommer til at gøre to flere indrykninger.

223
00:09:44,760 --> 00:09:50,060
Og forhåbentlig vil bidrage til at
se dette gjort to gange mere.

224
00:09:50,060 --> 00:09:52,210
>> Lad os nu indsætte et andet universitet.

225
00:09:52,210 --> 00:09:54,630
Lad os indsætte Yale ind i denne trie.

226
00:09:54,630 --> 00:09:57,037
Yale blev grundlagt i 1701.

227
00:09:57,037 --> 00:09:58,870
Så vi vil starte på
rod, som vi altid gør.

228
00:09:58,870 --> 00:09:59,890
Og vi sætter en traversal pointer.

229
00:09:59,890 --> 00:10:01,624
Vi kommer til at bruge det til at bevæge sig igennem.

230
00:10:01,624 --> 00:10:03,790
Den første ting, vi ønsker at
gøre er at gå ned ad en vej.

231
00:10:03,790 --> 00:10:05,830
Det er det første ciffer i vores nøgle.

232
00:10:05,830 --> 00:10:08,420
Heldigvis selvom, vi ikke
nødt til at gøre noget arbejde denne gang.

233
00:10:08,420 --> 00:10:09,919
Den 1 stien er allerede blevet ryddet.

234
00:10:09,919 --> 00:10:13,520
Jeg blokerede den tidligere, når jeg
blev indsætte Harvard på 1.636.

235
00:10:13,520 --> 00:10:18,090
Så jeg kan trygt bevæge
ned 1 og bare gå der.

236
00:10:18,090 --> 00:10:20,150
Hvis der kan bevæge sig ned i 1.

237
00:10:20,150 --> 00:10:22,930
>> Men nu jeg ønsker at gå til 7.

238
00:10:22,930 --> 00:10:24,280
Jeg ryddet vejen ved 6.

239
00:10:24,280 --> 00:10:27,050
Jeg ved, jeg kan trygt
Fortsæt ned 6 sti.

240
00:10:27,050 --> 00:10:29,220
Men jeg har brug for at fortsætte den 7. vej.

241
00:10:29,220 --> 00:10:30,580
Så hvad skal jeg gøre?

242
00:10:30,580 --> 00:10:35,070
Nå, ligesom før, jeg har bare brug for
at rydde porten, komme ud af den måde,

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

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

245
00:10:40,250 --> 00:10:42,930
>> Så nu har jeg flyttet 1 og derefter 7.

246
00:10:42,930 --> 00:10:45,550
Og nu mærke til, er jeg sortere
af denne nye subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Alt andet fra 16
på, jeg er ligeglad om.

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

250
00:10:50,720 --> 00:10:51,750
Jeg laver 17 ting.

251
00:10:51,750 --> 00:10:58,380
>> Så nu fra 17 på, jeg er nødt til
slags blis nye stier her.

252
00:10:58,380 --> 00:11:00,462
Det næste ciffer min nøgle er 0.

253
00:11:00,462 --> 00:11:01,670
Jeg kan naturligvis ikke komme nogen steder.

254
00:11:01,670 --> 00:11:02,628
Jeg har lige bygget denne node.

255
00:11:02,628 --> 00:11:04,550
Så jeg ved, der er ingen
stier frem herfra.

256
00:11:04,550 --> 00:11:06,370
Så jeg er nødt til at lave en selv.

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

258
00:11:09,360 --> 00:11:12,770
Og så en gang mere, jeg malloc en
nyt knudepunkt og har et tidspunkt.

259
00:11:12,770 --> 00:11:15,870
Igen, jeg har opbrugt min nøgle, 1701.

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

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

262
00:11:19,680 --> 00:11:24,660
>> Og så nu, hvis jeg nogensinde har brug for at se, om Yale
er i denne Trie, jeg starter ved roden,

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
malet på jorden, så

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

266
00:11:32,200 --> 00:11:32,950
Lad os gøre en mere.

267
00:11:32,950 --> 00:11:36,430
Lad os indsætte Dartmouth ind i denne
Trie, som blev grundlagt i 1769.

268
00:11:36,430 --> 00:11:37,750
>> Start ved roden igen.

269
00:11:37,750 --> 00:11:39,445
Min første ciffer i min nøgle er 1.

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

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

272
00:11:42,400 --> 00:11:44,040
Det næste ciffer i min nøgle er 7.

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

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

275
00:11:47,540 --> 00:11:49,000
>> Mit næste er 6.

276
00:11:49,000 --> 00:11:52,860
Herfra hvor jeg i øjeblikket er
i gul der i denne midterste knudepunkt,

277
00:11:52,860 --> 00:11:56,060
6 er i øjeblikket låst ud.

278
00:11:56,060 --> 00:11:58,830
Hvis jeg ønsker at gå den vej,
Jeg er nødt til at bygge det selv.

279
00:11:58,830 --> 00:12:02,250
Så jeg vil malloc en ny knude
og har 6 point der.

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

281
00:12:04,250 --> 00:12:10,750
>> Så jeg malloc en ny knude, så fra
at node-- kanalnummer 9-- og så nu

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

283
00:12:13,584 --> 00:12:15,500
Der er ikke noget i øjeblikket
spray malet 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 indsat
Dartmouth i trie.

286
00:12:20,710 --> 00:12:23,450
>> Så det er at indsætte
ting ind i trie.

287
00:12:23,450 --> 00:12:25,384
Nu ønsker vi at søge efter ting.

288
00:12:25,384 --> 00:12:27,050
Hvordan kan vi søge efter ting i trie?

289
00:12:27,050 --> 00:12:29,170
Tja, det er temmelig meget den samme idé.

290
00:12:29,170 --> 00:12:33,620
Nu skal vi bare bruge cifrene i nøglen
at se, om vi kan navigere fra roden

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

292
00:12:37,170 --> 00:12:41,620
>> Hvis vi ramt en blindgyde på noget tidspunkt, så
vi ved, at dette element ikke kan findes

293
00:12:41,620 --> 00:12:44,500
eller andet, vej ville
Der er allerede blevet ryddet.

294
00:12:44,500 --> 00:12:45,930
Hvis vi gør det hele vejen til
enden, alt, hvad vi behøver at gøre

295
00:12:45,930 --> 00:12:48,471
er at kigge ned og se, om det er
elementet, vi leder efter.

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

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

298
00:12:52,610 --> 00:12:54,940
>> Så lad os søge efter
Harvard i denne trie.

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

300
00:12:56,020 --> 00:12:58,228
Og igen, vi kommer til at
skabe en traversal pointer

301
00:12:58,228 --> 00:12:59,390
at gøre vores bevægelser for os.

302
00:12:59,390 --> 00:13:02,080
Fra roden ved vi, at
første sted vi nødt til at gå er 1,

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

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

305
00:13:03,982 --> 00:13:04,690
Hvis der findes sikkert.

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

307
00:13:06,660 --> 00:13:08,440
>> Nu er den næste sted, vi skal gå, er 6.

308
00:13:08,440 --> 00:13:10,557
Har 6 stien eksisterer herfra?

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

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

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

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

313
00:13:16,130 --> 00:13:18,450
Nå, da det viser sig,
ja, der findes også.

314
00:13:18,450 --> 00:13:20,790
Og kan vi få på 6 stien 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 besvaret
spørgsmålet endnu.

317
00:13:24,002 --> 00:13:25,710
Der er stadig en mere
trin, som nu er

318
00:13:25,710 --> 00:13:28,520
vi nødt til at kigge ned og
se, om det er actually--

319
00:13:28,520 --> 00:13:32,660
hvis vi leder efter Harvard, er, at
hvad vi finder, når vi udtømme nøglen?

320
00:13:32,660 --> 00:13:35,430
I det eksempel, vi bruger her,
årene er altid fire cifre.

321
00:13:35,430 --> 00:13:40,280
Men du kan være ved hjælp af eksempel, hvor
du gemmer en ordbog over ord.

322
00:13:40,280 --> 00:13:44,060
>> Og så i stedet for at have 10 pejlemærker
for min placering, kan du have 26.

323
00:13:44,060 --> 00:13:46,040
En for hvert bogstav i alfabetet.

324
00:13:46,040 --> 00:13:50,350
Og der er nogle ord som flagermus,
som er en delmængde af batch, f.eks.

325
00:13:50,350 --> 00:13:53,511
Og så selvom du kommer til
enden af ​​nøglen, og du kigger ned,

326
00:13:53,511 --> 00:13:55,260
du måske ikke se, hvad
du leder efter.

327
00:13:55,260 --> 00:13:58,500
>> Så du altid har til at krydse
hele stien og derefter

328
00:13:58,500 --> 00:14:01,540
hvis du var held i stand
til at krydse hele stien,

329
00:14:01,540 --> 00:14:03,440
kigge ned og gøre en sidste bekræftelse.

330
00:14:03,440 --> 00:14:05,120
Er det, hvad jeg leder efter?

331
00:14:05,120 --> 00:14:07,740
Nå, jeg ser ned efter start
øverst og går 1636.

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, det lykkedes jeg.

335
00:14:11,689 --> 00:14:13,980
Hvad hvis det, jeg leder efter
er ikke i Trie, selv om.

336
00:14:13,980 --> 00:14:17,200
Hvad hvis jeg leder efter Princeton,
som blev grundlagt i 1746.

337
00:14:17,200 --> 00:14:20,875
Og så 1746 bliver min nøgle
til at navigere gennem trie.

338
00:14:20,875 --> 00:14:22,040
Nå, jeg starter ved roden.

339
00:14:22,040 --> 00:14:24,760
Og det første sted jeg vil have
til går ned i 1 stien.

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

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

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

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

344
00:14:29,230 --> 00:14:30,750
Der findes også.

345
00:14:30,750 --> 00:14:32,460
Men kan jeg gå ned i 4 stien herfra?

346
00:14:32,460 --> 00:14:35,550
Det er som at stille spørgsmålet, kan
Jeg fortsætter ned at lille firkant

347
00:14:35,550 --> 00:14:37,114
at jeg har fremhævet med gult?

348
00:14:37,114 --> 00:14:38,030
Der er ikke noget der.

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

350
00:14:38,610 --> 00:14:41,310
>> Der er ingen vej frem nede 4 sti.

351
00:14:41,310 --> 00:14:46,480
Hvis Princeton var i denne trie, at 4
ville have været ryddet for os allerede.

352
00:14:46,480 --> 00:14:49,130
Og så på dette punkt
Vi har nået en blindgyde.

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

354
00:14:50,250 --> 00:14:53,440
Og så vi kan sige, endeligt, nej.

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

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

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

358
00:14:59,360 --> 00:15:01,000
Der er en masse foregår her.

359
00:15:01,000 --> 00:15:02,500
Der er pegepinde over det hele.

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

361
00:15:04,249 --> 00:15:07,010
der er en masse noder,
er slags flyver rundt.

362
00:15:07,010 --> 00:15:13,480
Men mærke hver gang vi ønskede at
kontrollere, om der var noget i trie,

363
00:15:13,480 --> 00:15:15,000
Vi havde kun at lave 4 træk.

364
00:15:15,000 --> 00:15:17,208
>> Hver gang vi ønskede at
indsætte noget i trie,

365
00:15:17,208 --> 00:15:20,440
vi er nødt til at gøre 4 bevæger sig, muligvis
mallocing nogle ting undervejs.

366
00:15:20,440 --> 00:15:23,482
Men som vi så, da vi indsat
Dartmouth i trie,

367
00:15:23,482 --> 00:15:25,940
undertiden nogle af stien
måske allerede blive ryddet for os.

368
00:15:25,940 --> 00:15:30,520
Og så vores Trie bliver større og
større, har vi at gøre mindre arbejde, hver gang

369
00:15:30,520 --> 00:15:32,270
at indsætte nye ting
fordi vi har allerede

370
00:15:32,270 --> 00:15:35,746
bygget en masse af mellemproduktet
grene undervejs.

371
00:15:35,746 --> 00:15:38,370
Hvis vi kun nogensinde nødt til at se på
4 ting, 4 er bare en konstant.

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

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

374
00:15:44,501 --> 00:15:47,500
Tradeoff naturligvis er, at
denne trie, som du kan sandsynligvis fortælle,

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

376
00:15:49,030 --> 00:15:51,040
Hver af disse knuder
optager en masse plads.

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

378
00:15:52,090 --> 00:15:55,260
Hvis vi ønsker virkelig hurtig
insertion, virkelig hurtig sletning,

379
00:15:55,260 --> 00:15:59,630
og virkelig hurtig opslag, vi er nødt til at
har en masse data flyver rundt.

380
00:15:59,630 --> 00:16:03,590
Vi er nødt til at afsætte en masse plads
og hukommelse til at datastruktur

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

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

383
00:16:05,415 --> 00:16:07,310
Men det ser ud som vi
kunne have fundet det.

384
00:16:07,310 --> 00:16:09,560
Vi kunne have fundet, at
hellige gral af datastrukturer

385
00:16:09,560 --> 00:16:12,264
med hurtig indsættelse,
deletion og opslag.

386
00:16:12,264 --> 00:16:14,430
Og måske dette vil være en
passende datastruktur

387
00:16:14,430 --> 00:16:18,890
til brug for de oplysninger
vi forsøger at gemme.

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

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