1
00:00:00,000 --> 00:00:02,994
>> [Predvaja glasba]

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

3
00:00:05,426 --> 00:00:08,550
Doug LLOYD: Torej smo bili inching bližje
in bližje, da je sveti gral podatkov

4
00:00:08,550 --> 00:00:13,050
strukture, tista, ki se lahko vstavi
v, izbrišete iz in poglej gor

5
00:00:13,050 --> 00:00:15,440
v stalnem času.

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

7
00:00:16,270 --> 00:00:17,280
To je nekako avt.

8
00:00:17,280 --> 00:00:19,720
Želimo biti sposoben narediti
stvari zelo, zelo hitro.

9
00:00:19,720 --> 00:00:22,580
>> Imeli smo ga našli tukaj, ko
govorimo o poskusih?

10
00:00:22,580 --> 00:00:23,670
No, poglej.

11
00:00:23,670 --> 00:00:25,628
Tako smo videli več
različne podatkovne strukture

12
00:00:25,628 --> 00:00:28,680
ki skrbi za preslikavo
ti pari ključ vrednostjo,

13
00:00:28,680 --> 00:00:32,080
kartiranje kakšen kos podatkov
na nek drug podatek

14
00:00:32,080 --> 00:00:36,020
tako da bomo vedeli, kje najti
Podatki v strukturi.

15
00:00:36,020 --> 00:00:40,060
>> Torej za niz, na primer,
Ključ je indeks element ali niz

16
00:00:40,060 --> 00:00:42,600
lokacija 0 ali matrika 1 in tako naprej.

17
00:00:42,600 --> 00:00:46,140
In je vrednost podatkov
da obstaja na tem mestu.

18
00:00:46,140 --> 00:00:48,550
Torej, kaj shranjeni v matriki 0?

19
00:00:48,550 --> 00:00:54,290
Kaj se shrani v polju 1 v primerjavi s samo
0 in 1, ki bi bili ključi.

20
00:00:54,290 --> 00:00:56,360
>> Z hash tabele je
sortiranje iste zamisli.

21
00:00:56,360 --> 00:01:00,690
Z hash tabele, imamo to hash
Funkcija, ki ustvarja hash kode.

22
00:01:00,690 --> 00:01:03,670
Torej je ključ hash code podatkov.

23
00:01:03,670 --> 00:01:06,530
In vrednost, zlasti
smo se pogovarjali o verižni

24
00:01:06,530 --> 00:01:10,590
v videu na hash tabele,
je ta povezana seznam podatkov

25
00:01:10,590 --> 00:01:12,550
da hashes na to hashcode.

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

27
00:01:14,050 --> 00:01:16,050
Kaj pa drugega pristopa
Ta metoda, čeprav?

28
00:01:16,050 --> 00:01:21,000
Kaj metodi kadar
Ključ je zagotovljeno, da je edinstven,

29
00:01:21,000 --> 00:01:25,410
za razliko od hash tabele, kjer smo lahko
na koncu z dvema kosoma podatkov

30
00:01:25,410 --> 00:01:27,200
ki ima isto hashcode.

31
00:01:27,200 --> 00:01:30,020
In potem smo se morali spopasti s
da jih bodisi sondiranje ali več

32
00:01:30,020 --> 00:01:33,340
možnosti verižnem popraviti to težavo.

33
00:01:33,340 --> 00:01:37,520
>> Zdaj bomo lahko zagotovili
da bo naša ključna edinstvena.

34
00:01:37,520 --> 00:01:39,690
In kaj, če je bil naš vrednost
samo nekaj tako enostavno,

35
00:01:39,690 --> 00:01:44,080
kot true in false, ki nam pove, ali
ali ne, da podatek

36
00:01:44,080 --> 00:01:45,610
obstaja v strukturi?

37
00:01:45,610 --> 00:01:48,180
Logično bi bilo tako enostavno, kot bit.

38
00:01:48,180 --> 00:01:52,660
Realno je to verjetno
bajtu bolj verjetno kot bit.

39
00:01:52,660 --> 00:01:55,410
Ampak to je veliko manjša od
shranjevanje morda niz 50 znakov,

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

41
00:01:57,360 --> 00:02:02,210
>> Torej poskusih podobna hash tabele,
ki združujejo nizi in povezani seznam,

42
00:02:02,210 --> 00:02:05,790
poskuša združiti nizi,
strukture in kazalci

43
00:02:05,790 --> 00:02:08,509
skupaj za shranjevanje podatkov v
zanimiv način, ki je

44
00:02:08,509 --> 00:02:11,550
precej drugačna od
kaj smo videli doslej.

45
00:02:11,550 --> 00:02:16,750
Zdaj smo uporabili podatke kot načrt
krmariti to podatkovno strukturo.

46
00:02:16,750 --> 00:02:18,710
In če bomo lahko sledili
načrt, če bomo lahko

47
00:02:18,710 --> 00:02:22,390
nadaljnje podatke iz
začetka do konca, bomo

48
00:02:22,390 --> 00:02:24,945
vedeti, ali te podatke
obstajajo v trie.

49
00:02:24,945 --> 00:02:28,310
>> In če ne moremo slediti zemljevid
od kar pomeni, da na koncu sploh,

50
00:02:28,310 --> 00:02:30,600
podatkov ne more obstajati.

51
00:02:30,600 --> 00:02:32,890
Spet ključi tukaj
zagotovljeno, da je edinstven.

52
00:02:32,890 --> 00:02:36,020
In tako za razliko od hash tabele, bomo nikoli
se morajo ukvarjati z trčenj tukaj.

53
00:02:36,020 --> 00:02:39,090
In ni dveh kosov podatkov
imajo povsem enak načrt

54
00:02:39,090 --> 00:02:40,530
razen če so podatki enaki.

55
00:02:40,530 --> 00:02:44,580
>> Če bomo vstavite John, nato
iščemo za Janeza.

56
00:02:44,580 --> 00:02:47,430
To je dva identična kosov
podatki, prav, bomo iskali skozi.

57
00:02:47,430 --> 00:02:49,880
Toda drugače, vsak
dva kosa podatkov so

58
00:02:49,880 --> 00:02:52,750
zagotovljeno, da imajo edinstvene načrte
skozi to strukturo podatkov.

59
00:02:52,750 --> 00:02:56,210
In bomo si oglejte
vizualni to v samo trenutek.

60
00:02:56,210 --> 00:02:58,810
>> To bomo storili s poskušanjem
ustvariti novo podatkovno strukturo,

61
00:02:58,810 --> 00:03:00,564
kartiranje naslednje ključne parov vrednosti.

62
00:03:00,564 --> 00:03:03,480
V tem primeru ne bomo uporabljati
nekaj tako enostavno, kot logičnim.

63
00:03:03,480 --> 00:03:06,200
Bomo dejansko shranite niz.

64
00:03:06,200 --> 00:03:08,690
In da je niz se bo
je ime univerze.

65
00:03:08,690 --> 00:03:12,140
>> In ključ se bo leto
ko je bila ta univerza ustanovljena.

66
00:03:12,140 --> 00:03:15,380
Vsa leta za univerze
se bodo štiri številke.

67
00:03:15,380 --> 00:03:19,840
In tako bomo uporabili te štiri cifre na
krmariti skozi to strukturo podatkov.

68
00:03:19,840 --> 00:03:22,270
In bomo videli, še enkrat, kako
storimo, da v samo sekundo.

69
00:03:22,270 --> 00:03:25,110
>> Na koncu poti,
bomo videli ime

70
00:03:25,110 --> 00:03:30,250
univerze, ki ustreza
v tem ključu, te štiri številke.

71
00:03:30,250 --> 00:03:34,390
Osnovna ideja je Trie
je imamo osrednjo pot.

72
00:03:34,390 --> 00:03:35,640
Torej, razmišljam o tem kot drevo.

73
00:03:35,640 --> 00:03:39,211
In to je podobno kot pri črkovanju
in v koncept na drevesu.

74
00:03:39,211 --> 00:03:41,460
Na splošno, ko razmišljamo o
drevesa v resničnem svetu,

75
00:03:41,460 --> 00:03:44,090
imajo korenine, ki je v
tleh in rastejo navzgor

76
00:03:44,090 --> 00:03:46,830
in imajo podružnice
in imajo listi.

77
00:03:46,830 --> 00:03:49,450
In v bistvu ideja
trie je popolnoma enak,

78
00:03:49,450 --> 00:03:51,755
razen da je koren zasidrana
nekje na nebu.

79
00:03:51,755 --> 00:03:53,130
In listi so na dnu.

80
00:03:53,130 --> 00:03:55,750
>> Torej, to je nekako kot ob drevo
in samo flipping glavo.

81
00:03:55,750 --> 00:03:56,880
Vendar še vedno obstajajo panoge.

82
00:03:56,880 --> 00:03:59,463
In tisti, bi bilo naše poti,
tistih, ki bodo naši povezave

83
00:03:59,463 --> 00:04:02,220
od korenin do listov.

84
00:04:02,220 --> 00:04:04,200
V tem primeru tistih
poti, te podružnice

85
00:04:04,200 --> 00:04:08,490
so označeni s številkami, ki nam povedo,
v katero smer iti od tam, kjer smo.

86
00:04:08,490 --> 00:04:11,800
>> Če vidimo 0, gremo po tej podružnici,
če bomo videli 1, gremo po tej podružnici,

87
00:04:11,800 --> 00:04:12,900
in tako in tako naprej.

88
00:04:12,900 --> 00:04:14,060
No, kaj to pomeni?

89
00:04:14,060 --> 00:04:16,519
No, to pomeni, da
na vsaki stični točki

90
00:04:16,519 --> 00:04:19,260
in vsako vozlišče v
srednji in vsaka veja,

91
00:04:19,260 --> 00:04:23,020
obstajajo 10 možno
kraji, da lahko gremo.

92
00:04:23,020 --> 00:04:27,690
Torej obstaja 10 kazalci
iz vsake lokacije.

93
00:04:27,690 --> 00:04:30,610
>> In to je, če lahko poskuša dobiti
malo zastrašujoče za nekoga

94
00:04:30,610 --> 00:04:34,460
kdo nima veliko
izkušnje na področju računalništva poprej.

95
00:04:34,460 --> 00:04:35,960
Ampak poskuša so res precej super.

96
00:04:35,960 --> 00:04:37,793
In če imate
priložnost za delo z njimi

97
00:04:37,793 --> 00:04:40,420
in ste pripravljeni kopati, v
in eksperimentira z njimi,

98
00:04:40,420 --> 00:04:44,234
oni so res precej zanimivo
podatkovne strukture delati.

99
00:04:44,234 --> 00:04:46,900
Če želimo vstaviti element
v Trie, vse, kar morate storiti,

100
00:04:46,900 --> 00:04:51,360
je zgraditi pravo pot
od korenin do listov.

101
00:04:51,360 --> 00:04:55,390
Tukaj je tisto, kar na vsakem koraku, skupaj
kako bi izgledal.

102
00:04:55,390 --> 00:04:59,660
Bomo določili novo podatkov
strukturo za novo vozlišče, imenovano trie.

103
00:04:59,660 --> 00:05:02,560
>> In znotraj teh podatkov
Struktura obstajata dva kosa.

104
00:05:02,560 --> 00:05:05,460
Mi bomo za shranjevanje
ime univerze.

105
00:05:05,460 --> 00:05:09,410
In bomo za shranjevanje
niz kazalcev

106
00:05:09,410 --> 00:05:12,190
z drugimi vozlišči istega tipa.

107
00:05:12,190 --> 00:05:14,780
Torej, še enkrat, to je, da sortiranje
od koncepta povsod

108
00:05:14,780 --> 00:05:18,567
smo, smo na 10 mogoče
krajev, lahko gremo.

109
00:05:18,567 --> 00:05:20,150
Če vidimo 0, gremo dol to vejo.

110
00:05:20,150 --> 00:05:22,690
Če bomo videli 1, ta podružnica,
in tako naprej in tako naprej in tako naprej.

111
00:05:22,690 --> 00:05:25,160
Če rečemo, 9, gremo dol to vejo.

112
00:05:25,160 --> 00:05:28,220
Torej na vsaki stični točki,
lahko gremo 10 možnih krajev.

113
00:05:28,220 --> 00:05:35,740
Torej vsako vozlišče mora vsebovati 10 kazalcev
do drugih vozlišč, do 10 drugih vozlišč.

114
00:05:35,740 --> 00:05:39,810
>> In podatke bomo shranjevanje je
samo ime univerze.

115
00:05:39,810 --> 00:05:41,060
Torej, kaj je zgraditi trie.

116
00:05:41,060 --> 00:05:44,860
Oglejmo vstavite par
postavk v naši trie.

117
00:05:44,860 --> 00:05:46,740
Torej, na samem vrhu,
to je naša koren vozlišče.

118
00:05:46,740 --> 00:05:49,740
To je verjetno, da bo nekaj
boš globalno prijave.

119
00:05:49,740 --> 00:05:53,450
In ti boš globalno ohraniti
kazalec na tem vozlišču vedno.

120
00:05:53,450 --> 00:05:55,360
>> Boste rekli,
koren enak, in ste

121
00:05:55,360 --> 00:05:57,580
dogaja, da si malloc Trie vozlišče.

122
00:05:57,580 --> 00:05:59,850
In ti ne bo nikoli
ponovno dotakniti korenin.

123
00:05:59,850 --> 00:06:02,300
Vsakič, ko želite
Navigacijo začnete s,

124
00:06:02,300 --> 00:06:05,802
nastavite drug kazalec
enako korena, kot trav,

125
00:06:05,802 --> 00:06:07,760
ki je primer I
uporabo v veliko mojih videoposnetkov

126
00:06:07,760 --> 00:06:11,090
tukaj na kupih in čakalnih vrst
in seznami povezav in tako naprej.

127
00:06:11,090 --> 00:06:13,320
>> Nastavite drug kazalec
pozval trav za prečkanje.

128
00:06:13,320 --> 00:06:15,890
In uporabljate trav za navigacijo
s podatkovno strukturo.

129
00:06:15,890 --> 00:06:17,500
Torej, da vidimo, kako se bo to videti.

130
00:06:17,500 --> 00:06:19,880
Torej sedaj, kaj
ne vozlišče izgledal?

131
00:06:19,880 --> 00:06:22,920
No, tako kot naših podatkih
Izjava struktura je navedeno,

132
00:06:22,920 --> 00:06:26,906
imamo niz, ki je
V tem primeru je prazna.

133
00:06:26,906 --> 00:06:27,780
Nič ni tukaj.

134
00:06:27,780 --> 00:06:29,550
>> In niz 10 kazalcev.

135
00:06:29,550 --> 00:06:31,790
In zdaj smo samo
ima pa 1 vozlišče v tem trie.

136
00:06:31,790 --> 00:06:33,110
Nič drugega v njej.

137
00:06:33,110 --> 00:06:36,020
Tako da vse 10 tistih
kazalci pokažite na ničlo.

138
00:06:36,020 --> 00:06:38,090
To je tisto, rdeča označuje.

139
00:06:38,090 --> 00:06:39,500
>> Oglejmo vstavite niz Harvard.

140
00:06:39,500 --> 00:06:41,999
Oglejmo vstavite univerza
Harvard v tem trie, ki

141
00:06:41,999 --> 00:06:43,940
je bila ustanovljena leta 1636.

142
00:06:43,940 --> 00:06:48,220
Želimo, da uporabite tipko,
1636, da nam poveste, kje smo

143
00:06:48,220 --> 00:06:50,140
dogaja, da shranite Harvard v trie.

144
00:06:50,140 --> 00:06:51,470
Zdaj, kako lahko to storimo?

145
00:06:51,470 --> 00:06:52,886
>> Morda bi izgledala nekako takole.

146
00:06:52,886 --> 00:06:54,160
Začnemo pri korenu.

147
00:06:54,160 --> 00:06:56,920
In imamo teh 10 mest lahko gremo.

148
00:06:56,920 --> 00:06:59,900
Korenina je tako kot vsaka
drugo vozlišče trie.

149
00:06:59,900 --> 00:07:02,850
Obstaja 10 krajev, lahko gremo od tukaj.

150
00:07:02,850 --> 00:07:07,215
>> Kam bomo verjetno želeli
iti, če je ključ 1636?

151
00:07:07,215 --> 00:07:08,340
Tam je res dve možnosti.

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

153
00:07:08,450 --> 00:07:10,825
Lahko gradimo ključ
desne proti levi in ​​začeti s 6.

154
00:07:10,825 --> 00:07:14,000
Ali lahko gradimo na ključ
od leve proti desni in začeti z 1.

155
00:07:14,000 --> 00:07:16,140
>> To je verjetno bolj
intuitiven kot človeško bitje

156
00:07:16,140 --> 00:07:18,110
da bomo razumeli boste
pojdi z leve proti desni.

157
00:07:18,110 --> 00:07:21,140
In tako, če želim, da vstavite
Harvard v tem Trie,

158
00:07:21,140 --> 00:07:23,560
Verjetno želim začeti
z začetkom pri korenu,

159
00:07:23,560 --> 00:07:25,720
videti na mojih 10 možnosti
pred mano in rekel

160
00:07:25,720 --> 00:07:28,700
Rad bi šel dol v 1 pot.

161
00:07:28,700 --> 00:07:29,700
V REDU.

162
00:07:29,700 --> 00:07:31,810
>> Zdaj, 1 Pot je sedaj null.

163
00:07:31,810 --> 00:07:35,920
Torej, če želim nadaljevati po tej poti
vstaviti ta element v Trie,

164
00:07:35,920 --> 00:07:42,040
Moram malloc novo vozlišče, imajo 1
točko tam, in potem sem na dobri poti.

165
00:07:42,040 --> 00:07:46,460
>> Tako sem v bistvu sem na
točka, kjer stojim

166
00:07:46,460 --> 00:07:50,270
na korenu drevesa ali
trie in tam so 10 podružnice.

167
00:07:50,270 --> 00:07:52,260
Ampak vsaka veja ima
vrata pred njim.

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

169
00:07:53,060 --> 00:07:54,850
Ker ni nič drugega tam.

170
00:07:54,850 --> 00:07:56,522
Ne varen prehod.

171
00:07:56,522 --> 00:07:58,980
To pomeni, da ni nič
katerokoli od teh podružnic.

172
00:07:58,980 --> 00:08:02,532
Če želim začeti gradnjo
nekaj, želim odstraniti vrata.

173
00:08:02,532 --> 00:08:04,490
Želim odstraniti vrata
pred številko 1.

174
00:08:04,490 --> 00:08:05,698
In želim, da hodi dol, da.

175
00:08:05,698 --> 00:08:08,060
In želim graditi
drugo mesto za mene, da gredo.

176
00:08:08,060 --> 00:08:09,470
>> In to je tisto, kar sem tukaj naredil.

177
00:08:09,470 --> 00:08:11,430
Torej 1 ne kaže na null.

178
00:08:11,430 --> 00:08:13,830
Sem rekel, da je varno iti tukaj zdaj.

179
00:08:13,830 --> 00:08:15,789
Sem zgradil še eno vozlišče.

180
00:08:15,789 --> 00:08:18,330
In ko pridem do tega vozlišča, I
še eno odločitev, da bo.

181
00:08:18,330 --> 00:08:20,890
Kje sem šla od tu?

182
00:08:20,890 --> 00:08:22,700
>> No, sem že šel dol po 1.

183
00:08:22,700 --> 00:08:24,470
Torej, zdaj bom verjetno želeli, da gredo navzdol 6.

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

185
00:08:24,970 --> 00:08:27,100
Spet imam 10 lokacij bom lahko izbirate.

186
00:08:27,100 --> 00:08:30,060
Torej, kaj je zdaj dol številko 6.

187
00:08:30,060 --> 00:08:32,280
Tako sem počistiti vrata
Pred številko 6.

188
00:08:32,280 --> 00:08:33,250
In jaz sem hodil tja dol.

189
00:08:33,250 --> 00:08:34,580
In jaz zgraditi še eno vozlišče.

190
00:08:34,580 --> 00:08:37,630
In sem dosegel drugo priključno točko.

191
00:08:37,630 --> 00:08:40,289
>> Spet imam 10 izbire
za kje lahko grem.

192
00:08:40,289 --> 00:08:42,799
Sem se preselil od 1 do 6.

193
00:08:42,799 --> 00:08:44,215
Torej, zdaj bom verjetno želeli, da gredo do 3.

194
00:08:44,215 --> 00:08:45,381
3, pa je nikjer ne morem iti.

195
00:08:45,381 --> 00:08:48,980
Tako da sem moral počistiti pot
in zgraditi sam nov prostor.

196
00:08:48,980 --> 00:08:50,870
In potem od 3, Kam želite iti?

197
00:08:50,870 --> 00:08:52,450
Rad bi šel dol 6.

198
00:08:52,450 --> 00:08:54,770
>> In, še enkrat, sem moral
jasen način, da to storite.

199
00:08:54,770 --> 00:08:59,179
Torej, zdaj sem uporabil moj ključ za vstavljanje ustvarjanje
vozlišča in začeti graditi to trie.

200
00:08:59,179 --> 00:09:00,220
Začel sem pri korenu.

201
00:09:00,220 --> 00:09:03,666
Sem padel na tla in 1636.

202
00:09:03,666 --> 00:09:05,540
In zdaj sem na dnu
tam na to vozlišče.

203
00:09:05,540 --> 00:09:06,610
In boste morda lahko
ga vidite na zaslonu.

204
00:09:06,610 --> 00:09:07,735
>> To je poudarjeno v rumeno.

205
00:09:07,735 --> 00:09:10,020
To je, kjer sem trenutno jaz.

206
00:09:10,020 --> 00:09:11,300
Moj ključ je storiti.

207
00:09:11,300 --> 00:09:13,030
Sem izčrpana vsak položaj v mojem ključu.

208
00:09:13,030 --> 00:09:15,040
Tako da ne more iti več naprej.

209
00:09:15,040 --> 00:09:17,720
Torej, v tem trenutku, vse, kar sem
res morate storiti je reči, OK.

210
00:09:17,720 --> 00:09:18,990
To je nekako kot je videti
v tla,

211
00:09:18,990 --> 00:09:21,115
če ste viziranje
sebe kot te vrste poti

212
00:09:21,115 --> 00:09:22,350
z različnimi priključki.

213
00:09:22,350 --> 00:09:25,800
Nekako je videti dol in nekako
spray slikarstvo Harvard na terenu.

214
00:09:25,800 --> 00:09:26,800
To je ime za to.

215
00:09:26,800 --> 00:09:28,300
Vedite, da je tisto, kar je na tej lokaciji.

216
00:09:28,300 --> 00:09:31,870
Če začnemo pri korenu in gremo dol
1 in nato 6 in nato 3, nato pa 6,

217
00:09:31,870 --> 00:09:32,780
kje smo?

218
00:09:32,780 --> 00:09:35,640
No, če pogledamo navzdol
in vidimo Harvard, nato

219
00:09:35,640 --> 00:09:38,960
vemo, da je Harvard
ustanovljeno leta 1636, ki temelji na poti

220
00:09:38,960 --> 00:09:41,400
smo izvajanje te podatkovne strukture.

221
00:09:41,400 --> 00:09:43,177
Tako da je bil upajmo enostavna.

222
00:09:43,177 --> 00:09:44,760
Bomo narediti še dva vstavljanja.

223
00:09:44,760 --> 00:09:50,060
In upajmo, da bo to pripomoglo k
glej to storjeno dvakrat več.

224
00:09:50,060 --> 00:09:52,210
>> Zdaj pa vstavite drugo univerzo.

225
00:09:52,210 --> 00:09:54,630
Oglejmo vstavite Yale v tem trie.

226
00:09:54,630 --> 00:09:57,037
Yale je bila ustanovljena leta 1701.

227
00:09:57,037 --> 00:09:58,870
Torej bomo začeti izvajati
koren, kot smo vedno.

228
00:09:58,870 --> 00:09:59,890
In smo si zastavili prečkanje kazalec.

229
00:09:59,890 --> 00:10:01,624
Bomo uporabili, da se premaknete skozi.

230
00:10:01,624 --> 00:10:03,790
Prva stvar, ki jo želimo
storiti, je šel dol v 1 pot.

231
00:10:03,790 --> 00:10:05,830
To je prva številka našega ključa.

232
00:10:05,830 --> 00:10:08,420
Na srečo, čeprav ne bomo
morali narediti katerokoli delo, ki ta čas.

233
00:10:08,420 --> 00:10:09,919
Se je 1. Pot je že izbil.

234
00:10:09,919 --> 00:10:13,520
Jaz žogo izbil prej, ko sem
je vstavljanje Harvard na 1636.

235
00:10:13,520 --> 00:10:18,090
Tako da sem lahko varno premikanje
dol 1. in pojdi tja.

236
00:10:18,090 --> 00:10:20,150
Če lahko premaknete navzdol 1.

237
00:10:20,150 --> 00:10:22,930
>> Sedaj, čeprav, hočem iti do 7.

238
00:10:22,930 --> 00:10:24,280
Sem odprla pot na 6.

239
00:10:24,280 --> 00:10:27,050
Vem, da sem lahko varno
nadaljuje navzdol 6 pot.

240
00:10:27,050 --> 00:10:29,220
Ampak moram nadaljevati na 7 poti.

241
00:10:29,220 --> 00:10:30,580
Torej, kaj moram storiti?

242
00:10:30,580 --> 00:10:35,070
No, tako kot prej, jaz šele potreba
počistiti vrata, ven iz poti,

243
00:10:35,070 --> 00:10:38,740
in zgraditi novo vozlišče s 7 poti.

244
00:10:38,740 --> 00:10:40,250
Tako kot je ta.

245
00:10:40,250 --> 00:10:42,930
>> Torej, zdaj sem se preselil 1 in se nato 7.

246
00:10:42,930 --> 00:10:45,550
In zdaj opazili, da sem nekako
od te nove Subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Vse ostalo od 16
no, jaz ne briga.

249
00:10:49,260 --> 00:10:50,720
Jaz ne delam 16 ničesar.

250
00:10:50,720 --> 00:10:51,750
Delam 17 stvari.

251
00:10:51,750 --> 00:10:58,380
>> Torej, zdaj od 17 naprej, moram
nekako pokazati nove poti tukaj.

252
00:10:58,380 --> 00:11:00,462
Naslednja številka moj ključ je 0.

253
00:11:00,462 --> 00:11:01,670
Jaz seveda ne more dobiti nikjer.

254
00:11:01,670 --> 00:11:02,628
Pravkar sem zgradil to vozlišče.

255
00:11:02,628 --> 00:11:04,550
Zato vem, da ni
poti naprej od tod.

256
00:11:04,550 --> 00:11:06,370
Tako da sem moral narediti eno sam.

257
00:11:06,370 --> 00:11:09,360
>> Tako sem malloc novo vozlišče
in imajo 0 točk tam.

258
00:11:09,360 --> 00:11:12,770
In potem še enkrat, sem malloc
novo vozlišče in ima eno točko tam.

259
00:11:12,770 --> 00:11:15,870
Spet sem izčrpana svoj ključ, 1701.

260
00:11:15,870 --> 00:11:18,472
Zato sem pogledal dol in sem spray barve Yale.

261
00:11:18,472 --> 00:11:19,680
To je ime tega vozlišča.

262
00:11:19,680 --> 00:11:24,660
>> In zdaj, če bom kdaj morali videti, če Yale
je v tem Trie, začnem pri korenu,

263
00:11:24,660 --> 00:11:27,060
Grem dol 1701, in pogledal dol.

264
00:11:27,060 --> 00:11:30,030
In če vidim Yale sprej
pobarvan na tla, potem

265
00:11:30,030 --> 00:11:32,200
Vem Yale obstaja v tem trie.

266
00:11:32,200 --> 00:11:32,950
Naredimo še eno.

267
00:11:32,950 --> 00:11:36,430
Oglejmo vstavite Dartmouth v to
trie, ki je bila ustanovljena leta 1769.

268
00:11:36,430 --> 00:11:37,750
>> Spet pri korenu.

269
00:11:37,750 --> 00:11:39,445
Moja prva številka mojega ključa je 1.

270
00:11:39,445 --> 00:11:40,820
Mirno lahko premikate po tej poti.

271
00:11:40,820 --> 00:11:42,400
Ki že obstaja.

272
00:11:42,400 --> 00:11:44,040
Naslednja številka mojega ključa je 7.

273
00:11:44,040 --> 00:11:45,890
Mirno lahko premikate po tej poti.

274
00:11:45,890 --> 00:11:47,540
Obstaja pa tudi.

275
00:11:47,540 --> 00:11:49,000
>> Moj naslednji pa je 6.

276
00:11:49,000 --> 00:11:52,860
Od tu, od koder sem trenutno jaz
v rumeno je v tem osrednjem vozlišču,

277
00:11:52,860 --> 00:11:56,060
6 je trenutno zaklenjena off.

278
00:11:56,060 --> 00:11:58,830
Če želim iti po tej poti,
Moram ga graditi sam.

279
00:11:58,830 --> 00:12:02,250
Torej bom malloc novo vozlišče
in imajo 6 točko tam.

280
00:12:02,250 --> 00:12:04,250
In potem še enkrat, jaz sem
Plamen nove poti tukaj.

281
00:12:04,250 --> 00:12:10,750
>> Tako sem malloc novo vozlišče tako, da se od
da node-- številka pot 9-- in nato zdaj

282
00:12:10,750 --> 00:12:13,584
če potujem 1769, in sem pogledal dol.

283
00:12:13,584 --> 00:12:15,500
Nič zdaj
spray tam naslikal.

284
00:12:15,500 --> 00:12:16,930
Pisati znam Dartmouth.

285
00:12:16,930 --> 00:12:20,710
In sem se vstavi
Dartmouth v trie.

286
00:12:20,710 --> 00:12:23,450
>> Tako da je vstavljanje
Stvari v trie.

287
00:12:23,450 --> 00:12:25,384
Sedaj želimo iskati stvari.

288
00:12:25,384 --> 00:12:27,050
Kako iščemo stvari v trie?

289
00:12:27,050 --> 00:12:29,170
No, to je precej isto idejo.

290
00:12:29,170 --> 00:12:33,620
Zdaj smo samo uporabo številk ključa
da vidim, če smo lahko premikate od korena

291
00:12:33,620 --> 00:12:37,170
kam želimo iti v trie.

292
00:12:37,170 --> 00:12:41,620
>> Če bomo zadeli slepo ulico na kateri koli točki, nato pa
vemo, da ta element ni mogoče obstaja

293
00:12:41,620 --> 00:12:44,500
ali pa bi, da je pot
že izbil.

294
00:12:44,500 --> 00:12:45,930
Če naredimo to vse tja do
konec, vse, kar morate storiti,

295
00:12:45,930 --> 00:12:48,471
je pogledal dol in videli, če je to
element, ki ga iščemo.

296
00:12:48,471 --> 00:12:49,335
Če je to uspeh.

297
00:12:49,335 --> 00:12:52,610
Če je ne, ne.

298
00:12:52,610 --> 00:12:54,940
>> Tako da je iskanje
Harvard v tem trie.

299
00:12:54,940 --> 00:12:56,020
Začnemo pri korenu.

300
00:12:56,020 --> 00:12:58,228
In še enkrat, bomo
ustvariti prečkanje kazalec

301
00:12:58,228 --> 00:12:59,390
narediti naše poteze za nas.

302
00:12:59,390 --> 00:13:02,080
Od korenin vemo, da je
prvo mesto moramo iti 1,

303
00:13:02,080 --> 00:13:03,390
lahko storimo?

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

305
00:13:03,982 --> 00:13:04,690
Če varno obstaja.

306
00:13:04,690 --> 00:13:06,660
Lahko gremo tja.

307
00:13:06,660 --> 00:13:08,440
>> Zdaj, naslednji kraj moramo iti, je 6.

308
00:13:08,440 --> 00:13:10,557
Ali 6 pot obstaja od tu?

309
00:13:10,557 --> 00:13:11,140
Ja, to počne.

310
00:13:11,140 --> 00:13:12,690
Lahko gremo navzdol 6 pot.

311
00:13:12,690 --> 00:13:13,905
In smo na koncu tukaj.

312
00:13:13,905 --> 00:13:16,130
>> Lahko gremo dol 3 poti od tu?

313
00:13:16,130 --> 00:13:18,450
No, kot se izkaže,
ja, da obstaja preveč.

314
00:13:18,450 --> 00:13:20,790
In lahko pridemo na 6 poti od tu?

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

316
00:13:21,982 --> 00:13:24,002
>> Nismo povsem odgovoril
vprašanje še ni.

317
00:13:24,002 --> 00:13:25,710
Tam je še ena več
korak, ki je sedaj

318
00:13:25,710 --> 00:13:28,520
moramo pogledati navzdol in
vidim, če je to actually--

319
00:13:28,520 --> 00:13:32,660
Če iščemo Harvardu, je, da
Kaj smo ugotovili, ko smo izčrpali ključ?

320
00:13:32,660 --> 00:13:35,430
V našem primeru smo z uporabo tukaj,
leta so vedno štiri številke.

321
00:13:35,430 --> 00:13:40,280
Vendar vas bo morda s pomočjo primer, če
ste shranjevanje slovar besed.

322
00:13:40,280 --> 00:13:44,060
>> In tako namesto ob 10 kazalcev
za mojo lokacijo, boste morda morali 26.

323
00:13:44,060 --> 00:13:46,040
Eno za vsako črko abecede.

324
00:13:46,040 --> 00:13:50,350
In tam so nekatere besede kot bat,
ki je podmnožica serije, npr.

325
00:13:50,350 --> 00:13:53,511
In tako tudi, če prideš do
Konec ključa in jo potem tla

326
00:13:53,511 --> 00:13:55,260
morda ne boste videli, kaj
iščete.

327
00:13:55,260 --> 00:13:58,500
>> Tako boste vedno imeli za prečkanje
celotna pot in nato

328
00:13:58,500 --> 00:14:01,540
če ste bili uspešno mogli
prečkanje celotno pot,

329
00:14:01,540 --> 00:14:03,440
pogledal dol in naredil eno končno potrditev.

330
00:14:03,440 --> 00:14:05,120
Je to tisto, kar iščem?

331
00:14:05,120 --> 00:14:07,740
No, sem pogledal dol po začetku
na vrhu in bo 1636.

332
00:14:07,740 --> 00:14:08,240
Sem pogledal dol.

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

334
00:14:09,400 --> 00:14:11,689
Torej, ja, mi je uspelo.

335
00:14:11,689 --> 00:14:13,980
Kaj pa, če kaj iščem
ni v Trie, čeprav.

336
00:14:13,980 --> 00:14:17,200
Kaj pa, če iščem Princeton,
ki je bila ustanovljena leta 1746.

337
00:14:17,200 --> 00:14:20,875
In tako je leta 1746 postal moj ključ
krmariti skozi trie.

338
00:14:20,875 --> 00:14:22,040
No, naj začnem pri korenu.

339
00:14:22,040 --> 00:14:24,760
In na prvem mestu želim
da gre navzdol 1 pot.

340
00:14:24,760 --> 00:14:25,590
Ali lahko to storim?

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

342
00:14:26,490 --> 00:14:28,730
>> Lahko grem dol 7 poti od tam?

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

344
00:14:29,230 --> 00:14:30,750
Da obstaja preveč.

345
00:14:30,750 --> 00:14:32,460
Ampak lahko grem dol s 4 poti od tu?

346
00:14:32,460 --> 00:14:35,550
To je kot asking vprašanje, lahko
Sem se nadaljuje navzdol, da malo square

347
00:14:35,550 --> 00:14:37,114
da sem označen z rumeno barvo?

348
00:14:37,114 --> 00:14:38,030
Nič ni tam.

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

350
00:14:38,610 --> 00:14:41,310
>> Ni šans, naprej dol po 4 poti.

351
00:14:41,310 --> 00:14:46,480
Če je Princeton v tem Trie, da 4
bi bili izbil za nas že.

352
00:14:46,480 --> 00:14:49,130
In tako se na tej točki
smo dosegli slepo ulico.

353
00:14:49,130 --> 00:14:50,250
Mi ne more iti več naprej.

354
00:14:50,250 --> 00:14:53,440
In tako lahko rečemo, dokončno, št.

355
00:14:53,440 --> 00:14:56,760
Princeton ne obstaja v tem trie.

356
00:14:56,760 --> 00:14:58,860
>> Torej, kaj vse to pomeni?

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

358
00:14:59,360 --> 00:15:01,000
Tam je veliko dogaja.

359
00:15:01,000 --> 00:15:02,500
Tam je kazalci po vsem mestu.

360
00:15:02,500 --> 00:15:04,249
In, kot lahko vidite
samo iz diagrama,

361
00:15:04,249 --> 00:15:07,010
tam je veliko vozlišč, ki
so nekako plujejo okoli.

362
00:15:07,010 --> 00:15:13,480
Ampak obvestilo vsakič, ko smo želeli
preveriti, ali je bilo nekaj v Trie,

363
00:15:13,480 --> 00:15:15,000
smo imeli šele, da bi 4 poteze.

364
00:15:15,000 --> 00:15:17,208
>> Vsakič, ko smo želeli
nekaj vstavili v Trie,

365
00:15:17,208 --> 00:15:20,440
moramo narediti 4 poteze, po možnosti
mallocing nekaj stvari na tej poti.

366
00:15:20,440 --> 00:15:23,482
Toda, kot smo videli, ko smo vstavi
Dartmouth v Trie,

367
00:15:23,482 --> 00:15:25,940
včasih nekatere sredino
je morda že izbil za nas.

368
00:15:25,940 --> 00:15:30,520
In tako kot naša trie dobi večji in
večji, moramo storiti manj dela vsakič

369
00:15:30,520 --> 00:15:32,270
vstaviti nove stvari
Ker smo že

370
00:15:32,270 --> 00:15:35,746
zgradili veliko vmesna
veje vzdolž poti.

371
00:15:35,746 --> 00:15:38,370
Če bomo samo kdaj pogledati
4 stvari, 4 je le konstantna.

372
00:15:38,370 --> 00:15:41,750
Res smo se nekako približuje
stalen čas vstavitve

373
00:15:41,750 --> 00:15:44,501
in konstantna čas iskanje.

374
00:15:44,501 --> 00:15:47,500
Kompromis, seveda, le da
to trie, kot si verjetno lahko povem,

375
00:15:47,500 --> 00:15:49,030
je ogromno.

376
00:15:49,030 --> 00:15:51,040
Vsak od teh vozlišč
zavzame veliko prostora.

377
00:15:51,040 --> 00:15:52,090
>> Ampak to je kompromis.

378
00:15:52,090 --> 00:15:55,260
Če želimo res hitro
vstavljanje, res hiter izbris,

379
00:15:55,260 --> 00:15:59,630
in res hitro iskanje, moramo
imajo veliko podatkov plujejo okoli.

380
00:15:59,630 --> 00:16:03,590
Moramo prahi veliko prostora
in pomnilnik za te strukture podatkov

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

382
00:16:04,290 --> 00:16:05,415
>> In tako, da je kompromis.

383
00:16:05,415 --> 00:16:07,310
Ampak izgleda, da mi
Morda so ga našli.

384
00:16:07,310 --> 00:16:09,560
Smo lahko ugotovili, da
Sveti gral podatkovnih struktur

385
00:16:09,560 --> 00:16:12,264
s hitro vstavljanje,
izbris in iskanje.

386
00:16:12,264 --> 00:16:14,430
In morda to bo
ustrezno strukturo podatkov

387
00:16:14,430 --> 00:16:18,890
uporabiti za katerega koli informacij
poskušamo trgovini.

388
00:16:18,890 --> 00:16:21,860
Sem Doug Lloyd, to je CS50.

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