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

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Deci, am fost mai aproape tarasc
și mai aproape ca Sfântul Graal de date

4
00:00:08,550 --> 00:00:13,050
structuri, una care putem insera
în, ștergeți din, și privi în sus

5
00:00:13,050 --> 00:00:15,440
în timp constant.

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

7
00:00:16,270 --> 00:00:17,280
Asta e un fel de gol.

8
00:00:17,280 --> 00:00:19,720
Vrem să fie capabil să facă
lucruri foarte, foarte repede.

9
00:00:19,720 --> 00:00:22,580
>> Au am găsit aici când
vorbim despre încercări?

10
00:00:22,580 --> 00:00:23,670
Ei bine, haideți să aruncăm o privire.

11
00:00:23,670 --> 00:00:25,628
Așa că am văzut de mai multe
diferite structuri de date

12
00:00:25,628 --> 00:00:28,680
că se ocupe cartografierea
așa-numita perechi cheie-valoare,

13
00:00:28,680 --> 00:00:32,080
cartografiere unele bucată de date
la un alt bucată de date

14
00:00:32,080 --> 00:00:36,020
așa că știu unde să găsească
Informații în structura.

15
00:00:36,020 --> 00:00:40,060
>> Deci pentru matrice, de exemplu,
cheie este indicele sau matrice element de

16
00:00:40,060 --> 00:00:42,600
Localizare 0 sau 1 matrice și așa mai departe.

17
00:00:42,600 --> 00:00:46,140
Și valoarea este datele
care există în acea locație.

18
00:00:46,140 --> 00:00:48,550
Deci, ceea ce este stocat în matrice 0?

19
00:00:48,550 --> 00:00:54,290
Ceea ce este stocat în serie 1 față de doar
0 și 1, care ar fi cheile.

20
00:00:54,290 --> 00:00:56,360
>> Cu un tabel hash este
un fel de aceeași idee.

21
00:00:56,360 --> 00:01:00,690
Cu un tabel hash, avem această hash
funcție care generează codurile hash.

22
00:01:00,690 --> 00:01:03,670
Deci, cheia este codul de distribuire a datelor.

23
00:01:03,670 --> 00:01:06,530
Și valoarea, în special
am vorbit despre înlănțuirea

24
00:01:06,530 --> 00:01:10,590
în video pe tabele de dispersie,
este că lista de date legate de

25
00:01:10,590 --> 00:01:12,550
care hashes pentru că hashCode.

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

27
00:01:14,050 --> 00:01:16,050
Ce zici de o altă abordare
această metodă, deși?

28
00:01:16,050 --> 00:01:21,000
Ce zici de o metodă în cazul în care
cheie este garantat să fie unică,

29
00:01:21,000 --> 00:01:25,410
Spre deosebire de un tabel hash, în cazul în care am putea
termina cu două bucăți de date

30
00:01:25,410 --> 00:01:27,200
având aceeași hashCode.

31
00:01:27,200 --> 00:01:30,020
Și apoi avem de a face cu
care fie sondare sau mai mult

32
00:01:30,020 --> 00:01:33,340
preferabil înlănțuirea pentru a remedia această problemă.

33
00:01:33,340 --> 00:01:37,520
>> Deci, acum putem garanta
că cheia noastră va fi unic.

34
00:01:37,520 --> 00:01:39,690
Și ce dacă valoarea noastră a fost
doar ceva la fel de ușor

35
00:01:39,690 --> 00:01:44,080
ca adevărat și fals, care ne spune dacă
sau nu că bucata de informații

36
00:01:44,080 --> 00:01:45,610
există în structura?

37
00:01:45,610 --> 00:01:48,180
Un Boolean ar putea fi la fel de simplu ca un pic.

38
00:01:48,180 --> 00:01:52,660
Realist este, probabil, un
octet mai multe sanse decat un pic.

39
00:01:52,660 --> 00:01:55,410
Dar asta e mult mai mic decât
stocarea poate un șir de 50 de caractere,

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

41
00:01:57,360 --> 00:02:02,210
>> Deci încearcă, similar cu hash tabele,
care combină rețele și lista legate,

42
00:02:02,210 --> 00:02:05,790
încearcă combina tablouri,
structuri, și indicii

43
00:02:05,790 --> 00:02:08,509
împreună pentru a stoca date în
un mod interesant care este

44
00:02:08,509 --> 00:02:11,550
destul de diferit de la
tot ce am văzut până acum.

45
00:02:11,550 --> 00:02:16,750
Acum vom folosi datele ca o foaie de parcurs
pentru a naviga această structură de date.

46
00:02:16,750 --> 00:02:18,710
Și dacă putem urmări
foaia de parcurs, dacă putem

47
00:02:18,710 --> 00:02:22,390
urmați datele din
început până la sfârșit, vom

48
00:02:22,390 --> 00:02:24,945
știu dacă faptul că datele
există în trie.

49
00:02:24,945 --> 00:02:28,310
>> Și dacă nu putem urmări pe harta
de la ceea ce înseamnă să se încheie la toate,

50
00:02:28,310 --> 00:02:30,600
datele nu pot exista.

51
00:02:30,600 --> 00:02:32,890
Din nou, tastele sunt aici
garantat să fie unic.

52
00:02:32,890 --> 00:02:36,020
Și așa mai departe, spre deosebire de un tabel hash, nu am să
au de a face cu coliziuni aici.

53
00:02:36,020 --> 00:02:39,090
Și nu există două bucăți de date
au exact aceeași foaia de parcurs

54
00:02:39,090 --> 00:02:40,530
cu excepția cazului în care datele sunt identice.

55
00:02:40,530 --> 00:02:44,580
>> Dacă vom introduce John, apoi
cautam John.

56
00:02:44,580 --> 00:02:47,430
Asta e două bucăți identice de
date, dreapta, căutăm prin.

57
00:02:47,430 --> 00:02:49,880
Dar altfel, orice
două bucăți de date sunt

58
00:02:49,880 --> 00:02:52,750
garantat de a avea foi de parcurs unice
prin această structură de date.

59
00:02:52,750 --> 00:02:56,210
Și am de gând să ia o privire la
un vizual de acest lucru în doar un moment.

60
00:02:56,210 --> 00:02:58,810
>> Vom face acest lucru prin încercarea de a
crea o nouă structură de date,

61
00:02:58,810 --> 00:03:00,564
cartografiere următoarele perechi de valori-cheie.

62
00:03:00,564 --> 00:03:03,480
În acest caz, nu mergem să utilizeze
ceva la fel de simplu ca un Boolean.

63
00:03:03,480 --> 00:03:06,200
Noi de fapt, va stoca șir.

64
00:03:06,200 --> 00:03:08,690
Și că șir va
fie numele unei universități.

65
00:03:08,690 --> 00:03:12,140
>> Și cheia va fi anul
când a fost înființată ca universitate.

66
00:03:12,140 --> 00:03:15,380
Toate ani pentru universități
vor fi de patru cifre.

67
00:03:15,380 --> 00:03:19,840
Și așa vom folosi cele patru cifre
naviga prin această structură de date.

68
00:03:19,840 --> 00:03:22,270
Și vom vedea, din nou, cum
facem asta în doar o secundă.

69
00:03:22,270 --> 00:03:25,110
>> La sfârșitul căii,
vom vedea numele

70
00:03:25,110 --> 00:03:30,250
a universității care corespunde
pentru că cheie, cele patru cifre.

71
00:03:30,250 --> 00:03:34,390
Ideea de bază din spatele unui trie
este că avem un traseu central.

72
00:03:34,390 --> 00:03:35,640
Deci, cred că despre ea ca un copac.

73
00:03:35,640 --> 00:03:39,211
Și acest lucru este similar în ortografie
și în conceptul de un copac.

74
00:03:39,211 --> 00:03:41,460
În general, atunci când ne gândim la
copaci în lumea reală,

75
00:03:41,460 --> 00:03:44,090
ei au o rădăcină care este în
sol și cresc în sus

76
00:03:44,090 --> 00:03:46,830
și au filiale
și au frunze.

77
00:03:46,830 --> 00:03:49,450
Și practic ideea de
un trie este exact la fel,

78
00:03:49,450 --> 00:03:51,755
cu excepția faptului că rădăcină este ancorat
undeva în cer.

79
00:03:51,755 --> 00:03:53,130
Și frunzele sunt în partea de jos.

80
00:03:53,130 --> 00:03:55,750
>> Deci e un fel de a lua un copac
și doar flipping cu susul în jos.

81
00:03:55,750 --> 00:03:56,880
Dar există încă ramuri.

82
00:03:56,880 --> 00:03:59,463
Iar cei ar fi cai noastre,
acestea vor fi conexiunile noastre

83
00:03:59,463 --> 00:04:02,220
de la rădăcină la frunze.

84
00:04:02,220 --> 00:04:04,200
In acest caz, cei
căi, aceste ramuri

85
00:04:04,200 --> 00:04:08,490
sunt marcate cu cifre care ne spun
care mod de a merge, de unde suntem.

86
00:04:08,490 --> 00:04:11,800
>> Dacă vom vedea o 0, vom merge în jos această ramură,
dacă vom vedea un 1, vom merge în jos această ramură,

87
00:04:11,800 --> 00:04:12,900
și așa și așa mai departe.

88
00:04:12,900 --> 00:04:14,060
Ei bine, ce înseamnă asta?

89
00:04:14,060 --> 00:04:16,519
Ei bine, asta înseamnă că
la fiecare punct de joncțiune

90
00:04:16,519 --> 00:04:19,260
și fiecare nod din
mijloc și fiecare ramură,

91
00:04:19,260 --> 00:04:23,020
există 10 posibile
locuri pe care putem merge.

92
00:04:23,020 --> 00:04:27,690
Deci, există 10 indicii
din orice locație.

93
00:04:27,690 --> 00:04:30,610
>> Și acest lucru este în cazul în care încearcă să obține un
pic intimidant pentru cineva

94
00:04:30,610 --> 00:04:34,460
care e nu are o mulțime de
experiență în informatică înainte.

95
00:04:34,460 --> 00:04:35,960
Dar încearcă sunt într-adevăr destul de minunat.

96
00:04:35,960 --> 00:04:37,793
Și dacă aveți
sansa de a lucra cu ei

97
00:04:37,793 --> 00:04:40,420
și sunteți dispus să sape în
și experimenta cu ei,

98
00:04:40,420 --> 00:04:44,234
sunt foarte destul de interesant
structuri de date pentru a lucra cu.

99
00:04:44,234 --> 00:04:46,900
Dacă vrem să inserați un element
în trie, tot ce trebuie să facem

100
00:04:46,900 --> 00:04:51,360
este construit calea corectă
de la rădăcină până la frunza.

101
00:04:51,360 --> 00:04:55,390
Iată ce fiecare pas de-a lungul
modul ar putea arata ca.

102
00:04:55,390 --> 00:04:59,660
Vom defini o nouă date
structură pentru un nou nod numit trie.

103
00:04:59,660 --> 00:05:02,560
>> Și în interiorul acestor date
Structura există două piese.

104
00:05:02,560 --> 00:05:05,460
Vom magazin
Numele o universitate.

105
00:05:05,460 --> 00:05:09,410
Și am de gând să stoca
o serie de indicii

106
00:05:09,410 --> 00:05:12,190
la alte noduri de același tip.

107
00:05:12,190 --> 00:05:14,780
Deci, din nou, aceasta este ca un fel
conceptului de pretutindeni

108
00:05:14,780 --> 00:05:18,567
suntem, la 10 mai
locuri putem merge.

109
00:05:18,567 --> 00:05:20,150
Dacă vom vedea o 0, vom merge în jos această ramură.

110
00:05:20,150 --> 00:05:22,690
Dacă vom vedea o 1, această ramură,
și așa mai departe și așa mai departe și așa mai departe.

111
00:05:22,690 --> 00:05:25,160
Dacă spunem 9, vom merge în jos această ramură.

112
00:05:25,160 --> 00:05:28,220
Deci, la fiecare punct de joncțiune,
putem merge 10 locuri posibile.

113
00:05:28,220 --> 00:05:35,740
Astfel încât fiecare nod trebuie sa contina 10 indicii
la alte noduri, la alte 10 noduri.

114
00:05:35,740 --> 00:05:39,810
>> Iar datele suntem stocare este
doar numele universității.

115
00:05:39,810 --> 00:05:41,060
Deci, haideți să construim un trie.

116
00:05:41,060 --> 00:05:44,860
Să introduceți un cuplu
de articole în trie nostru.

117
00:05:44,860 --> 00:05:46,740
Deci, la foarte de sus,
acest lucru este nod rădăcină nostru.

118
00:05:46,740 --> 00:05:49,740
Acest lucru este, probabil, va fi ceva
ai de gând să nivel global declara.

119
00:05:49,740 --> 00:05:53,450
Și ai de gând să mențină nivel global
un pointer la acest nod întotdeauna.

120
00:05:53,450 --> 00:05:55,360
>> Ai de gând să spun,
rădăcină este egal, și tu ești

121
00:05:55,360 --> 00:05:57,580
O să vă malloc nod trie.

122
00:05:57,580 --> 00:05:59,850
Și niciodată nu vei
pentru a atinge din nou rădăcină.

123
00:05:59,850 --> 00:06:02,300
De fiecare dată când doriți să
începe navigarea prin,

124
00:06:02,300 --> 00:06:05,802
setați un alt pointer
egal cu radacina, cum ar fi trav,

125
00:06:05,802 --> 00:06:07,760
care este exemplul I
folosi în multe dintre videoclipurile mele

126
00:06:07,760 --> 00:06:11,090
aici, pe stive și cozi
și liste de link-ul și așa mai departe.

127
00:06:11,090 --> 00:06:13,320
>> Puteți seta un alt pointer
numit trav pentru traversarea.

128
00:06:13,320 --> 00:06:15,890
Și utilizați pentru a naviga trav
prin structura de date.

129
00:06:15,890 --> 00:06:17,500
Deci, hai sa vedem cum acest lucru ar putea arata.

130
00:06:17,500 --> 00:06:19,880
Deci, chiar acum, ceea ce
nu un nod arata ca?

131
00:06:19,880 --> 00:06:22,920
Ei bine, la fel ca datele noastre
declarație structura indicat,

132
00:06:22,920 --> 00:06:26,906
avem un șir de caractere, care
în acest caz este gol.

133
00:06:26,906 --> 00:06:27,780
Nu e nimic aici.

134
00:06:27,780 --> 00:06:29,550
>> Și o serie de 10 indicatori.

135
00:06:29,550 --> 00:06:31,790
Iar acum, noi doar
au un nod în acest trie.

136
00:06:31,790 --> 00:06:33,110
Nu e nimic altceva în ea.

137
00:06:33,110 --> 00:06:36,020
Deci, toate cele 10 de cei
indicii de puncte la null.

138
00:06:36,020 --> 00:06:38,090
Asta e ceea ce indică roșu.

139
00:06:38,090 --> 00:06:39,500
>> Să introduceți șirul Harvard.

140
00:06:39,500 --> 00:06:41,999
Să se introduce la Universitatea din
Harvard în această trie, care

141
00:06:41,999 --> 00:06:43,940
a fost fondată în anul 1636.

142
00:06:43,940 --> 00:06:48,220
Vrem să utilizați tasta,
1,636, să ne spună unde suntem

143
00:06:48,220 --> 00:06:50,140
va pentru a stoca Harvard în trie.

144
00:06:50,140 --> 00:06:51,470
Acum, cum pot să facem asta?

145
00:06:51,470 --> 00:06:52,886
>> S-ar putea arata ceva de genul asta.

146
00:06:52,886 --> 00:06:54,160
Începem de la rădăcină.

147
00:06:54,160 --> 00:06:56,920
Și avem aceste 10 locuri se poate merge.

148
00:06:56,920 --> 00:06:59,900
Rădăcina este la fel ca orice
alt nod din trie.

149
00:06:59,900 --> 00:07:02,850
Există 10 locuri putem merge de aici.

150
00:07:02,850 --> 00:07:07,215
>> În cazul în care face, probabil, ne-o dorim
pentru a merge în cazul în care cheia este 1,636?

151
00:07:07,215 --> 00:07:08,340
Există într-adevăr două opțiuni.

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

153
00:07:08,450 --> 00:07:10,825
Putem construi cheia din
la dreapta la stânga și să înceapă cu 6.

154
00:07:10,825 --> 00:07:14,000
Sau am putea construi cheia de la
la stânga la dreapta și să înceapă cu un.

155
00:07:14,000 --> 00:07:16,140
>> Este, probabil, mai
intuitiv ca o ființă umană

156
00:07:16,140 --> 00:07:18,110
să înțelegem vom
Doar du-te la stânga la dreapta.

157
00:07:18,110 --> 00:07:21,140
Și așa, dacă vreau să introduceți
Harvard în această trie,

158
00:07:21,140 --> 00:07:23,560
Probabil că vreau să încep
pornind de la rădăcină,

159
00:07:23,560 --> 00:07:25,720
uita la mele 10 opțiuni
în fața mea, și spunând

160
00:07:25,720 --> 00:07:28,700
Vreau să merg pe calea 1.

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

162
00:07:29,700 --> 00:07:31,810
>> Acum, o cale este în prezent nulă.

163
00:07:31,810 --> 00:07:35,920
Deci, dacă vreau să procedeze în jos această cale
pentru a introduce acest element în trie,

164
00:07:35,920 --> 00:07:42,040
Trebuie să malloc un nou nod, au 1
punct acolo, și atunci eu sunt bine să plec.

165
00:07:42,040 --> 00:07:46,460
>> Deci, eu de fapt sunt la o
punct în care stau

166
00:07:46,460 --> 00:07:50,270
la rădăcina copacul sau
trie și există 10 de sucursale.

167
00:07:50,270 --> 00:07:52,260
Dar fiecare ramură are un
poarta în fața lui.

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

169
00:07:53,060 --> 00:07:54,850
Pentru că nu e nimic altceva nu e.

170
00:07:54,850 --> 00:07:56,522
Nici un pasaj în condiții de siguranță.

171
00:07:56,522 --> 00:07:58,980
Asta înseamnă că nu e nimic
jos oricare dintre aceste ramuri.

172
00:07:58,980 --> 00:08:02,532
Dacă vreau pentru a începe construirea
ceva, vreau să eliminați poarta.

173
00:08:02,532 --> 00:08:04,490
Vreau să eliminați poarta
în fața numărului 1.

174
00:08:04,490 --> 00:08:05,698
Și vreau să merg pe asta.

175
00:08:05,698 --> 00:08:08,060
Și vreau să construiască
un alt loc pentru mine să merg.

176
00:08:08,060 --> 00:08:09,470
>> Și asta e ceea ce am făcut aici.

177
00:08:09,470 --> 00:08:11,430
Deci 1 nu mai arată la null.

178
00:08:11,430 --> 00:08:13,830
Am spus că se află în condiții de siguranță să meargă în jos aici, acum.

179
00:08:13,830 --> 00:08:15,789
Am construit un alt nod.

180
00:08:15,789 --> 00:08:18,330
Și când ajung la acel nod, am
o altă decizie de a face.

181
00:08:18,330 --> 00:08:20,890
În cazul în care am de gând să merg de aici?

182
00:08:20,890 --> 00:08:22,700
>> Ei bine, am plecat deja pe 1.

183
00:08:22,700 --> 00:08:24,470
Deci, acum, probabil, vreau să merg în jos 6.

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

185
00:08:24,970 --> 00:08:27,100
Din nou, am 10 de locații pot alege.

186
00:08:27,100 --> 00:08:30,060
Deci, hai sa mergem acum pe numărul 6.

187
00:08:30,060 --> 00:08:32,280
Așa că am clar poarta
în fața numărului 6.

188
00:08:32,280 --> 00:08:33,250
Și am mers acolo.

189
00:08:33,250 --> 00:08:34,580
Și am construi un alt nod.

190
00:08:34,580 --> 00:08:37,630
Și am ajuns la un alt punct de joncțiune.

191
00:08:37,630 --> 00:08:40,289
>> Din nou, am 10 variante
pentru cazul în care pot merge.

192
00:08:40,289 --> 00:08:42,799
Am trecut la 1 la 6.

193
00:08:42,799 --> 00:08:44,215
Deci, acum, probabil, eu vreau să merg la 3.

194
00:08:44,215 --> 00:08:45,381
3, nu e nicăieri pot merge.

195
00:08:45,381 --> 00:08:48,980
Așa că am să clar modul
și cu mine construi un nou spațiu.

196
00:08:48,980 --> 00:08:50,870
Și apoi de la 3, în cazul în care vreau să merg?

197
00:08:50,870 --> 00:08:52,450
Vreau să merg în jos 6.

198
00:08:52,450 --> 00:08:54,770
>> Și, din nou, a trebuit să
clar modul de a face acest lucru.

199
00:08:54,770 --> 00:08:59,179
Deci, acum am folosit cheia pentru a insera crea
noduri și începe să construiască acest trie.

200
00:08:59,179 --> 00:09:00,220
Am început de la rădăcină.

201
00:09:00,220 --> 00:09:03,666
Am coborât 1636.

202
00:09:03,666 --> 00:09:05,540
Și acum sunt în partea de jos
acolo pe acel nod.

203
00:09:05,540 --> 00:09:06,610
Și s-ar putea fi în măsură să
vedea pe ecran.

204
00:09:06,610 --> 00:09:07,735
>> Este evidențiat în galben.

205
00:09:07,735 --> 00:09:10,020
Acolo am în prezent sunt.

206
00:09:10,020 --> 00:09:11,300
Cheia se face.

207
00:09:11,300 --> 00:09:13,030
Am epuizat fiecare poziție în cheia mea.

208
00:09:13,030 --> 00:09:15,040
Deci, eu nu pot merge mai departe.

209
00:09:15,040 --> 00:09:17,720
Deci, la acest moment, tot ce am
într-adevăr trebuie să faceți este spus, OK.

210
00:09:17,720 --> 00:09:18,990
Este un fel de căutarea
în jos, la pământ,

211
00:09:18,990 --> 00:09:21,115
dacă sunteți prefigurand
te ca acest tip de drum

212
00:09:21,115 --> 00:09:22,350
cu diferite conexiuni.

213
00:09:22,350 --> 00:09:25,800
Un fel de a privi în jos și un fel de
spray-pictura Harvard pe teren.

214
00:09:25,800 --> 00:09:26,800
Acesta este numele acestui.

215
00:09:26,800 --> 00:09:28,300
Știu că e ceea ce e în această locație.

216
00:09:28,300 --> 00:09:31,870
Dacă începem de la rădăcină și vom merge în jos
1 și apoi 6 și apoi 3 și apoi 6,

217
00:09:31,870 --> 00:09:32,780
unde suntem?

218
00:09:32,780 --> 00:09:35,640
Ei bine, dacă ne uităm în jos
si vom vedea la Harvard, apoi

219
00:09:35,640 --> 00:09:38,960
știm că a fost la Harvard
fondată în 1636 pe baza drum

220
00:09:38,960 --> 00:09:41,400
suntem de punere în aplicare această structură de date.

221
00:09:41,400 --> 00:09:43,177
Deci asta a fost, sperăm simplu.

222
00:09:43,177 --> 00:09:44,760
Vom face mai multe inserții două.

223
00:09:44,760 --> 00:09:50,060
Și sperăm că-l vom ajuta să
aceasta face de două ori mai mult.

224
00:09:50,060 --> 00:09:52,210
>> Acum, haideți să introduceți o altă universitate.

225
00:09:52,210 --> 00:09:54,630
Să introduceți Yale în această trie.

226
00:09:54,630 --> 00:09:57,037
Yale a fost fondată în 1701.

227
00:09:57,037 --> 00:09:58,870
Deci, vom începe de la
rădăcină, așa cum facem mereu.

228
00:09:58,870 --> 00:09:59,890
Și am stabilit un pointer traversarea.

229
00:09:59,890 --> 00:10:01,624
Vom folosi pentru a vă deplasa prin.

230
00:10:01,624 --> 00:10:03,790
Primul lucru pe care vrem să
faceți este să mergeți pe calea 1.

231
00:10:03,790 --> 00:10:05,830
Asta e prima cifră de cheie noastre.

232
00:10:05,830 --> 00:10:08,420
Din fericire, însă, noi nu
trebuie să faci nici o lucrare de această dată.

233
00:10:08,420 --> 00:10:09,919
1 Calea a fost deja eliminate.

234
00:10:09,919 --> 00:10:13,520
Am șters anterior, atunci când o am
a fost introducerea Harvard la 1636.

235
00:10:13,520 --> 00:10:18,090
Deci, eu pot deplasa în siguranță
jos 1 și du-te acolo.

236
00:10:18,090 --> 00:10:20,150
Dacă se poate deplasa în jos, 1.

237
00:10:20,150 --> 00:10:22,930
>> Acum, însă, vreau să merg la 7.

238
00:10:22,930 --> 00:10:24,280
Am deschis calea la 6.

239
00:10:24,280 --> 00:10:27,050
Știu că pot în condiții de siguranță
continua pe 6 calea.

240
00:10:27,050 --> 00:10:29,220
Dar am nevoie pentru a trece de pe 7 calea.

241
00:10:29,220 --> 00:10:30,580
Deci, ce trebuie să fac?

242
00:10:30,580 --> 00:10:35,070
Ei bine, la fel ca înainte, am doar nevoie de
pentru a șterge poarta, ieși din drum,

243
00:10:35,070 --> 00:10:38,740
și de a construi o nouă nod de 7 cale.

244
00:10:38,740 --> 00:10:40,250
La fel ca aceasta.

245
00:10:40,250 --> 00:10:42,930
>> Deci, acum am mutat 1 și apoi 7.

246
00:10:42,930 --> 00:10:45,550
Și acum observați, sunt un fel
de pe acest nou subbranch.

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

248
00:10:46,050 --> 00:10:49,260
Orice altceva de la 16
pe, nu-mi pasă.

249
00:10:49,260 --> 00:10:50,720
Nu fac nimic 16.

250
00:10:50,720 --> 00:10:51,750
Fac 17 lucruri.

251
00:10:51,750 --> 00:10:58,380
>> Deci, acum la 17, am să
un fel de vâlvătaie trasee noi aici.

252
00:10:58,380 --> 00:11:00,462
Următoarea cifră cheia este 0.

253
00:11:00,462 --> 00:11:01,670
Eu în mod clar nu pot ajunge oriunde.

254
00:11:01,670 --> 00:11:02,628
Am construit acest nod.

255
00:11:02,628 --> 00:11:04,550
Așa că știu nu există nici
căi forward de aici.

256
00:11:04,550 --> 00:11:06,370
Așa că am să fac eu unul.

257
00:11:06,370 --> 00:11:09,360
>> Așa că am malloc un nou nod
și au 0 puncte acolo.

258
00:11:09,360 --> 00:11:12,770
Și apoi încă o dată, am o malloc
nod nou si au un punct de acolo.

259
00:11:12,770 --> 00:11:15,870
Din nou, mi-am epuizat cheia, 1701.

260
00:11:15,870 --> 00:11:18,472
Așa că am uita în jos și am spray cu vopsea Yale.

261
00:11:18,472 --> 00:11:19,680
Acesta este numele acestui nod.

262
00:11:19,680 --> 00:11:24,660
>> Și așa acum, dacă am nevoie pentru a vedea dacă Yale
este în acest trie, am începe de la rădăcină,

263
00:11:24,660 --> 00:11:27,060
Mă duc în jos 1701, și privi în jos.

264
00:11:27,060 --> 00:11:30,030
Și dacă văd pulverizare Yale
pictat pe pământ, apoi

265
00:11:30,030 --> 00:11:32,200
Știu Yale există în acest trie.

266
00:11:32,200 --> 00:11:32,950
Hai să facem unul mai mult.

267
00:11:32,950 --> 00:11:36,430
Să introduceți Dartmouth în această
trie, care a fost fondată în 1769.

268
00:11:36,430 --> 00:11:37,750
>> Start la rădăcină din nou.

269
00:11:37,750 --> 00:11:39,445
Prima mea cifră de cheia este de 1.

270
00:11:39,445 --> 00:11:40,820
Mă pot mișca în siguranță pe această cale.

271
00:11:40,820 --> 00:11:42,400
Care există deja.

272
00:11:42,400 --> 00:11:44,040
Următoarea cifră de cheia este 7.

273
00:11:44,040 --> 00:11:45,890
Mă pot mișca în siguranță pe această cale.

274
00:11:45,890 --> 00:11:47,540
El există, de asemenea.

275
00:11:47,540 --> 00:11:49,000
>> Urmatorul meu este de 6.

276
00:11:49,000 --> 00:11:52,860
De aici, de unde am în prezent sunt
în galben acolo, în acel nod de mijloc,

277
00:11:52,860 --> 00:11:56,060
6 este în prezent blocat de pe.

278
00:11:56,060 --> 00:11:58,830
Dacă vreau să merg în jos această cale,
Trebuie să-l construiască singur.

279
00:11:58,830 --> 00:12:02,250
Așa că voi malloc un nou nod
și au 6 punctul acolo.

280
00:12:02,250 --> 00:12:04,250
Și apoi, din nou, eu sunt
aprins noi trasee aici.

281
00:12:04,250 --> 00:12:10,750
>> Așa că am malloc un nou nod, astfel încât de la
acest număr cale node-- 9-- și apoi acum

282
00:12:10,750 --> 00:12:13,584
dacă am de călătorie 1,769, și mă uit în jos.

283
00:12:13,584 --> 00:12:15,500
Nu e nimic în prezent
pulverizare pictat acolo.

284
00:12:15,500 --> 00:12:16,930
Pot să scriu Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Și am introdus
Dartmouth în trie.

286
00:12:20,710 --> 00:12:23,450
>> Așa că e inserarea
lucrurile în trie.

287
00:12:23,450 --> 00:12:25,384
Acum vrem pentru a căuta lucruri.

288
00:12:25,384 --> 00:12:27,050
Cum căutăm lucruri în trie?

289
00:12:27,050 --> 00:12:29,170
Ei bine, e destul de mult aceeași idee.

290
00:12:29,170 --> 00:12:33,620
Acum vom folosi doar cifrele cheie
pentru a vedea dacă putem naviga de la rădăcină

291
00:12:33,620 --> 00:12:37,170
unde vrem să mergem în trie.

292
00:12:37,170 --> 00:12:41,620
>> Dacă am lovit-o fundătură în orice moment, atunci
știm că nu se poate că există elemente

293
00:12:41,620 --> 00:12:44,500
sau altceva care ar fi calea
au fost deja eliminate.

294
00:12:44,500 --> 00:12:45,930
Dacă vom face tot drumul până la
cele din urmă, tot ce trebuie să facem

295
00:12:45,930 --> 00:12:48,471
este uita în jos și a vedea dacă acesta este
elementul căutăm.

296
00:12:48,471 --> 00:12:49,335
Dacă este, succesul.

297
00:12:49,335 --> 00:12:52,610
În cazul în care nu e, nu.

298
00:12:52,610 --> 00:12:54,940
>> Deci, haideți să căuta
Harvard în această trie.

299
00:12:54,940 --> 00:12:56,020
Începem de la rădăcină.

300
00:12:56,020 --> 00:12:58,228
Și, din nou, vom
a crea un pointer de traversare

301
00:12:58,228 --> 00:12:59,390
de a face miscari noastre pentru noi.

302
00:12:59,390 --> 00:13:02,080
Din rădăcina știm că
primul loc avem nevoie pentru a merge este de 1,

303
00:13:02,080 --> 00:13:03,390
putem face asta?

304
00:13:03,390 --> 00:13:03,982
Da putem.

305
00:13:03,982 --> 00:13:04,690
Dacă există condiții de siguranță.

306
00:13:04,690 --> 00:13:06,660
Putem merge acolo.

307
00:13:06,660 --> 00:13:08,440
>> Acum, următorul loc avem nevoie pentru a merge este de 6.

308
00:13:08,440 --> 00:13:10,557
Are 6 calea exista de aici?

309
00:13:10,557 --> 00:13:11,140
Da, așa e.

310
00:13:11,140 --> 00:13:12,690
Putem merge pe calea 6.

311
00:13:12,690 --> 00:13:13,905
Și am ajuns aici.

312
00:13:13,905 --> 00:13:16,130
>> Putem merge pe calea 3 de aici?

313
00:13:16,130 --> 00:13:18,450
Ei bine, se pare că,
da, care există de asemenea.

314
00:13:18,450 --> 00:13:20,790
Și putem ajunge pe 6 calea de aici?

315
00:13:20,790 --> 00:13:21,982
Da putem.

316
00:13:21,982 --> 00:13:24,002
>> Noi nu am destul de răspuns
întrebarea încă.

317
00:13:24,002 --> 00:13:25,710
Există încă o mai
pas, care este acum

318
00:13:25,710 --> 00:13:28,520
avem nevoie să se uite în jos și
vedea dacă e actually--

319
00:13:28,520 --> 00:13:32,660
dacă suntem în căutarea pentru Harvard, este că
ceea ce vom găsi după ce epuizează cheia?

320
00:13:32,660 --> 00:13:35,430
În exemplul folosim aici,
anii sunt întotdeauna patru cifre.

321
00:13:35,430 --> 00:13:40,280
Dar s-ar putea să fie folosind exemplul în care
sunteți stocarea unui dicționar de cuvinte.

322
00:13:40,280 --> 00:13:44,060
>> Și astfel încât în ​​loc de a avea 10 indicii
pentru locația mea, s-ar putea avea 26.

323
00:13:44,060 --> 00:13:46,040
Unul pentru fiecare literă a alfabetului.

324
00:13:46,040 --> 00:13:50,350
Și există unele cuvinte, cum ar fi BAT,
care este un subset al lotului, de exemplu.

325
00:13:50,350 --> 00:13:53,511
Și astfel, chiar dacă tu a lua la
sfârșitul cheia și te uiți în jos,

326
00:13:53,511 --> 00:13:55,260
s-ar putea să nu vezi ce
sunteți în căutarea pentru.

327
00:13:55,260 --> 00:13:58,500
>> Deci, va trebui întotdeauna să traverseze
întreaga cale și apoi

328
00:13:58,500 --> 00:14:01,540
dacă ai fost capabil succes
pentru a traversa întreaga cale,

329
00:14:01,540 --> 00:14:03,440
privi în jos și de a face o confirmare finală.

330
00:14:03,440 --> 00:14:05,120
Asta caut?

331
00:14:05,120 --> 00:14:07,740
Ei bine, m-am uita în jos după începerea
în partea de sus și merge 1,636.

332
00:14:07,740 --> 00:14:08,240
Mă uit în jos.

333
00:14:08,240 --> 00:14:09,400
Văd Harvard.

334
00:14:09,400 --> 00:14:11,689
Deci, da, am reușit.

335
00:14:11,689 --> 00:14:13,980
Ce se întâmplă dacă ceea ce caut
nu este în trie, totuși.

336
00:14:13,980 --> 00:14:17,200
Ce se întâmplă dacă caut Princeton,
care a fost fondată în 1746.

337
00:14:17,200 --> 00:14:20,875
Și astfel 1,746 devine cheia mea
pentru a naviga prin trie.

338
00:14:20,875 --> 00:14:22,040
Ei bine, eu încep de la rădăcină.

339
00:14:22,040 --> 00:14:24,760
Și primul loc vreau
a se duce în jos 1 calea.

340
00:14:24,760 --> 00:14:25,590
Pot să o fac?

341
00:14:25,590 --> 00:14:26,490
Da, eu pot.

342
00:14:26,490 --> 00:14:28,730
>> Pot să mă duc pe calea 7 de acolo?

343
00:14:28,730 --> 00:14:29,230
Da, pot.

344
00:14:29,230 --> 00:14:30,750
Care există prea.

345
00:14:30,750 --> 00:14:32,460
Dar pot merge pe calea 4 de aici?

346
00:14:32,460 --> 00:14:35,550
E ca și cum pune întrebarea, poate
Am continua pe aia pătrat

347
00:14:35,550 --> 00:14:37,114
care l-am evidențiat în galben?

348
00:14:37,114 --> 00:14:38,030
Nu e nimic acolo.

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

350
00:14:38,610 --> 00:14:41,310
>> Nu există nici o cale de urmat pe calea 4.

351
00:14:41,310 --> 00:14:46,480
Dacă Princeton a fost în acest trie, că 4
ar fi fost eliminate deja pentru noi.

352
00:14:46,480 --> 00:14:49,130
Și astfel, în acest moment
am ajuns într-o fundătură.

353
00:14:49,130 --> 00:14:50,250
Nu putem merge mai departe.

354
00:14:50,250 --> 00:14:53,440
Și astfel putem spune, definitiv, nr.

355
00:14:53,440 --> 00:14:56,760
Princeton nu există în acest trie.

356
00:14:56,760 --> 00:14:58,860
>> Deci, ce inseamna toate acestea?

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

358
00:14:59,360 --> 00:15:01,000
Există o mulțime întâmplă aici.

359
00:15:01,000 --> 00:15:02,500
Există indicii peste tot.

360
00:15:02,500 --> 00:15:04,249
Și, după cum puteți vedea
doar din diagrama,

361
00:15:04,249 --> 00:15:07,010
există o mulțime de noduri care
sunt un fel de zbor în jurul.

362
00:15:07,010 --> 00:15:13,480
Dar observați de fiecare dată când am vrut să
verifică dacă ceva a fost în trie,

363
00:15:13,480 --> 00:15:15,000
am avut doar pentru a face 4 mutări.

364
00:15:15,000 --> 00:15:17,208
>> De fiecare dată când am vrut să
introduceți ceva în trie,

365
00:15:17,208 --> 00:15:20,440
avem de a face 4 mutări, eventual
mallocing unele lucruri de-a lungul drum.

366
00:15:20,440 --> 00:15:23,482
Dar, așa cum am văzut când am introdus
Dartmouth în trie,

367
00:15:23,482 --> 00:15:25,940
uneori o parte din calea
ar putea fi deja eliminate pentru noi.

368
00:15:25,940 --> 00:15:30,520
Și astfel ca trie nostru devine mai mare și
mai mare, ne-am făcut mai puțin de lucru de fiecare dată

369
00:15:30,520 --> 00:15:32,270
pentru a introduce lucruri noi
pentru că ne-am deja

370
00:15:32,270 --> 00:15:35,746
a construit o mulțime de intermediar
ramuri de-a lungul drum.

371
00:15:35,746 --> 00:15:38,370
Dacă avem doar vreodată să se uite la
4 lucruri, 4 este doar o constantă.

372
00:15:38,370 --> 00:15:41,750
Suntem intr-adevar sunt un fel de abordare
inserție timp constant

373
00:15:41,750 --> 00:15:44,501
și de căutare constantă de timp.

374
00:15:44,501 --> 00:15:47,500
Compromisul, desigur, fiind că
acest trie, după cum puteți, probabil, spune,

375
00:15:47,500 --> 00:15:49,030
este imens.

376
00:15:49,030 --> 00:15:51,040
Fiecare dintre aceste noduri
ocupă o mulțime de spațiu.

377
00:15:51,040 --> 00:15:52,090
>> Dar asta e compromisul.

378
00:15:52,090 --> 00:15:55,260
Dacă vrem cu adevărat rapid
inserție, ștergere foarte repede,

379
00:15:55,260 --> 00:15:59,630
și de căutare foarte rapid, trebuie să ne
au o mulțime de date de zbor în jurul.

380
00:15:59,630 --> 00:16:03,590
Trebuie să pună deoparte o mulțime de spațiu
și memorie pentru ca structura de date

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

382
00:16:04,290 --> 00:16:05,415
>> Și așa că e compromisul.

383
00:16:05,415 --> 00:16:07,310
Dar se pare ca ne-am
s-ar putea l-au găsit.

384
00:16:07,310 --> 00:16:09,560
S-ar putea au descoperit ca
Sfântul Graal al structurilor de date

385
00:16:09,560 --> 00:16:12,264
cu inserție rapidă,
ștergerea, și de căutare.

386
00:16:12,264 --> 00:16:14,430
Și poate acest lucru va fi un
structură de date corespunzătoare

387
00:16:14,430 --> 00:16:18,890
de a utiliza pentru orice informații
încercăm să magazin.

388
00:16:18,890 --> 00:16:21,860
Sunt Doug Lloyd, aceasta este CS50.

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