1
00:00:00,000 --> 00:00:02,994
>> [Přehrávání hudby]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Takže jsme byli blíží se
a blíž, že svatý grál dat

4
00:00:08,550 --> 00:00:13,050
struktury, ten, který můžeme vložit
do, odstranit z, a dívat se

5
00:00:13,050 --> 00:00:15,440
v konstantním čase.

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

7
00:00:16,270 --> 00:00:17,280
To je něco jako cíle.

8
00:00:17,280 --> 00:00:19,720
Chceme být schopni dělat
věci velmi, velmi rychle.

9
00:00:19,720 --> 00:00:22,580
>> Už jsme ho našli tady, když
mluvíme o pokusech?

10
00:00:22,580 --> 00:00:23,670
Dobře, pojďme se podívat.

11
00:00:23,670 --> 00:00:25,628
Takže jsme viděli několik
různé datové struktury

12
00:00:25,628 --> 00:00:28,680
že zvládnout mapování
tzv párů klíč-hodnota,

13
00:00:28,680 --> 00:00:32,080
mapování nějakou část dat
na nějakou jinou část dat

14
00:00:32,080 --> 00:00:36,020
takže víme, kde najít
Informace ve struktuře.

15
00:00:36,020 --> 00:00:40,060
>> Takže pro pole, například,
Klíčem k úspěchu je index prvek nebo pole

16
00:00:40,060 --> 00:00:42,600
Poloha 0 nebo 1 pole, a tak dále.

17
00:00:42,600 --> 00:00:46,140
A je hodnota údaje
že v daném umístění existuje.

18
00:00:46,140 --> 00:00:48,550
Takže to, co je uloženo v poli 0?

19
00:00:48,550 --> 00:00:54,290
To, co je uložen v matici 1 ve srovnání s právě
0 a 1, což by bylo klíče.

20
00:00:54,290 --> 00:00:56,360
>> S hash tabulky je to
druh ze stejné myšlenky.

21
00:00:56,360 --> 00:01:00,690
S hash tabulky, máme tuto hash
funkce, která generuje hash kódy.

22
00:01:00,690 --> 00:01:03,670
Takže klíč je hash kód dat.

23
00:01:03,670 --> 00:01:06,530
A hodnota, zejména
jsme si povídali o řetězení

24
00:01:06,530 --> 00:01:10,590
ve videu na stoly mřížky,
je to, že spojená seznam údajů,

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

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

27
00:01:14,050 --> 00:01:16,050
Co jiného přístupu
Tato metoda, i když?

28
00:01:16,050 --> 00:01:21,000
Jak je to způsob, kde
Klíčem je zaručeno, že je jedinečný,

29
00:01:21,000 --> 00:01:25,410
na rozdíl od tabulky hash, kde bychom mohli
skončit s dvěma kusy dat

30
00:01:25,410 --> 00:01:27,200
které mají stejnou hodnotu hash.

31
00:01:27,200 --> 00:01:30,020
A pak máme co do činění s
že buď snímání nebo více

32
00:01:30,020 --> 00:01:33,340
přednostně řetězení vyřešit tento problém.

33
00:01:33,340 --> 00:01:37,520
>> Takže teď můžeme zaručit
že náš klíč bude jedinečná.

34
00:01:37,520 --> 00:01:39,690
A co když naše hodnota byla
prostě něco tak snadné

35
00:01:39,690 --> 00:01:44,080
jako true a false, která nám říká, zda
či ne, že část informace

36
00:01:44,080 --> 00:01:45,610
existuje ve struktuře?

37
00:01:45,610 --> 00:01:48,180
Booleovská může být stejně jednoduché jako trochu.

38
00:01:48,180 --> 00:01:52,660
Reálně je to asi
byte s větší pravděpodobností než trochu.

39
00:01:52,660 --> 00:01:55,410
Ale to je mnohem menší, než
uložení možná 50-řetězec znaků,

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

41
00:01:57,360 --> 00:02:02,210
>> Takže pokusech, podobně jako hash tabulky,
které kombinují pole a spojový seznam,

42
00:02:02,210 --> 00:02:05,790
snaží kombinovat pole,
struktury, a ukazatele

43
00:02:05,790 --> 00:02:08,509
společně ukládat data v
zajímavý způsob, jak to je

44
00:02:08,509 --> 00:02:11,550
docela odlišný od
cokoliv, co jsme dosud viděli.

45
00:02:11,550 --> 00:02:16,750
Nyní budeme používat data jako cestovní mapa
navigovat tuto strukturu dat.

46
00:02:16,750 --> 00:02:18,710
A pokud můžeme sledovat
Cestovní mapa, pokud můžeme

47
00:02:18,710 --> 00:02:22,390
následovat data z
začátku až do konce, budeme

48
00:02:22,390 --> 00:02:24,945
vědět, zda těchto dat
existují v trie.

49
00:02:24,945 --> 00:02:28,310
>> A když nemůžeme sledovat mapu
což znamená, ze do konce vůbec,

50
00:02:28,310 --> 00:02:30,600
data nemůže existovat.

51
00:02:30,600 --> 00:02:32,890
Opět platí, že zde jsou klíče
zaručena jedinečnost.

52
00:02:32,890 --> 00:02:36,020
A tak na rozdíl od stolu mřížky, budeme nikdy
budou muset vypořádat s kolizemi zde.

53
00:02:36,020 --> 00:02:39,090
A žádné dva kusy dat
mají přesně stejný plán

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

55
00:02:40,530 --> 00:02:44,580
>> Pokud vložíme John, pak
hledáme pro Johna.

56
00:02:44,580 --> 00:02:47,430
To je dvě identické kusy
Údaje, vpravo, díváme skrz.

57
00:02:47,430 --> 00:02:49,880
Ale jinak, jakákoliv
dva kusy dat jsou

58
00:02:49,880 --> 00:02:52,750
zaručeno, že mají jedinečné plány
prostřednictvím této datové struktury.

59
00:02:52,750 --> 00:02:56,210
A budeme se podívat na
vizuální to za chvíli.

60
00:02:56,210 --> 00:02:58,810
>> Uděláme to, že se snaží
vytvořit novou datovou strukturu,

61
00:02:58,810 --> 00:03:00,564
mapování tyto dvojice hodnoty klíče.

62
00:03:00,564 --> 00:03:03,480
V tomto případě, nebudeme používat
něco tak jednoduchého, jako Boolean.

63
00:03:03,480 --> 00:03:06,200
Vlastně jsme uloží řetězec.

64
00:03:06,200 --> 00:03:08,690
A to řetězec se chystá
být název vysoké školy.

65
00:03:08,690 --> 00:03:12,140
>> A klíč bude rok
kdy byla založena, že vysokoškolské.

66
00:03:12,140 --> 00:03:15,380
Všechny roky pro vysoké školy
se bude čtyři číslice.

67
00:03:15,380 --> 00:03:19,840
A tak budeme používat ty čtyři číslic
procházet této datové struktury.

68
00:03:19,840 --> 00:03:22,270
A uvidíme, opět, jak
uděláme, že v jen sekundu.

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

70
00:03:25,110 --> 00:03:30,250
univerzity, která odpovídá
k tlačítku, tyto čtyři číslice.

71
00:03:30,250 --> 00:03:34,390
Základní myšlenkou trie
je máme centrální trasu.

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

73
00:03:35,640 --> 00:03:39,211
A toto je podobné v hláskování
a v pojetí k stromu.

74
00:03:39,211 --> 00:03:41,460
Obecně platí, když si myslíme, že o
stromy v reálném světě,

75
00:03:41,460 --> 00:03:44,090
mají kořen, který je v
pozemní a rostou vzhůru

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 podstatě myšlenka
Trie je přesně stejný,

78
00:03:49,450 --> 00:03:51,755
s výjimkou, že kořen je ukotven
někde na obloze.

79
00:03:51,755 --> 00:03:53,130
A listy jsou ve spodní části.

80
00:03:53,130 --> 00:03:55,750
>> Takže je to trochu jako s strom
a jen překlopení vzhůru nohama.

81
00:03:55,750 --> 00:03:56,880
Ale jsou tu ještě pobočky.

82
00:03:56,880 --> 00:03:59,463
A ti by se naše cesty,
ty budou naše spoje

83
00:03:59,463 --> 00:04:02,220
z kořene do listů.

84
00:04:02,220 --> 00:04:04,200
V tomto případě, ti,
cest, tyto pobočky

85
00:04:04,200 --> 00:04:08,490
jsou označeny číslicemi, které vypovídají
kudy jít z místa, kde jsme.

86
00:04:08,490 --> 00:04:11,800
>> Pokud vidíme 0, půjdeme dolů tohoto odvětví,
pokud vidíme 1, půjdeme dolů tohoto odvětví,

87
00:04:11,800 --> 00:04:12,900
a tak, a tak dále.

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

89
00:04:14,060 --> 00:04:16,519
No, to znamená, že
v každém spojovacím místě

90
00:04:16,519 --> 00:04:19,260
a každý uzel ve
prostřední a každá větev,

91
00:04:19,260 --> 00:04:23,020
tam jsou 10 možný
míst, které můžeme jít.

92
00:04:23,020 --> 00:04:27,690
Takže existuje 10 ukazatelů
z každého místa.

93
00:04:27,690 --> 00:04:30,610
>> A to je místo, kde se pokusí se dostat
trochu zastrašující pro někoho

94
00:04:30,610 --> 00:04:34,460
kdo je nemá mnoho
zkušenosti v oblasti počítačové vědy před.

95
00:04:34,460 --> 00:04:35,960
Ale snaží jsou opravdu dost děsivý.

96
00:04:35,960 --> 00:04:37,793
A pokud máte
možnost pracovat s nimi

97
00:04:37,793 --> 00:04:40,420
a jste ochotni kopat-in
a experimentovat s nimi,

98
00:04:40,420 --> 00:04:44,234
jsou opravdu docela zajímavé
datové struktury pro práci s.

99
00:04:44,234 --> 00:04:46,900
Chceme-li vložit prvek
do trie, vše, co potřebujete udělat,

100
00:04:46,900 --> 00:04:51,360
je vytvořit správnou cestu
z kořene do listu.

101
00:04:51,360 --> 00:04:55,390
Tady je to, co na každém kroku podél
způsob, jak by mohla vypadat.

102
00:04:55,390 --> 00:04:59,660
Budeme definovat nové údaje
struktura pro nový uzel nazývaný trie.

103
00:04:59,660 --> 00:05:02,560
>> A uvnitř těchto údajů
Struktura existují dva kusy.

104
00:05:02,560 --> 00:05:05,460
Chystáme se ukládat
jméno univerzity.

105
00:05:05,460 --> 00:05:09,410
A budeme uchovávat
pole ukazatelů

106
00:05:09,410 --> 00:05:12,190
do jiných uzlů stejného typu.

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

108
00:05:14,780 --> 00:05:18,567
my jsme, jsme na 10 možný
místa můžeme jít.

109
00:05:18,567 --> 00:05:20,150
Pokud vidíme 0, půjdeme dolů toto odvětví.

110
00:05:20,150 --> 00:05:22,690
Pokud budeme vidět 1, toto odvětví,
a tak dále, a tak dále a tak dále.

111
00:05:22,690 --> 00:05:25,160
Říkáme-li, 9, půjdeme dolů toto odvětví.

112
00:05:25,160 --> 00:05:28,220
Takže v každém spojovacím místě,
můžeme jít 10 možných míst.

113
00:05:28,220 --> 00:05:35,740
Každý uzel tak musí obsahovat 10 ukazatele
do jiných uzlů, do 10 ostatních uzlů.

114
00:05:35,740 --> 00:05:39,810
>> A data, my je ukládání
jen název univerzity.

115
00:05:39,810 --> 00:05:41,060
Takže pojďme postavit trie.

116
00:05:41,060 --> 00:05:44,860
Pojďme vložit pár
předmětů do našich trie.

117
00:05:44,860 --> 00:05:46,740
Takže na samém vrcholu,
to je náš kořen.

118
00:05:46,740 --> 00:05:49,740
Toto je pravděpodobně bude něco
budete globálně prohlašují.

119
00:05:49,740 --> 00:05:53,450
A vy budete globálně udržení
ukazatel na tento uzel vždy.

120
00:05:53,450 --> 00:05:55,360
>> Budeš říkat,
kořen rovná, a vy jste

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

122
00:05:57,580 --> 00:05:59,850
A vy nikdy
dotknout kořen znovu.

123
00:05:59,850 --> 00:06:02,300
Pokaždé, když budete chtít
zahájit procházení,

124
00:06:02,300 --> 00:06:05,802
můžete nastavit další ukazatele
rovnající se kořen, jako je například trav,

125
00:06:05,802 --> 00:06:07,760
což je příklad I
použití v mnoha mých videí

126
00:06:07,760 --> 00:06:11,090
tady na komíny a fronty
a odkaz seznamy, a tak dále.

127
00:06:11,090 --> 00:06:13,320
>> Můžete nastavit jinou ukazatel
volal trav umožňujícím průchod.

128
00:06:13,320 --> 00:06:15,890
A používáte trav k navigaci
přes datové struktury.

129
00:06:15,890 --> 00:06:17,500
Tak uvidíme, jak to může vypadat.

130
00:06:17,500 --> 00:06:19,880
Takže teď, co
dělá uzel vypadá?

131
00:06:19,880 --> 00:06:22,920
No, stejně jako naše data
Prohlášení struktura je uvedeno,

132
00:06:22,920 --> 00:06:26,906
Máme řetězec, který
v tomto případě je prázdný.

133
00:06:26,906 --> 00:06:27,780
Tady nic není.

134
00:06:27,780 --> 00:06:29,550
>> A pole 10 ukazatelů.

135
00:06:29,550 --> 00:06:31,790
A právě teď, my jen
má 1 uzel v tomto trie.

136
00:06:31,790 --> 00:06:33,110
Na tom není nic jiného v něm.

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

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

139
00:06:38,090 --> 00:06:39,500
>> Pojďme vložte řetězec Harvard.

140
00:06:39,500 --> 00:06:41,999
Pojďme vložte univerzita
Harvard do této trie, který

141
00:06:41,999 --> 00:06:43,940
byla založena v roce 1636.

142
00:06:43,940 --> 00:06:48,220
Chceme použít klíč,
1.636, nám říct, kde jsme

143
00:06:48,220 --> 00:06:50,140
bude ukládat Harvard v trie.

144
00:06:50,140 --> 00:06:51,470
Nyní, jak by to uděláme?

145
00:06:51,470 --> 00:06:52,886
>> Mohlo by to vypadat nějak takhle.

146
00:06:52,886 --> 00:06:54,160
Začneme u kořene.

147
00:06:54,160 --> 00:06:56,920
A máme těchto 10 míst, můžeme jít.

148
00:06:56,920 --> 00:06:59,900
Kořen je stejně jako jakýkoli
jiný uzel trie.

149
00:06:59,900 --> 00:07:02,850
K dispozici je 10 míst, můžeme přejít od tady.

150
00:07:02,850 --> 00:07:07,215
>> Kam pravděpodobně chceme
kam jít, pokud je klíč 1636?

151
00:07:07,215 --> 00:07:08,340
Je to opravdu dvě možnosti.

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

153
00:07:08,450 --> 00:07:10,825
Můžeme vytvořit klíč od
zprava doleva a začít s 6.

154
00:07:10,825 --> 00:07:14,000
Nebo bychom mohli postavit klíč
zleva doprava a začít s 1.

155
00:07:14,000 --> 00:07:16,140
>> Je to pravděpodobně více
intuitivní jako lidská bytost

156
00:07:16,140 --> 00:07:18,110
porozumět budeme
Stačí jít zleva doprava.

157
00:07:18,110 --> 00:07:21,140
A tak, když chci vložit
Harvard do této trie,

158
00:07:21,140 --> 00:07:23,560
Asi Chci začít
tím, že začíná u kořene,

159
00:07:23,560 --> 00:07:25,720
při pohledu na mé 10 možností
přede mnou, a řekl

160
00:07:25,720 --> 00:07:28,700
Chci jít dolů 1 cestu.

161
00:07:28,700 --> 00:07:29,700
DOBŘE.

162
00:07:29,700 --> 00:07:31,810
>> Nyní, 1 cesta je v současné době null.

163
00:07:31,810 --> 00:07:35,920
Takže pokud chci pokračovat touto cestou
vložit tento prvek do trie,

164
00:07:35,920 --> 00:07:42,040
Musím malloc nový uzel, má 1
bod tam, a pak jsem dobré jít.

165
00:07:42,040 --> 00:07:46,460
>> Takže jsem v podstatě jsem v a
místo, kde stojím

166
00:07:46,460 --> 00:07:50,270
u kořene stromu nebo pod
Trie a tam jsou 10 poboček.

167
00:07:50,270 --> 00:07:52,260
Ale každá větev má
brána před ním.

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

169
00:07:53,060 --> 00:07:54,850
Vzhledem k tomu, nic jiného tam.

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

171
00:07:56,522 --> 00:07:58,980
To znamená, že není nic
se některý z těchto větví.

172
00:07:58,980 --> 00:08:02,532
Pokud chci začít stavět
něco, chci odstranit bránu.

173
00:08:02,532 --> 00:08:04,490
Chci odstranit bránu
Před číslo 1.

174
00:08:04,490 --> 00:08:05,698
A já chci jít dolů, že.

175
00:08:05,698 --> 00:08:08,060
A já chci stavět
další místo pro mě jít.

176
00:08:08,060 --> 00:08:09,470
>> A to je to, co jsem tady udělal.

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

178
00:08:11,430 --> 00:08:13,830
Řekl jsem, že to je bezpečné jít dolů teď tady.

179
00:08:13,830 --> 00:08:15,789
Postavil jsem jiného uzlu.

180
00:08:15,789 --> 00:08:18,330
A když jsem se dostat do tohoto uzlu, I
mají další rozhodnutí učinit.

181
00:08:18,330 --> 00:08:20,890
Kam mám jít odsud?

182
00:08:20,890 --> 00:08:22,700
>> No, já jsem už pryč dolů 1.

183
00:08:22,700 --> 00:08:24,470
Takže teď pravděpodobně chtít jít dolů 6.

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

185
00:08:24,970 --> 00:08:27,100
Opět platí, že mám 10 míst si mohu vybrat.

186
00:08:27,100 --> 00:08:30,060
Takže pojďme teď jít dolů číslo 6.

187
00:08:30,060 --> 00:08:32,280
Tak jsem vyčistit bránu
Před číslo 6.

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

189
00:08:33,250 --> 00:08:34,580
A já vybudovat další uzel.

190
00:08:34,580 --> 00:08:37,630
A já jsem dosáhl dalšího spojovací bod.

191
00:08:37,630 --> 00:08:40,289
>> Opět platí, že mám 10 možností
Pro kam můžu jít.

192
00:08:40,289 --> 00:08:42,799
Jsem se přestěhoval od 1 do 6.

193
00:08:42,799 --> 00:08:44,215
Takže teď pravděpodobně chtít jít na 3.

194
00:08:44,215 --> 00:08:45,381
3, není kam můžu jít.

195
00:08:45,381 --> 00:08:48,980
Takže mám vyčistit cestu
a vybudovat sám nový prostor.

196
00:08:48,980 --> 00:08:50,870
A pak se z 3, kam chci jít?

197
00:08:50,870 --> 00:08:52,450
Chci jít dolů 6.

198
00:08:52,450 --> 00:08:54,770
>> A opět jsem musel
uvolnit cestu, jak to udělat.

199
00:08:54,770 --> 00:08:59,179
Takže teď Použil jsem svůj klíč k vložení vytvoření
uzly a začít budovat tento trie.

200
00:08:59,179 --> 00:09:00,220
Začal jsem u kořene.

201
00:09:00,220 --> 00:09:03,666
Já jsem šel dolů 1636.

202
00:09:03,666 --> 00:09:05,540
A teď jsem na dně
tam v daném uzlu.

203
00:09:05,540 --> 00:09:06,610
A vy jste měli být schopni
vidět na obrazovce.

204
00:09:06,610 --> 00:09:07,735
>> Je zvýrazněna žlutě.

205
00:09:07,735 --> 00:09:10,020
To je místo, kde v současné době jsem já.

206
00:09:10,020 --> 00:09:11,300
Můj klíč je hotovo.

207
00:09:11,300 --> 00:09:13,030
Já jsem vyčerpal všechny pozice ve svém klíči.

208
00:09:13,030 --> 00:09:15,040
Takže nemohu jít dál.

209
00:09:15,040 --> 00:09:17,720
Takže v tomto bodě, všechno, co jsem
opravdu potřebujete udělat, je říct, OK.

210
00:09:17,720 --> 00:09:18,990
Je to trochu jako dívat se
dolů na zem,

211
00:09:18,990 --> 00:09:21,115
pokud jste si představovat
Chcete se tento druh cesty

212
00:09:21,115 --> 00:09:22,350
s různými typy připojení.

213
00:09:22,350 --> 00:09:25,800
Druh dívat se dolů a druh
sprej malování Harvardu na zemi.

214
00:09:25,800 --> 00:09:26,800
To je název tohoto.

215
00:09:26,800 --> 00:09:28,300
Vězte, že to, co je na tomto místě.

216
00:09:28,300 --> 00:09:31,870
Pokud začneme u kořene a jedeme dolů
1 a poté na 6 a pak 3 a pak 6,

217
00:09:31,870 --> 00:09:32,780
kde jsme?

218
00:09:32,780 --> 00:09:35,640
No, pokud se podíváme dolů
a vidíme Harvard, pak

219
00:09:35,640 --> 00:09:38,960
víme, že Harvard byl
založena v roce 1636 na základě způsobu, jakým

220
00:09:38,960 --> 00:09:41,400
budeme provádění tohoto datovou strukturu.

221
00:09:41,400 --> 00:09:43,177
Tak to byl snad jednoduchá.

222
00:09:43,177 --> 00:09:44,760
Chystáme se udělat dvě další inzerce.

223
00:09:44,760 --> 00:09:50,060
A doufejme, že to pomůže, aby
vidět toto udělal ještě dvakrát.

224
00:09:50,060 --> 00:09:52,210
>> Nyní se pojďme vložit jinou univerzitu.

225
00:09:52,210 --> 00:09:54,630
Pojďme vložit Yale do této trie.

226
00:09:54,630 --> 00:09:57,037
Yale byl založen v roce 1701.

227
00:09:57,037 --> 00:09:58,870
Takže začneme u
kořen, jak jsme vždycky dělat.

228
00:09:58,870 --> 00:09:59,890
A my jsme nastavili ukazatel traversal.

229
00:09:59,890 --> 00:10:01,624
Budeme používat, které pro pohyb.

230
00:10:01,624 --> 00:10:03,790
První věc, kterou chceme
udělat, je jít dolů na 1 cestu.

231
00:10:03,790 --> 00:10:05,830
To je první číslice z našich klíčových.

232
00:10:05,830 --> 00:10:08,420
Naštěstí, i když, my ne
muset dělat žádnou práci tentokrát.

233
00:10:08,420 --> 00:10:09,919
1 Cesta již byla smazána.

234
00:10:09,919 --> 00:10:13,520
Vymazány jsem to již dříve, když jsem
byla vložením Harvardu v roce 1636.

235
00:10:13,520 --> 00:10:18,090
Takže můžu bezpečně přesunout
dolů 1 a prostě jít tam.

236
00:10:18,090 --> 00:10:20,150
Pokud se může pohybovat dolů 1.

237
00:10:20,150 --> 00:10:22,930
>> A teď, když chci jít až 7.

238
00:10:22,930 --> 00:10:24,280
Vymazány jsem, jak na 6.

239
00:10:24,280 --> 00:10:27,050
Vím, že můžu bezpečně
pokračujte po pěšině 6.

240
00:10:27,050 --> 00:10:29,220
Ale musím pokračovat na cestě 7.

241
00:10:29,220 --> 00:10:30,580
Takže to, co musím udělat?

242
00:10:30,580 --> 00:10:35,070
No, stejně jako předtím, jen potřebuju
zrušte bránu, dostat se z cesty,

243
00:10:35,070 --> 00:10:38,740
a vytvořit nový uzel z cesty 7.

244
00:10:38,740 --> 00:10:40,250
Stejně jako tento.

245
00:10:40,250 --> 00:10:42,930
>> Takže teď jsem se přestěhoval 1 a pak 7.

246
00:10:42,930 --> 00:10:45,550
A teď si všimnout, že jsem nějak
ze dne o této nové subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Všechno ostatní od 16
, já se nestarám o.

249
00:10:49,260 --> 00:10:50,720
Nedělám 16 nic.

250
00:10:50,720 --> 00:10:51,750
Dělám 17 věci.

251
00:10:51,750 --> 00:10:58,380
>> Takže teď od 17. dne, musím
druh objevení nových cest zde.

252
00:10:58,380 --> 00:11:00,462
Další číslice můj klíč je 0.

253
00:11:00,462 --> 00:11:01,670
Jasně jsem nemůže dostat kamkoliv.

254
00:11:01,670 --> 00:11:02,628
Jen jsem postavil tento uzel.

255
00:11:02,628 --> 00:11:04,550
Takže vím, že to není
cesty vpřed odtud.

256
00:11:04,550 --> 00:11:06,370
Takže jsem musel udělat jednu sám.

257
00:11:06,370 --> 00:11:09,360
>> Tak jsem malloc nový uzel
a mají tam bod 0.

258
00:11:09,360 --> 00:11:12,770
A pak ještě jednou, jsem malloc
Nový uzel a mají tam jeden bod.

259
00:11:12,770 --> 00:11:15,870
Opět platí, že jsem vyčerpal svůj klíč, 1701.

260
00:11:15,870 --> 00:11:18,472
Tak jsem se dolů a já sprej malovat Yale.

261
00:11:18,472 --> 00:11:19,680
To je jméno tohoto uzlu.

262
00:11:19,680 --> 00:11:24,660
>> A tak teď, když jsem někdy potřebovat zjistit, jestli Yale
je v tomto trie, začnu u kořene,

263
00:11:24,660 --> 00:11:27,060
Jdu dolů 1701, a dívat se dolů.

264
00:11:27,060 --> 00:11:30,030
A když vidím Yale sprej
malované na zem a poté

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

266
00:11:32,200 --> 00:11:32,950
Udělejme ještě jeden.

267
00:11:32,950 --> 00:11:36,430
Pojďme do toho vložit Dartmouth
Trie, která byla založena v roce 1769.

268
00:11:36,430 --> 00:11:37,750
>> Začněte u kořene znovu.

269
00:11:37,750 --> 00:11:39,445
Moje první číslice můj klíč je 1.

270
00:11:39,445 --> 00:11:40,820
Mohu bezpečně pohybovat touto cestou.

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

272
00:11:42,400 --> 00:11:44,040
Další číslice mé klíče je 7.

273
00:11:44,040 --> 00:11:45,890
Mohu bezpečně pohybovat touto cestou.

274
00:11:45,890 --> 00:11:47,540
Existuje také.

275
00:11:47,540 --> 00:11:49,000
>> Mé další je 6.

276
00:11:49,000 --> 00:11:52,860
Odtud odkud I v současné době jsem
žlutě tam v tom středním uzlu,

277
00:11:52,860 --> 00:11:56,060
6 aktuálně uzamčen pryč.

278
00:11:56,060 --> 00:11:58,830
Pokud chci jít touto cestou,
Musím se postavit to sám.

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

280
00:12:02,250 --> 00:12:04,250
A pak zase, že jsem
hořící nové stezky zde.

281
00:12:04,250 --> 00:12:10,750
>> Tak jsem malloc nový uzel, takže z
že node-- číslo trasy 9-- a pak nyní

282
00:12:10,750 --> 00:12:13,584
pokud cestuji 1769, a Podívám se dolů.

283
00:12:13,584 --> 00:12:15,500
Není nic, co v současné době
nastříkal tam.

284
00:12:15,500 --> 00:12:16,930
Dokážu napsat Dartmouth.

285
00:12:16,930 --> 00:12:20,710
A já jsem vložena
Dartmouth do trie.

286
00:12:20,710 --> 00:12:23,450
>> Tak to je vkládání
věci do trie.

287
00:12:23,450 --> 00:12:25,384
Nyní chceme hledat věci.

288
00:12:25,384 --> 00:12:27,050
Jak můžeme hledat věci v trie?

289
00:12:27,050 --> 00:12:29,170
No, je to docela hodně stejný nápad.

290
00:12:29,170 --> 00:12:33,620
Teď už stačí použít číslice klíče
aby zjistil, jestli můžeme přejít od kořene

291
00:12:33,620 --> 00:12:37,170
na místo, kde chceme jít v trie.

292
00:12:37,170 --> 00:12:41,620
>> Pokud jsme narazili do slepé uličky na jakémkoli místě, pak
Víme, že tento prvek nemůže existuje

293
00:12:41,620 --> 00:12:44,500
anebo že cesta by
již byly vymazány.

294
00:12:44,500 --> 00:12:45,930
Pokud budeme dělat to celou cestu do
konec, vše, co potřebujete udělat,

295
00:12:45,930 --> 00:12:48,471
je dívat se dolů a zjistit, jestli je to
prvek hledáme.

296
00:12:48,471 --> 00:12:49,335
Pokud je, úspěch.

297
00:12:49,335 --> 00:12:52,610
Pokud to není, selhat.

298
00:12:52,610 --> 00:12:54,940
>> Takže pojďme hledat
Harvard v tomto trie.

299
00:12:54,940 --> 00:12:56,020
Začneme u kořene.

300
00:12:56,020 --> 00:12:58,228
A opět, budeme
vytvořit ukazatel traversal

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

302
00:12:59,390 --> 00:13:02,080
Z kořene víme, že
První místo, musíme jít, je 1,

303
00:13:02,080 --> 00:13:03,390
můžeme udělat, že?

304
00:13:03,390 --> 00:13:03,982
Ano můžeme.

305
00:13:03,982 --> 00:13:04,690
Pokud se bezpečně existuje.

306
00:13:04,690 --> 00:13:06,660
Můžeme jít tam.

307
00:13:06,660 --> 00:13:08,440
>> Nyní, další místo, musíme jít, je 6.

308
00:13:08,440 --> 00:13:10,557
Má cesta 6 existovat dál?

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

310
00:13:11,140 --> 00:13:12,690
Můžeme jít po cestě 6.

311
00:13:12,690 --> 00:13:13,905
A my jsme se sem.

312
00:13:13,905 --> 00:13:16,130
>> Můžeme jít dolů 3 cesty z tady?

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

314
00:13:18,450 --> 00:13:20,790
A můžeme dostat na 6 cestě odsud?

315
00:13:20,790 --> 00:13:21,982
Ano můžeme.

316
00:13:21,982 --> 00:13:24,002
>> Ještě jsme se úplně odpověděl
otázka dosud.

317
00:13:24,002 --> 00:13:25,710
Je tu ještě jeden
krok, který je nyní

318
00:13:25,710 --> 00:13:28,520
musíme se podívat dolů a
zjistit, jestli je to actually--

319
00:13:28,520 --> 00:13:32,660
pokud hledáme Harvardu, je to, že
Co jsme zjistili, když jsme vyčerpat klíč?

320
00:13:32,660 --> 00:13:35,430
V příkladu jsme pomocí tady,
roky jsou vždy čtyři číslice.

321
00:13:35,430 --> 00:13:40,280
Ale ty by mohly být pomocí na příklad, kde
jsou ukládání slovník slov.

322
00:13:40,280 --> 00:13:44,060
>> A tak místo toho, aby 10 ukazatelů
pro mé umístění, můžete mít 26.

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

324
00:13:46,040 --> 00:13:50,350
A tam jsou některé slova jako netopýr,
který je podmnožinou dávky, například.

325
00:13:50,350 --> 00:13:53,511
A tak i když se dostanete do
konec klíče a dívat se dolů,

326
00:13:53,511 --> 00:13:55,260
nemusíte vidět, co
hledáte.

327
00:13:55,260 --> 00:13:58,500
>> Takže budete mít vždy projít
celou cestu a pak

328
00:13:58,500 --> 00:14:01,540
pokud jste byli schopni úspěšně
procházet celou cestu,

329
00:14:01,540 --> 00:14:03,440
dívat se dolů a udělat jednu finální potvrzení.

330
00:14:03,440 --> 00:14:05,120
Je to to, co jsem hledal?

331
00:14:05,120 --> 00:14:07,740
No, Podívám se dolů po spuštění
nahoře a jít 1636.

332
00:14:07,740 --> 00:14:08,240
Podívám se dolů.

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

334
00:14:09,400 --> 00:14:11,689
Takže ano, uspěl jsem.

335
00:14:11,689 --> 00:14:13,980
Co jestli to, co Hledám
není v trie, ačkoli.

336
00:14:13,980 --> 00:14:17,200
Co když jsem hledal Princeton,
která byla založena v roce 1746.

337
00:14:17,200 --> 00:14:20,875
A tak se stává 1746 můj klíč
procházet trie.

338
00:14:20,875 --> 00:14:22,040
No, začnu u kořene.

339
00:14:22,040 --> 00:14:24,760
A na prvním místě chci
se jde dolů na 1 cestu.

340
00:14:24,760 --> 00:14:25,590
Mohu to udělat?

341
00:14:25,590 --> 00:14:26,490
Ano, mohu.

342
00:14:26,490 --> 00:14:28,730
>> Můžu jít po cestě od 7 tam?

343
00:14:28,730 --> 00:14:29,230
Jo, můžu.

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

345
00:14:30,750 --> 00:14:32,460
Ale můžu jít dolů 4 cesty odsud?

346
00:14:32,460 --> 00:14:35,550
To je jako ptát na otázku, může
Mám postupovat dolů, že malý čtverec

347
00:14:35,550 --> 00:14:37,114
že jsem zvýrazněny žlutě?

348
00:14:37,114 --> 00:14:38,030
Nic tam není.

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

350
00:14:38,610 --> 00:14:41,310
>> Neexistuje způsob, jak vpřed dolů 4 cestě.

351
00:14:41,310 --> 00:14:46,480
Pokud Princeton bylo v této trie, že 4
by byly vymazány už pro nás.

352
00:14:46,480 --> 00:14:49,130
A tak v tomto bodě
dosáhli jsme do slepé uličky.

353
00:14:49,130 --> 00:14:50,250
Nemůžeme jít dále.

354
00:14:50,250 --> 00:14:53,440
A tak můžeme říci, definitivně, 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 co to všechno znamená?

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

358
00:14:59,360 --> 00:15:01,000
Je tu spousta děje.

359
00:15:01,000 --> 00:15:02,500
Je tu ukazatele po celém místě.

360
00:15:02,500 --> 00:15:04,249
A jak můžete vidět,
Jen z diagramu,

361
00:15:04,249 --> 00:15:07,010
je tu spousta z uzlů, které
jsou druh létání okolo.

362
00:15:07,010 --> 00:15:13,480
Povšimněme si ale pokaždé, když jsme chtěli
ověřit, zda se něco v trie,

363
00:15:13,480 --> 00:15:15,000
jsme měli jen, aby 4 tahy.

364
00:15:15,000 --> 00:15:17,208
>> Pokaždé, když jsme chtěli
vložit něco v trie,

365
00:15:17,208 --> 00:15:20,440
musíme 4 pohyby, případně
mallocing nějaké věci podél cesty.

366
00:15:20,440 --> 00:15:23,482
Ale jak jsme viděli, když jsme vložena
Dartmouth do trie,

367
00:15:23,482 --> 00:15:25,940
někdy některé z cesty
již může být zrušeno pro nás.

368
00:15:25,940 --> 00:15:30,520
A tak jako naše Trie dostane větší a
větší, musíme dělat méně práce pokaždé,

369
00:15:30,520 --> 00:15:32,270
vložit nové věci
protože jsme už

370
00:15:32,270 --> 00:15:35,746
postavený hodně meziproduktu
větve podél cesty.

371
00:15:35,746 --> 00:15:38,370
Pokud budeme jen někdy se podívat na
4 věci, 4 je jen konstantní.

372
00:15:38,370 --> 00:15:41,750
Opravdu jsme se trochu blíží
konstantní vložení čas

373
00:15:41,750 --> 00:15:44,501
a konstantní čas vyhledávání.

374
00:15:44,501 --> 00:15:47,500
Kompromis, samozřejmě, je, že
Trie to, jak si asi říct,

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 uzlů
zabírá hodně místa.

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

378
00:15:52,090 --> 00:15:55,260
Chceme-li opravdu rychle
vložení, opravdu rychlý vymazání,

379
00:15:55,260 --> 00:15:59,630
a opravdu rychle vyhledávání, musíme
mají velké množství dat létající kolem.

380
00:15:59,630 --> 00:16:03,590
Musíme vyčlenit hodně prostoru
a paměť pro tuto strukturu dat

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

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

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

384
00:16:07,310 --> 00:16:09,560
Mohli jsme zjistili, že
svatý grál datových struktur

385
00:16:09,560 --> 00:16:12,264
s rychlým zavedením,
smazání a vyhledávání.

386
00:16:12,264 --> 00:16:14,430
A možná to bude
vhodné datové struktury

387
00:16:14,430 --> 00:16:18,890
použít pro jakékoliv informace,
snažíme se obchodu.

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

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