1
00:00:00,000 --> 00:00:02,994
>> [Prehrávanie hudby]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Takže sme boli blíži sa
a bližšie, že svätý grál dát

4
00:00:08,550 --> 00:00:13,050
štruktúry, ten, ktorý môžeme vložiť
do, odstrániť z, a pozerať sa

5
00:00:13,050 --> 00:00:15,440
v konštantnom čase.

6
00:00:15,440 --> 00:00:16,270
Správne.

7
00:00:16,270 --> 00:00:17,280
To je niečo ako ciele.

8
00:00:17,280 --> 00:00:19,720
Chceme byť schopní robiť
veci veľmi, veľmi rýchlo.

9
00:00:19,720 --> 00:00:22,580
>> Už sme ho našli tu, keď
hovoríme o pokusoch?

10
00:00:22,580 --> 00:00:23,670
Dobre, poďme sa pozrieť.

11
00:00:23,670 --> 00:00:25,628
Takže sme videli niekoľko
rôzne dátové štruktúry

12
00:00:25,628 --> 00:00:28,680
že zvládnuť mapovanie
tzv párov kľúč-hodnota,

13
00:00:28,680 --> 00:00:32,080
mapovanie nejakú časť dát
na nejakú inú časť dát

14
00:00:32,080 --> 00:00:36,020
takže vieme, kde nájsť
Informácie v štruktúre.

15
00:00:36,020 --> 00:00:40,060
>> Takže pre pole, napríklad,
Kľúčom k úspechu je index prvok alebo pole

16
00:00:40,060 --> 00:00:42,600
Poloha 0 alebo 1 pole, a tak ďalej.

17
00:00:42,600 --> 00:00:46,140
A je hodnota údaje
že v danom umiestnení existuje.

18
00:00:46,140 --> 00:00:48,550
Takže to, čo je uložené v poli 0?

19
00:00:48,550 --> 00:00:54,290
To, čo je uložený v matici 1 v porovnaní s práve
0 a 1, čo by bolo kľúča.

20
00:00:54,290 --> 00:00:56,360
>> S hash tabuľky je to
druh z rovnakej myšlienky.

21
00:00:56,360 --> 00:01:00,690
S hash tabuľky, máme túto hash
funkcia, ktorá generuje hash kódy.

22
00:01:00,690 --> 00:01:03,670
Takže kľúč je hash kód dát.

23
00:01:03,670 --> 00:01:06,530
A hodnota, najmä
sme sa rozprávali o reťazenie

24
00:01:06,530 --> 00:01:10,590
vo videu na stoly mriežky,
je to, že spojená zoznam údajov,

25
00:01:10,590 --> 00:01:12,550
že hash k tomuto hashCode.

26
00:01:12,550 --> 00:01:14,050
Správne.

27
00:01:14,050 --> 00:01:16,050
Čo iného prístupu
Táto metóda, aj keď?

28
00:01:16,050 --> 00:01:21,000
Ako je to spôsob, kde
Kľúčom je zaručené, že je jedinečný,

29
00:01:21,000 --> 00:01:25,410
na rozdiel od tabuľky hash, kde by sme mohli
skončiť s dvoma kusmi dát

30
00:01:25,410 --> 00:01:27,200
ktoré majú rovnakú hodnotu hash.

31
00:01:27,200 --> 00:01:30,020
A potom máme čo do činenia s
že buď snímania alebo viac

32
00:01:30,020 --> 00:01:33,340
prednostne reťazenie vyriešiť tento problém.

33
00:01:33,340 --> 00:01:37,520
>> Takže teraz môžeme zaručiť
že náš kľúč bude jedinečná.

34
00:01:37,520 --> 00:01:39,690
A čo keď naša hodnota bola
proste niečo tak jednoduché

35
00:01:39,690 --> 00:01:44,080
ako true a false, ktorá nám hovorí, či
či nie, že časť informácie

36
00:01:44,080 --> 00:01:45,610
existuje v štruktúre?

37
00:01:45,610 --> 00:01:48,180
Boolovská môže byť rovnako jednoduché ako trochu.

38
00:01:48,180 --> 00:01:52,660
Reálne je to asi
byte s väčšou pravdepodobnosťou ako trochu.

39
00:01:52,660 --> 00:01:55,410
Ale to je oveľa menšie, než
uloženie možná 50-reťazec znakov,

40
00:01:55,410 --> 00:01:57,360
napríklad.

41
00:01:57,360 --> 00:02:02,210
>> Takže pokusoch, podobne ako hash tabuľky,
ktoré kombinujú polia a spájať zoznam,

42
00:02:02,210 --> 00:02:05,790
snaží kombinovať polia,
štruktúry, a ukazovatele

43
00:02:05,790 --> 00:02:08,509
spoločne ukladať dáta v
zaujímavý spôsob, ako to je

44
00:02:08,509 --> 00:02:11,550
celkom odlišný od
čokoľvek, čo sme doteraz videli.

45
00:02:11,550 --> 00:02:16,750
Teraz budeme používať dáta ako cestovná mapa
navigovať túto štruktúru dát.

46
00:02:16,750 --> 00:02:18,710
A ak môžeme sledovať
Cestovná mapa, ak môžeme

47
00:02:18,710 --> 00:02:22,390
nasledovať dáta z
začiatku až do konca, budeme

48
00:02:22,390 --> 00:02:24,945
vedieť, či týchto dát
existujú v trie.

49
00:02:24,945 --> 00:02:28,310
>> A keď nemôžeme sledovať mapu
čo znamená, ze do konca vôbec,

50
00:02:28,310 --> 00:02:30,600
dáta nemôže existovať.

51
00:02:30,600 --> 00:02:32,890
Opäť platí, že tu sú kľúče
zaručená jedinečnosť.

52
00:02:32,890 --> 00:02:36,020
A tak na rozdiel od stola mriežky, budeme nikdy
budú musieť vysporiadať s kolíziami tu.

53
00:02:36,020 --> 00:02:39,090
A žiadne dva kusy dát
majú presne rovnaký plán

54
00:02:39,090 --> 00:02:40,530
ibaže, že údaje sú totožné.

55
00:02:40,530 --> 00:02:44,580
>> Ak vložíme John, potom
hľadáme pre Johna.

56
00:02:44,580 --> 00:02:47,430
To je dve identické kusy
Údaje, vpravo, pozeráme skrz.

57
00:02:47,430 --> 00:02:49,880
Ale inak, akákoľvek
dva kusy dát sú

58
00:02:49,880 --> 00:02:52,750
zaručené, že majú jedinečné plány
prostredníctvom tejto dátovej štruktúry.

59
00:02:52,750 --> 00:02:56,210
A budeme sa pozrieť na
vizuálne to za chvíľu.

60
00:02:56,210 --> 00:02:58,810
>> Urobíme to, že sa snaží
vytvoriť novú dátovú štruktúru,

61
00:02:58,810 --> 00:03:00,564
mapovanie tieto dvojice hodnoty kľúča.

62
00:03:00,564 --> 00:03:03,480
V tomto prípade, nebudeme používať
niečo tak jednoduchého, ako Boolean.

63
00:03:03,480 --> 00:03:06,200
Vlastne sme uloží reťazec.

64
00:03:06,200 --> 00:03:08,690
A to reťazec sa chystá
byť názov vysokej školy.

65
00:03:08,690 --> 00:03:12,140
>> A kľúč bude rok
kedy bola založená, že vysokoškolské.

66
00:03:12,140 --> 00:03:15,380
Všetky roky pre vysoké školy
sa bude štyri číslice.

67
00:03:15,380 --> 00:03:19,840
A tak budeme používať tie štyri číslice
prechádzať tejto dátové štruktúry.

68
00:03:19,840 --> 00:03:22,270
A uvidíme, opäť, ako
urobíme, že v len sekundu.

69
00:03:22,270 --> 00:03:25,110
>> Na konci dráhy,
uvidíme meno

70
00:03:25,110 --> 00:03:30,250
univerzity, ktorá zodpovedá
k tlačidlu, tieto štyri číslice.

71
00:03:30,250 --> 00:03:34,390
Základnou myšlienkou trie
je máme centrálne trasu.

72
00:03:34,390 --> 00:03:35,640
Takže myslíte, že o tom ako strom.

73
00:03:35,640 --> 00:03:39,211
A toto je podobné v hláskovanie
a v poňatí k stromu.

74
00:03:39,211 --> 00:03:41,460
Všeobecne platí, keď si myslíme, že o
stromy v reálnom svete,

75
00:03:41,460 --> 00:03:44,090
majú koreň, ktorý je v
pozemné a rastú nahor

76
00:03:44,090 --> 00:03:46,830
a oni majú pobočky
a majú listy.

77
00:03:46,830 --> 00:03:49,450
A v podstate myšlienka
Trie je presne rovnaký,

78
00:03:49,450 --> 00:03:51,755
s výnimkou, že koreň je ukotvený
niekde na oblohe.

79
00:03:51,755 --> 00:03:53,130
A listy sú v spodnej časti.

80
00:03:53,130 --> 00:03:55,750
>> Takže je to trochu ako s strom
a len preklopeniu hore nohami.

81
00:03:55,750 --> 00:03:56,880
Ale sú tu ešte pobočky.

82
00:03:56,880 --> 00:03:59,463
A tí by sa naše cesty,
tie budú naše spoje

83
00:03:59,463 --> 00:04:02,220
z koreňa do listov.

84
00:04:02,220 --> 00:04:04,200
V tomto prípade, tí,
ciest, tieto pobočky

85
00:04:04,200 --> 00:04:08,490
sú označené číslicami, ktoré vypovedajú
kadiaľ ísť z miesta, kde sme.

86
00:04:08,490 --> 00:04:11,800
>> Ak vidíme 0, pôjdeme dole tohto odvetvia,
ak vidíme 1, pôjdeme dole tohto odvetvia,

87
00:04:11,800 --> 00:04:12,900
a tak, a tak ďalej.

88
00:04:12,900 --> 00:04:14,060
No, čo to znamená?

89
00:04:14,060 --> 00:04:16,519
No, to znamená, že
v každom spojovacom mieste

90
00:04:16,519 --> 00:04:19,260
a každý uzol vo
prostrednej a každá vetva,

91
00:04:19,260 --> 00:04:23,020
tam sú 10 možný
miest, ktoré môžeme ísť.

92
00:04:23,020 --> 00:04:27,690
Takže existuje 10 ukazovateľov
z každého miesta.

93
00:04:27,690 --> 00:04:30,610
>> A to je miesto, kde sa pokúsi sa dostať
trochu zastrašujúce pre niekoho

94
00:04:30,610 --> 00:04:34,460
kto ich nemá veľa
skúsenosti v oblasti počítačovej vedy pred.

95
00:04:34,460 --> 00:04:35,960
Ale snaží sú naozaj dosť desivý.

96
00:04:35,960 --> 00:04:37,793
A ak máte
možnosť pracovať s nimi

97
00:04:37,793 --> 00:04:40,420
a ste ochotní kopať-in
a experimentovať s nimi,

98
00:04:40,420 --> 00:04:44,234
sú naozaj celkom zaujímavé
dátové štruktúry pre prácu s.

99
00:04:44,234 --> 00:04:46,900
Ak chceme vložiť prvok
do trie, všetko, čo potrebujete urobiť,

100
00:04:46,900 --> 00:04:51,360
je vytvoriť správnu cestu
z koreňa do listu.

101
00:04:51,360 --> 00:04:55,390
Tu je to, čo na každom kroku pozdĺž
spôsob, ako by mohla vyzerať.

102
00:04:55,390 --> 00:04:59,660
Budeme definovať nové údaje
štruktúra pre nový uzol nazývaný trie.

103
00:04:59,660 --> 00:05:02,560
>> A vo vnútri týchto údajov
Štruktúra existujú dva kusy.

104
00:05:02,560 --> 00:05:05,460
Chystáme sa ukladať
meno univerzity.

105
00:05:05,460 --> 00:05:09,410
A budeme uchovávať
poľa ukazovateľov

106
00:05:09,410 --> 00:05:12,190
do iných uzlov rovnakého typu.

107
00:05:12,190 --> 00:05:14,780
Takže, znovu, je to, že druh
z koncepcie všade

108
00:05:14,780 --> 00:05:18,567
my sme, sme na 10 možný
miesta môžeme ísť.

109
00:05:18,567 --> 00:05:20,150
Ak vidíme 0, pôjdeme dole toto odvetvie.

110
00:05:20,150 --> 00:05:22,690
Ak budeme vidieť 1, toto odvetvie,
a tak ďalej, a tak ďalej a tak ďalej.

111
00:05:22,690 --> 00:05:25,160
Ak hovoríme, 9, pôjdeme dole toto odvetvie.

112
00:05:25,160 --> 00:05:28,220
Takže v každom spojovacom mieste,
môžeme ísť 10 možných miest.

113
00:05:28,220 --> 00:05:35,740
Každý uzol tak musí obsahovať 10 ukazovatele
do iných uzlov, do 10 ostatných uzlov.

114
00:05:35,740 --> 00:05:39,810
>> A dáta, my ich ukladanie
len názov univerzity.

115
00:05:39,810 --> 00:05:41,060
Takže poďme postaviť trie.

116
00:05:41,060 --> 00:05:44,860
Poďme vložiť pár
predmetov do našich trie.

117
00:05:44,860 --> 00:05:46,740
Takže na samom vrchole,
to je náš koreň.

118
00:05:46,740 --> 00:05:49,740
Toto je pravdepodobne bude niečo
budete globálne vyhlasujú.

119
00:05:49,740 --> 00:05:53,450
A vy budete globálne udržanie
ukazovateľ na tento uzol vždy.

120
00:05:53,450 --> 00:05:55,360
>> Budeš hovoriť,
koreň rovná, a vy ste

121
00:05:55,360 --> 00:05:57,580
bude malloc sami trie uzol.

122
00:05:57,580 --> 00:05:59,850
A vy nikdy
dotknúť koreň znova.

123
00:05:59,850 --> 00:06:02,300
Zakaždým, keď budete chcieť
prehliada,

124
00:06:02,300 --> 00:06:05,802
môžete nastaviť ďalšie ukazovatele
rovnajúcu sa koreň, ako je napríklad tráv,

125
00:06:05,802 --> 00:06:07,760
čo je príklad I
použitie v mnohých mojich videí

126
00:06:07,760 --> 00:06:11,090
tu na komíny a fronty
a odkaz zoznamy, a tak ďalej.

127
00:06:11,090 --> 00:06:13,320
>> Môžete nastaviť inú ukazovateľ
volal tráv umožňujúcim priechod.

128
00:06:13,320 --> 00:06:15,890
A používate tráv k navigácii
cez dátové štruktúry.

129
00:06:15,890 --> 00:06:17,500
Tak uvidíme, ako to môže vyzerať.

130
00:06:17,500 --> 00:06:19,880
Takže teraz, čo
robí uzol vyzerá?

131
00:06:19,880 --> 00:06:22,920
No, rovnako ako naše dáta
Vyhlásenie štruktúra je uvedené,

132
00:06:22,920 --> 00:06:26,906
Máme reťazec, ktorý
v tomto prípade je prázdny.

133
00:06:26,906 --> 00:06:27,780
Tu nič nie je.

134
00:06:27,780 --> 00:06:29,550
>> A pole 10 ukazovateľov.

135
00:06:29,550 --> 00:06:31,790
A práve teraz, my len
má 1 uzol v tomto trie.

136
00:06:31,790 --> 00:06:33,110
Na tom nie je nič iné v ňom.

137
00:06:33,110 --> 00:06:36,020
Takže všetko 10 z tých,
ukazovatele bod na hodnotu null.

138
00:06:36,020 --> 00:06:38,090
To je to, čo červená indikuje.

139
00:06:38,090 --> 00:06:39,500
>> Poďme vložte reťazec Harvard.

140
00:06:39,500 --> 00:06:41,999
Poďme vložte univerzita
Harvard do tejto trie, ktorý

141
00:06:41,999 --> 00:06:43,940
bola založená v roku 1636.

142
00:06:43,940 --> 00:06:48,220
Chceme použiť kľúč,
1.636, nám povedať, kde sme

143
00:06:48,220 --> 00:06:50,140
bude ukladať Harvard v trie.

144
00:06:50,140 --> 00:06:51,470
Teraz, ako by to urobíme?

145
00:06:51,470 --> 00:06:52,886
>> Mohlo by to vyzerať nejako takto.

146
00:06:52,886 --> 00:06:54,160
Začneme pri koreni.

147
00:06:54,160 --> 00:06:56,920
A máme týchto 10 miest, môžeme ísť.

148
00:06:56,920 --> 00:06:59,900
Koreň je rovnako ako akýkoľvek
iný uzol trie.

149
00:06:59,900 --> 00:07:02,850
K dispozícii je 10 miest, môžeme prejsť od tady.

150
00:07:02,850 --> 00:07:07,215
>> Kam pravdepodobne chceme
kam ísť, ak je kľúč 1636?

151
00:07:07,215 --> 00:07:08,340
Je to naozaj dve možnosti.

152
00:07:08,340 --> 00:07:08,450
Správne.

153
00:07:08,450 --> 00:07:10,825
Môžeme vytvoriť kľúč od
sprava doľava a začať s 6.

154
00:07:10,825 --> 00:07:14,000
Alebo by sme mohli postaviť kľúč
zľava doprava a začať s 1.

155
00:07:14,000 --> 00:07:16,140
>> Je to pravdepodobne viac
intuitívne ako ľudská bytosť

156
00:07:16,140 --> 00:07:18,110
porozumieť budeme
Stačí ísť zľava doprava.

157
00:07:18,110 --> 00:07:21,140
A tak, keď chcem vložiť
Harvard do tejto trie,

158
00:07:21,140 --> 00:07:23,560
Asi Chcem začať
tým, že začína pri koreni,

159
00:07:23,560 --> 00:07:25,720
pri pohľade na mojej 10 možností
predo mnou, a povedal

160
00:07:25,720 --> 00:07:28,700
Chcem ísť dole 1 cestu.

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

162
00:07:29,700 --> 00:07:31,810
>> Teraz, 1 cesta je v súčasnej dobe null.

163
00:07:31,810 --> 00:07:35,920
Takže ak chcem pokračovať touto cestou
vložiť tento prvok do trie,

164
00:07:35,920 --> 00:07:42,040
Musím malloc nový uzol, má 1
bod tam, a potom som dobré ísť.

165
00:07:42,040 --> 00:07:46,460
>> Takže som v podstate som v a
miesto, kde stojím

166
00:07:46,460 --> 00:07:50,270
pri koreni stromu alebo pod
Trie a tam sú 10 pobočiek.

167
00:07:50,270 --> 00:07:52,260
Ale každá vetva má
brána pred ním.

168
00:07:52,260 --> 00:07:53,060
Správne.

169
00:07:53,060 --> 00:07:54,850
Vzhľadom k tomu, nič iné tam.

170
00:07:54,850 --> 00:07:56,522
No bezpečný priechod.

171
00:07:56,522 --> 00:07:58,980
To znamená, že nie je nič
sa niektorý z týchto vetiev.

172
00:07:58,980 --> 00:08:02,532
Ak chcem začať stavať
niečo, chcem odstrániť bránu.

173
00:08:02,532 --> 00:08:04,490
Chcem odstrániť bránu
Pred číslo 1.

174
00:08:04,490 --> 00:08:05,698
A ja chcem ísť dole, že.

175
00:08:05,698 --> 00:08:08,060
A ja chcem stavať
ďalšie miesto pre mňa ísť.

176
00:08:08,060 --> 00:08:09,470
>> A to je to, čo som tu urobil.

177
00:08:09,470 --> 00:08:11,430
Takže 1 už poukazuje na hodnotu null.

178
00:08:11,430 --> 00:08:13,830
Povedal som, že to je bezpečné ísť dole teraz tu.

179
00:08:13,830 --> 00:08:15,789
Postavil som iného uzla.

180
00:08:15,789 --> 00:08:18,330
A keď som sa dostať do tohto uzla, I
majú ďalšie rozhodnutie urobiť.

181
00:08:18,330 --> 00:08:20,890
Kam mám ísť odtiaľto?

182
00:08:20,890 --> 00:08:22,700
>> No, ja som už preč dolu 1.

183
00:08:22,700 --> 00:08:24,470
Takže teraz pravdepodobne chcieť ísť dole 6.

184
00:08:24,470 --> 00:08:24,970
Správne.

185
00:08:24,970 --> 00:08:27,100
Opäť platí, že mám 10 miest si môžem vybrať.

186
00:08:27,100 --> 00:08:30,060
Takže poďme teraz ísť dole číslo 6.

187
00:08:30,060 --> 00:08:32,280
Tak som vyčistiť bránu
Pred číslo 6.

188
00:08:32,280 --> 00:08:33,250
A idem tam dole.

189
00:08:33,250 --> 00:08:34,580
A ja vybudovať ďalšie uzol.

190
00:08:34,580 --> 00:08:37,630
A ja som dosiahol ďalšieho spojovací bod.

191
00:08:37,630 --> 00:08:40,289
>> Opäť platí, že mám 10 možností
Pre kam môžem ísť.

192
00:08:40,289 --> 00:08:42,799
Som sa presťahoval od 1 do 6.

193
00:08:42,799 --> 00:08:44,215
Takže teraz pravdepodobne chcieť ísť na 3.

194
00:08:44,215 --> 00:08:45,381
3, nie je kam môžem ísť.

195
00:08:45,381 --> 00:08:48,980
Takže mám vyčistiť cestu
a vybudovať sám nový priestor.

196
00:08:48,980 --> 00:08:50,870
A potom sa z 3, kam chcem ísť?

197
00:08:50,870 --> 00:08:52,450
Chcem ísť dole 6.

198
00:08:52,450 --> 00:08:54,770
>> A opäť som musel
uvoľniť cestu, ako to urobiť.

199
00:08:54,770 --> 00:08:59,179
Takže teraz Použil som svoj kľúč k vloženie vytvoreniu
uzly a začať budovať tento trie.

200
00:08:59,179 --> 00:09:00,220
Začal som pri koreni.

201
00:09:00,220 --> 00:09:03,666
Ja som išiel dole 1636.

202
00:09:03,666 --> 00:09:05,540
A teraz som na dne
tam v danom uzle.

203
00:09:05,540 --> 00:09:06,610
A vy ste mali byť schopní
vidieť na obrazovke.

204
00:09:06,610 --> 00:09:07,735
>> Je zvýraznená žltou farbou.

205
00:09:07,735 --> 00:09:10,020
To je miesto, kde v súčasnej dobe som ja.

206
00:09:10,020 --> 00:09:11,300
Môj kľúč je hotovo.

207
00:09:11,300 --> 00:09:13,030
Ja som vyčerpal všetky pozície vo svojom kľúči.

208
00:09:13,030 --> 00:09:15,040
Takže nemôžem ísť ďalej.

209
00:09:15,040 --> 00:09:17,720
Takže v tomto bode, všetko, čo som
naozaj potrebujete urobiť, je povedať, OK.

210
00:09:17,720 --> 00:09:18,990
Je to trochu ako pozerať sa
dole na zem,

211
00:09:18,990 --> 00:09:21,115
ak ste si predstavovať
Chcete sa tento druh cesty

212
00:09:21,115 --> 00:09:22,350
s rôznymi typmi pripojenia.

213
00:09:22,350 --> 00:09:25,800
Druh pozerať sa dole a druh
sprej maľovanie Harvarde na zemi.

214
00:09:25,800 --> 00:09:26,800
To je názov tohto.

215
00:09:26,800 --> 00:09:28,300
Vedzte, že to, čo je na tomto mieste.

216
00:09:28,300 --> 00:09:31,870
Ak začneme pri koreni a ideme dole
1 a potom na 6 a potom 3 a potom 6,

217
00:09:31,870 --> 00:09:32,780
Kde sme?

218
00:09:32,780 --> 00:09:35,640
No, ak sa pozrieme dolu
a vidíme Harvard, potom

219
00:09:35,640 --> 00:09:38,960
vieme, že Harvard bol
založená v roku 1636 na základe spôsobu, akým

220
00:09:38,960 --> 00:09:41,400
budeme vykonávanie tohto dátovú štruktúru.

221
00:09:41,400 --> 00:09:43,177
Tak to bol snáď jednoduchá.

222
00:09:43,177 --> 00:09:44,760
Chystáme sa urobiť dve ďalšie inzercie.

223
00:09:44,760 --> 00:09:50,060
A dúfajme, že to pomôže, aby
vidieť toto urobil ešte dvakrát.

224
00:09:50,060 --> 00:09:52,210
>> Teraz sa poďme vložiť inú univerzitu.

225
00:09:52,210 --> 00:09:54,630
Poďme vložiť Yale do tejto trie.

226
00:09:54,630 --> 00:09:57,037
Yale bol založený v roku 1701.

227
00:09:57,037 --> 00:09:58,870
Takže začneme u
koreň, ako sme vždy robiť.

228
00:09:58,870 --> 00:09:59,890
A my sme nastavili ukazovateľ traversal.

229
00:09:59,890 --> 00:10:01,624
Budeme používať, ktoré pre pohyb.

230
00:10:01,624 --> 00:10:03,790
Prvá vec, ktorú chceme
urobiť, je ísť dole na 1 cestu.

231
00:10:03,790 --> 00:10:05,830
To je prvá číslica z našich kľúčových.

232
00:10:05,830 --> 00:10:08,420
Našťastie, aj keď, my nie
musieť robiť žiadnu prácu tentoraz.

233
00:10:08,420 --> 00:10:09,919
1 Cesta už bola vymazaná.

234
00:10:09,919 --> 00:10:13,520
Vymazané som to už skôr, keď som
bola vložením Harvarde v roku 1636.

235
00:10:13,520 --> 00:10:18,090
Takže môžem bezpečne presunúť
nadol 1 a jednoducho ísť tam.

236
00:10:18,090 --> 00:10:20,150
Ak sa môže pohybovať dole 1.

237
00:10:20,150 --> 00:10:22,930
>> A teraz, keď chcem ísť až 7.

238
00:10:22,930 --> 00:10:24,280
Vymazané som, ako na 6.

239
00:10:24,280 --> 00:10:27,050
Viem, že môžem bezpečne
pokračujte po chodníku 6.

240
00:10:27,050 --> 00:10:29,220
Ale musím pokračovať na ceste 7.

241
00:10:29,220 --> 00:10:30,580
Takže to, čo musím urobiť?

242
00:10:30,580 --> 00:10:35,070
No, rovnako ako predtým, len potrebujem
zrušte bránu, dostať sa z cesty,

243
00:10:35,070 --> 00:10:38,740
a vytvoriť nový uzol z cesty 7.

244
00:10:38,740 --> 00:10:40,250
Podobne ako tento.

245
00:10:40,250 --> 00:10:42,930
>> Takže teraz som sa presťahoval 1 a potom 7.

246
00:10:42,930 --> 00:10:45,550
A teraz si všimnúť, že som nejako
z o tejto novej subbranch.

247
00:10:45,550 --> 00:10:46,050
Správne.

248
00:10:46,050 --> 00:10:49,260
Všetko ostatné od 16
, Ja sa nestarám o.

249
00:10:49,260 --> 00:10:50,720
Nerobím 16 nič.

250
00:10:50,720 --> 00:10:51,750
Robím 17 veci.

251
00:10:51,750 --> 00:10:58,380
>> Takže teraz od 17. dňa, musím
druh objavenie nových ciest tu.

252
00:10:58,380 --> 00:11:00,462
Ďalšie číslica môj kľúč je 0.

253
00:11:00,462 --> 00:11:01,670
Jasne som nemôže dostať kamkoľvek.

254
00:11:01,670 --> 00:11:02,628
Len som postavil tento uzol.

255
00:11:02,628 --> 00:11:04,550
Takže viem, že to nie je
cesty vpred odtiaľ.

256
00:11:04,550 --> 00:11:06,370
Takže som musel urobiť jednu sám.

257
00:11:06,370 --> 00:11:09,360
>> Tak som malloc nový uzol
a majú tam bod 0.

258
00:11:09,360 --> 00:11:12,770
A potom ešte raz, som malloc
Nový uzol a majú tam jeden bod.

259
00:11:12,770 --> 00:11:15,870
Opäť platí, že som vyčerpal svoj kľúč, 1701.

260
00:11:15,870 --> 00:11:18,472
Tak som sa dole a ja sprej maľovať Yale.

261
00:11:18,472 --> 00:11:19,680
To je meno tohto uzla.

262
00:11:19,680 --> 00:11:24,660
>> A tak teraz, keď som niekedy potrebovať zistiť, či Yale
je v tomto trie, začnem pri koreni,

263
00:11:24,660 --> 00:11:27,060
Idem dole 1701, a pozerať sa dole.

264
00:11:27,060 --> 00:11:30,030
A keď vidím Yale sprej
maľované na zem a potom

265
00:11:30,030 --> 00:11:32,200
Viem, že Yale existuje v tomto trie.

266
00:11:32,200 --> 00:11:32,950
Urobme ešte jeden.

267
00:11:32,950 --> 00:11:36,430
Poďme do toho vložiť Dartmouth
Trie, ktorá bola založená v roku 1769.

268
00:11:36,430 --> 00:11:37,750
>> Začnite pri koreni znova.

269
00:11:37,750 --> 00:11:39,445
Moja prvá číslica môj kľúč je 1.

270
00:11:39,445 --> 00:11:40,820
Môžem bezpečne pohybovať touto cestou.

271
00:11:40,820 --> 00:11:42,400
To už existuje.

272
00:11:42,400 --> 00:11:44,040
Ďalšie číslica mojej kľúča je 7.

273
00:11:44,040 --> 00:11:45,890
Môžem bezpečne pohybovať touto cestou.

274
00:11:45,890 --> 00:11:47,540
Existuje tiež.

275
00:11:47,540 --> 00:11:49,000
>> Moje ďalšie je 6.

276
00:11:49,000 --> 00:11:52,860
Odtiaľ odkiaľ Aj v súčasnej dobe som
žlto tam v tom strednom uzla,

277
00:11:52,860 --> 00:11:56,060
6 aktuálne uzamknutý preč.

278
00:11:56,060 --> 00:11:58,830
Ak chcem ísť touto cestou,
Musím sa postaviť to sám.

279
00:11:58,830 --> 00:12:02,250
Takže budem malloc nový uzol
a majú 6 bod tam.

280
00:12:02,250 --> 00:12:04,250
A potom zase, že som
horiace nové chodníky tu.

281
00:12:04,250 --> 00:12:10,750
>> Tak som malloc nový uzol, takže z
že node-- číslo trasy 9-- a potom teraz

282
00:12:10,750 --> 00:12:13,584
ak cestujem 1769, a Pozriem sa dole.

283
00:12:13,584 --> 00:12:15,500
Nie je nič, čo v súčasnej dobe
nastriekal tam.

284
00:12:15,500 --> 00:12:16,930
Dokážem napísať Dartmouth.

285
00:12:16,930 --> 00:12:20,710
A ja som vložená
Dartmouth do trie.

286
00:12:20,710 --> 00:12:23,450
>> Tak to je vkladanie
veci do trie.

287
00:12:23,450 --> 00:12:25,384
Teraz chceme hľadať veci.

288
00:12:25,384 --> 00:12:27,050
Ako môžeme hľadať veci v trie?

289
00:12:27,050 --> 00:12:29,170
No, je to celkom veľa rovnaký nápad.

290
00:12:29,170 --> 00:12:33,620
Teraz už stačí použiť číslica kľúče
aby zistil, či môžeme prejsť od koreňa

291
00:12:33,620 --> 00:12:37,170
na miesto, kde chceme ísť v trie.

292
00:12:37,170 --> 00:12:41,620
>> Ak sme narazili do slepej uličky na akomkoľvek mieste, potom
Vieme, že tento prvok nemôže existuje

293
00:12:41,620 --> 00:12:44,500
alebo že cesta by
už boli vymazané.

294
00:12:44,500 --> 00:12:45,930
Ak budeme robiť to celú cestu do
koniec, všetko, čo potrebujete urobiť,

295
00:12:45,930 --> 00:12:48,471
je pozerať sa dole a zistiť, či je to
prvok hľadáme.

296
00:12:48,471 --> 00:12:49,335
Ak je, úspech.

297
00:12:49,335 --> 00:12:52,610
Ak to nie je, zlyhať.

298
00:12:52,610 --> 00:12:54,940
>> Takže poďme hľadať
Harvard v tomto trie.

299
00:12:54,940 --> 00:12:56,020
Začneme pri koreni.

300
00:12:56,020 --> 00:12:58,228
A opäť, budeme
vytvoriť ukazovateľ traversal

301
00:12:58,228 --> 00:12:59,390
k tomu naše pohyby pre nás.

302
00:12:59,390 --> 00:13:02,080
Z koreňa vieme, že
Prvé miesto, musíme ísť, je 1,

303
00:13:02,080 --> 00:13:03,390
môžeme urobiť, že?

304
00:13:03,390 --> 00:13:03,982
Áno, môžme.

305
00:13:03,982 --> 00:13:04,690
Ak sa bezpečne existuje.

306
00:13:04,690 --> 00:13:06,660
Môžeme ísť tam.

307
00:13:06,660 --> 00:13:08,440
>> Teraz, ďalšie miesto, musíme ísť, je 6.

308
00:13:08,440 --> 00:13:10,557
Má cesta 6 existovať ďalej?

309
00:13:10,557 --> 00:13:11,140
Jo, je to tak.

310
00:13:11,140 --> 00:13:12,690
Môžeme ísť po ceste 6.

311
00:13:12,690 --> 00:13:13,905
A my sme sa sem.

312
00:13:13,905 --> 00:13:16,130
>> Môžeme ísť dole 3 cesty z tu?

313
00:13:16,130 --> 00:13:18,450
No, ako to dopadá,
áno, že existuje taky.

314
00:13:18,450 --> 00:13:20,790
A môžeme dostať na 6 ceste odtiaľto?

315
00:13:20,790 --> 00:13:21,982
Áno, môžme.

316
00:13:21,982 --> 00:13:24,002
>> Ešte sme sa úplne odpovedal
otázka doteraz.

317
00:13:24,002 --> 00:13:25,710
Je tu ešte jeden
krok, ktorý je teraz

318
00:13:25,710 --> 00:13:28,520
musíme sa pozrieť dole a
zistiť, či je to actually--

319
00:13:28,520 --> 00:13:32,660
ak hľadáme Harvardu, je to, že
Čo sme zistili, keď sme vyčerpať kľúč?

320
00:13:32,660 --> 00:13:35,430
V príklade sme pomocou tu,
roky sú vždy štyri číslice.

321
00:13:35,430 --> 00:13:40,280
Ale tie by mohli byť pomocou na príklad, kde
sú ukladanie slovník slov.

322
00:13:40,280 --> 00:13:44,060
>> A tak namiesto toho, aby 10 ukazovateľov
pre moje umiestnenie, môžete mať 26.

323
00:13:44,060 --> 00:13:46,040
Jeden pre každé písmeno abecedy.

324
00:13:46,040 --> 00:13:50,350
A tam sú niektoré slová ako netopier,
ktorý je podmnožinou dávky, napríklad.

325
00:13:50,350 --> 00:13:53,511
A tak aj keď sa dostanete do
koniec kľúče a pozerať sa dole,

326
00:13:53,511 --> 00:13:55,260
nemusíte vidieť, čo
hľadáte.

327
00:13:55,260 --> 00:13:58,500
>> Takže budete mať vždy prejsť
celú cestu a potom

328
00:13:58,500 --> 00:14:01,540
ak ste boli schopní úspešne
prechádzať celú cestu,

329
00:14:01,540 --> 00:14:03,440
pozerať sa dole a urobiť jednu finálnu potvrdenie.

330
00:14:03,440 --> 00:14:05,120
Je to to, čo som hľadal?

331
00:14:05,120 --> 00:14:07,740
No, Pozriem sa dolu po spustení
hore a ísť 1636.

332
00:14:07,740 --> 00:14:08,240
Pozriem sa dolu.

333
00:14:08,240 --> 00:14:09,400
Vidím Harvarde.

334
00:14:09,400 --> 00:14:11,689
Takže áno, uspel som.

335
00:14:11,689 --> 00:14:13,980
Čo či to, čo Hľadám
nie je v trie, hoci.

336
00:14:13,980 --> 00:14:17,200
Čo keď som hľadal Princeton,
ktorá bola založená v roku 1746.

337
00:14:17,200 --> 00:14:20,875
A tak sa stáva 1746 môj kľúč
prechádzať trie.

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

339
00:14:22,040 --> 00:14:24,760
A na prvom mieste chcem
sa ide dole na 1 cestu.

340
00:14:24,760 --> 00:14:25,590
Môžem to urobiť?

341
00:14:25,590 --> 00:14:26,490
Áno môžem.

342
00:14:26,490 --> 00:14:28,730
>> Môžem ísť po ceste od 7 tam?

343
00:14:28,730 --> 00:14:29,230
Jo, môžem.

344
00:14:29,230 --> 00:14:30,750
To existuje taky.

345
00:14:30,750 --> 00:14:32,460
Ale môžem ísť dole 4 cesty odtiaľto?

346
00:14:32,460 --> 00:14:35,550
To je ako pýtať na otázku, môže
Mám postupovať dole, že malý štvorec

347
00:14:35,550 --> 00:14:37,114
že som zvýraznené žlto?

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

349
00:14:38,030 --> 00:14:38,610
Správne.

350
00:14:38,610 --> 00:14:41,310
>> Neexistuje spôsob, ako vpred dole 4 ceste.

351
00:14:41,310 --> 00:14:46,480
Ak Princeton bolo v tejto trie, že 4
by boli vymazané už pre nás.

352
00:14:46,480 --> 00:14:49,130
A tak v tomto bode
dosiahli sme do slepej uličky.

353
00:14:49,130 --> 00:14:50,250
Nemôžeme ísť ďalej.

354
00:14:50,250 --> 00:14:53,440
A tak môžeme povedať, definitívne, no.

355
00:14:53,440 --> 00:14:56,760
Princeton neexistuje v tomto trie.

356
00:14:56,760 --> 00:14:58,860
>> Takže čo to všetko znamená?

357
00:14:58,860 --> 00:14:59,360
Správne.

358
00:14:59,360 --> 00:15:01,000
Je tu veľa deje.

359
00:15:01,000 --> 00:15:02,500
Je tu ukazovatele po celom mieste.

360
00:15:02,500 --> 00:15:04,249
A ako môžete vidieť,
Len z diagramu,

361
00:15:04,249 --> 00:15:07,010
je tu veľa z uzlov, ktoré
sú druh lietania okolo.

362
00:15:07,010 --> 00:15:13,480
Povšimnime si ale zakaždým, keď sme chceli
overiť, či sa niečo v trie,

363
00:15:13,480 --> 00:15:15,000
sme mali len, aby 4 ťahy.

364
00:15:15,000 --> 00:15:17,208
>> Zakaždým, keď sme chceli
vložiť niečo v trie,

365
00:15:17,208 --> 00:15:20,440
musíme 4 pohyby, prípadne
mallocing nejaké veci pozdĺž cesty.

366
00:15:20,440 --> 00:15:23,482
Ale ako sme videli, keď sme vložená
Dartmouth do trie,

367
00:15:23,482 --> 00:15:25,940
niekedy niektoré z cesty
už môže byť zrušené pre nás.

368
00:15:25,940 --> 00:15:30,520
A tak ako naše Trie dostane väčšie a
väčšie, musíme robiť menej práce zakaždým,

369
00:15:30,520 --> 00:15:32,270
vložiť nové veci
pretože sme už

370
00:15:32,270 --> 00:15:35,746
postavený veľa medziproduktu
vetvy pozdĺž cesty.

371
00:15:35,746 --> 00:15:38,370
Ak budeme len niekedy sa pozrieť na
4 veci, 4 je len konštantná.

372
00:15:38,370 --> 00:15:41,750
Naozaj sme sa trochu blíži
konštantný vloženie čas

373
00:15:41,750 --> 00:15:44,501
a konštantný čas vyhľadávania.

374
00:15:44,501 --> 00:15:47,500
Kompromis, samozrejme, je, že
Trie to, ako si asi povedať,

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

376
00:15:49,030 --> 00:15:51,040
Každý z týchto uzlov
zaberá veľa miesta.

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

378
00:15:52,090 --> 00:15:55,260
Ak chceme naozaj rýchlo
vloženie, naozaj rýchly vymazanie,

379
00:15:55,260 --> 00:15:59,630
a naozaj rýchlo vyhľadávania, musíme
majú veľké množstvo dát lietajúce okolo.

380
00:15:59,630 --> 00:16:03,590
Musíme vyčleniť veľa priestoru
a pamäť pre túto štruktúru dát

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

382
00:16:04,290 --> 00:16:05,415
>> A tak to je kompromis.

383
00:16:05,415 --> 00:16:07,310
Ale vyzerá to, že
Možno ho našli.

384
00:16:07,310 --> 00:16:09,560
Mohli sme zistili, že
svätý grál dátových štruktúr

385
00:16:09,560 --> 00:16:12,264
s rýchlym zavedením,
zmazanie a vyhľadávanie.

386
00:16:12,264 --> 00:16:14,430
A možno to bude
vhodné dátové štruktúry

387
00:16:14,430 --> 00:16:18,890
použiť pre akékoľvek informácie,
snažíme sa obchodu.

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

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