1
00:00:00,000 --> 00:00:02,994
>> [REPRODUCCIÓ DE MÚSICA]

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Així que hem estat cada vegada més a prop
i més a prop que el sant grial de les dades

4
00:00:08,550 --> 00:00:13,050
estructures, un que podem inserir
en, eliminar de, i mirar cap amunt

5
00:00:13,050 --> 00:00:15,440
en temps constant.

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

7
00:00:16,270 --> 00:00:17,280
En certa manera és la meta.

8
00:00:17,280 --> 00:00:19,720
Volem ser capaços de fer
coses molt, molt ràpidament.

9
00:00:19,720 --> 00:00:22,580
>> Tenim el trobem aquí quan
estem parlant d'intents?

10
00:00:22,580 --> 00:00:23,670
Bé, anem a fer una ullada.

11
00:00:23,670 --> 00:00:25,628
Així que hem vist diverses
diferents estructures de dades

12
00:00:25,628 --> 00:00:28,680
que manegen el mapeig de
els anomenats parells clau-valor,

13
00:00:28,680 --> 00:00:32,080
cartografia d'alguna peça de dades
a alguna altra peça de dades

14
00:00:32,080 --> 00:00:36,020
així que sabem on trobar
la informació en l'estructura.

15
00:00:36,020 --> 00:00:40,060
>> Així que per array, per exemple, el
clau és l'índex d'element o conjunt

16
00:00:40,060 --> 00:00:42,600
ubicació 0 o matriu 1 i així successivament.

17
00:00:42,600 --> 00:00:46,140
I el valor de les dades és
que hi ha en aquesta ubicació.

18
00:00:46,140 --> 00:00:48,550
Així que el que s'emmagatzema en l'array 0?

19
00:00:48,550 --> 00:00:54,290
El que s'emmagatzema en la matriu 1 enfront de només
0 i 1, el que seria les tecles.

20
00:00:54,290 --> 00:00:56,360
>> Amb una taula hash és
espècie de la mateixa idea.

21
00:00:56,360 --> 00:01:00,690
Amb una taula hash, tenim aquest hash
funció que genera codis hash.

22
00:01:00,690 --> 00:01:03,670
Així que la clau és el codi hash de les dades.

23
00:01:03,670 --> 00:01:06,530
I el valor, en particular
parlem d'encadenament

24
00:01:06,530 --> 00:01:10,590
en el vídeo en taules hash,
és que la llista enllaçada de dades

25
00:01:10,590 --> 00:01:12,550
que hashes a aquest codi hash.

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

27
00:01:14,050 --> 00:01:16,050
Què passa amb un altre enfocament
aquest mètode, però?

28
00:01:16,050 --> 00:01:21,000
Què passa amb un mètode en el qual el
clau es garanteix que sigui únic,

29
00:01:21,000 --> 00:01:25,410
a diferència d'una taula hash, on podíem
acabar amb dues peces de dades

30
00:01:25,410 --> 00:01:27,200
que tenen el mateix codi hash.

31
00:01:27,200 --> 00:01:30,020
I llavors hem de fer front a
que per qualsevol sondeig o més

32
00:01:30,020 --> 00:01:33,340
preferentment d'encadenament per arreglar aquest problema.

33
00:01:33,340 --> 00:01:37,520
>> Així que ara podem garantir
que la nostra clau serà únic.

34
00:01:37,520 --> 00:01:39,690
¿I si el nostre valor era
només una cosa tan fàcil

35
00:01:39,690 --> 00:01:44,080
com a veritable i fals que ens diu si
o no aquesta informació

36
00:01:44,080 --> 00:01:45,610
existeix en l'estructura?

37
00:01:45,610 --> 00:01:48,180
Booleà podria ser tan simple com una mica.

38
00:01:48,180 --> 00:01:52,660
Sent realistes és probablement una
byte més probable que una mica.

39
00:01:52,660 --> 00:01:55,410
Però això és molt menor que
emmagatzemar potser una cadena de 50 caràcters,

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

41
00:01:57,360 --> 00:02:02,210
>> Així que intenta, a hashish, taules,
que combinen les matrius i llista enllaçada,

42
00:02:02,210 --> 00:02:05,790
tries combinen matrius,
estructures i punters

43
00:02:05,790 --> 00:02:08,509
junts per emmagatzemar dades en
una forma interessant que és

44
00:02:08,509 --> 00:02:11,550
bastant diferent de
qualsevol cosa que haguem vist fins ara.

45
00:02:11,550 --> 00:02:16,750
Ara fem servir les dades com un full de ruta
per navegar aquesta estructura de dades.

46
00:02:16,750 --> 00:02:18,710
I si podem seguir
el full de ruta, si podem

47
00:02:18,710 --> 00:02:22,390
seguir les dades de
principi a fi, anem a

48
00:02:22,390 --> 00:02:24,945
saber si aquestes dades
existir en el trie.

49
00:02:24,945 --> 00:02:28,310
>> I si no podem seguir el mapa
del que significa per posar fi a tots,

50
00:02:28,310 --> 00:02:30,600
no poden existir les dades.

51
00:02:30,600 --> 00:02:32,890
Un cop més, les tecles són aquí
garanteix que sigui únic.

52
00:02:32,890 --> 00:02:36,020
I així, a diferència d'una taula hash, mai
haver de lidiar amb col·lisions aquí.

53
00:02:36,020 --> 00:02:39,090
I no hi ha dues peces de dades
tenir exactament el mateix full de ruta

54
00:02:39,090 --> 00:02:40,530
llevat que les dades són idèntics.

55
00:02:40,530 --> 00:02:44,580
>> Si inserim John, llavors
busquem Joan.

56
00:02:44,580 --> 00:02:47,430
Això és dues peces idèntiques de
dades, la dreta, estem mirant a través.

57
00:02:47,430 --> 00:02:49,880
Però d'altra banda, cap
dues peces de dades són

58
00:02:49,880 --> 00:02:52,750
la garantia de tenir fulls de ruta únics
a través d'aquesta estructura de dades.

59
00:02:52,750 --> 00:02:56,210
I anem a fer una ullada a
una imatge visual d'això en un moment.

60
00:02:56,210 --> 00:02:58,810
>> Farem això en tractar de
crear una nova estructura de dades,

61
00:02:58,810 --> 00:03:00,564
la cartografia dels següents parells de valors clau.

62
00:03:00,564 --> 00:03:03,480
En aquest cas, nosaltres no farem servir
una cosa tan simple com un valor booleà.

63
00:03:03,480 --> 00:03:06,200
En realitat anem a emmagatzemar la cadena.

64
00:03:06,200 --> 00:03:08,690
I aquesta cadena es va a
ser el nom d'una universitat.

65
00:03:08,690 --> 00:03:12,140
>> I la clau serà l'any
quan es va fundar aquesta universitat.

66
00:03:12,140 --> 00:03:15,380
Tots els anys per a les universitats
van a ser de quatre dígits.

67
00:03:15,380 --> 00:03:19,840
I així utilitzarem aquests quatre dígits a
navegar a través d'aquesta estructura de dades.

68
00:03:19,840 --> 00:03:22,270
I anem a veure, un cop més, com
fem que en tan sols un segon.

69
00:03:22,270 --> 00:03:25,110
>> Al final de la ruta,
anem a veure el nom

70
00:03:25,110 --> 00:03:30,250
de la Universitat que correspon
a aquesta tecla, aquests quatre dígits.

71
00:03:30,250 --> 00:03:34,390
La idea bàsica darrere d'un trie
és que tenim una ruta central.

72
00:03:34,390 --> 00:03:35,640
Així que pensar-hi com un arbre.

73
00:03:35,640 --> 00:03:39,211
I això és similar a l'ortografia
i en concepte a un arbre.

74
00:03:39,211 --> 00:03:41,460
Generalment quan pensem en
arbres en el món real,

75
00:03:41,460 --> 00:03:44,090
tenen una arrel que està en el
sòl i creixen cap amunt

76
00:03:44,090 --> 00:03:46,830
i tenen sucursals
i tenen fulles.

77
00:03:46,830 --> 00:03:49,450
I, bàsicament, la idea de
1 trie és exactament el mateix,

78
00:03:49,450 --> 00:03:51,755
excepte que l'arrel està ancorat
en algun lloc en el cel.

79
00:03:51,755 --> 00:03:53,130
I les fulles estan en el fons.

80
00:03:53,130 --> 00:03:55,750
>> Així que és una mena de prendre un arbre
i acaba de moure d'una tirada a l'inrevés.

81
00:03:55,750 --> 00:03:56,880
Però encara hi ha branques.

82
00:03:56,880 --> 00:03:59,463
I aquests serien els nostres camins,
aquests seran les nostres connexions

83
00:03:59,463 --> 00:04:02,220
des de l'arrel fins a les fulles.

84
00:04:02,220 --> 00:04:04,200
En aquest cas, aquells
camins, aquelles branques

85
00:04:04,200 --> 00:04:08,490
s'etiqueten amb els dígits que ens diuen
que manera d'anar des d'on estem.

86
00:04:08,490 --> 00:04:11,800
>> Si veiem un 0, baixem aquesta branca,
si veiem un 1, vam baixar aquesta branca,

87
00:04:11,800 --> 00:04:12,900
i així i així successivament.

88
00:04:12,900 --> 00:04:14,060
Bé, què vol dir això?

89
00:04:14,060 --> 00:04:16,519
Bé, això vol dir que
en cada punt d'unió

90
00:04:16,519 --> 00:04:19,260
i cada node al
mitjana i totes les branques,

91
00:04:19,260 --> 00:04:23,020
hi ha 10 possibles
llocs que podem anar.

92
00:04:23,020 --> 00:04:27,690
Així que hi ha 10 punters
de cada lloc.

93
00:04:27,690 --> 00:04:30,610
>> I aquí és on tries poden obtenir una
mica intimidatori per a algú

94
00:04:30,610 --> 00:04:34,460
qui no té una gran quantitat de
experiència en ciències de la computació abans.

95
00:04:34,460 --> 00:04:35,960
Però intents són realment bastant impressionant.

96
00:04:35,960 --> 00:04:37,793
I si vostè té la
oportunitat de treballar amb ells

97
00:04:37,793 --> 00:04:40,420
i que està disposat a excavar a
i experimentar amb ells,

98
00:04:40,420 --> 00:04:44,234
són realment molt interessant
estructures de dades per treballar.

99
00:04:44,234 --> 00:04:46,900
Si volem inserir un element
al trie, tot el que ha de fer

100
00:04:46,900 --> 00:04:51,360
és construir el camí correcte
des de l'arrel a la fulla.

101
00:04:51,360 --> 00:04:55,390
Això és el que cada pas al llarg de
el camí podria ser similar.

102
00:04:55,390 --> 00:04:59,660
Anem a definir un nou dades
estructura per a un nou node trucat un trie.

103
00:04:59,660 --> 00:05:02,560
>> I dins d'aquestes dades
estructura hi ha dues peces.

104
00:05:02,560 --> 00:05:05,460
Anem a emmagatzemar el
nom d'una universitat.

105
00:05:05,460 --> 00:05:09,410
I anem a emmagatzemar
una matriu de punters

106
00:05:09,410 --> 00:05:12,190
a altres nodes del mateix tipus.

107
00:05:12,190 --> 00:05:14,780
Així, de nou, això és que espècie
del concepte d'arreu

108
00:05:14,780 --> 00:05:18,567
som, a les 10 possibles
llocs que podem anar.

109
00:05:18,567 --> 00:05:20,150
Si veiem un 0, baixem aquesta branca.

110
00:05:20,150 --> 00:05:22,690
Si veiem un 1, aquesta branca,
i així successivament i així successivament i així successivament.

111
00:05:22,690 --> 00:05:25,160
Si diem 9, baixem aquesta branca.

112
00:05:25,160 --> 00:05:28,220
Així que en cada punt d'unió,
podem anar 10 llocs possibles.

113
00:05:28,220 --> 00:05:35,740
Així que cada node ha de contenir 10 punters
a altres nodes, a altres 10 nodes.

114
00:05:35,740 --> 00:05:39,810
>> I les dades que estem emmagatzemant és
només el nom de la universitat.

115
00:05:39,810 --> 00:05:41,060
Així que anem a construir un trie.

116
00:05:41,060 --> 00:05:44,860
Anem a inserir un parell
d'elements en la nostra trie.

117
00:05:44,860 --> 00:05:46,740
Així que a la part superior,
aquest és el nostre node arrel.

118
00:05:46,740 --> 00:05:49,740
Aquesta és, probablement, serà una cosa
vas globalment declari.

119
00:05:49,740 --> 00:05:53,450
I vostè va a mantenir globalment
un punter a aquest node sempre.

120
00:05:53,450 --> 00:05:55,360
>> Vostè dirà,
és igual a l'arrel, i ja està

121
00:05:55,360 --> 00:05:57,580
va a malloc mateix node trie.

122
00:05:57,580 --> 00:05:59,850
I mai vas
tocar l'arrel de nou.

123
00:05:59,850 --> 00:06:02,300
Cada vegada que vulgui
començar a navegar a través de,

124
00:06:02,300 --> 00:06:05,802
configura un altre punter
igual a l'arrel, com trav,

125
00:06:05,802 --> 00:06:07,760
que és l'exemple que
utilitzar en moltes de les meves vídeos

126
00:06:07,760 --> 00:06:11,090
aquí en piles i cues
i llistes d'enllaços i així successivament.

127
00:06:11,090 --> 00:06:13,320
>> S'estableix un altre punter
anomenada trav de recorregut.

128
00:06:13,320 --> 00:06:15,890
I utilitza trav per navegar
a través de l'estructura de dades.

129
00:06:15,890 --> 00:06:17,500
Així que anem a veure com això podria mirar.

130
00:06:17,500 --> 00:06:19,880
Així que ara mateix, el que
no un node sembla?

131
00:06:19,880 --> 00:06:22,920
Bé, de la mateixa manera que les nostres dades
declaració d'estructura indicada,

132
00:06:22,920 --> 00:06:26,906
tenim una cadena, que
en aquest cas és buida.

133
00:06:26,906 --> 00:06:27,780
No hi ha res aquí.

134
00:06:27,780 --> 00:06:29,550
>> I un conjunt de 10 indicadors.

135
00:06:29,550 --> 00:06:31,790
I en aquest moment, només
tenen 1 node en aquest trie.

136
00:06:31,790 --> 00:06:33,110
No hi ha res més a ell.

137
00:06:33,110 --> 00:06:36,020
Així que tots els 10 dels
punta punters a NULL.

138
00:06:36,020 --> 00:06:38,090
Això és el que indica el vermell.

139
00:06:38,090 --> 00:06:39,500
>> Anem a inserir la cadena de Harvard.

140
00:06:39,500 --> 00:06:41,999
Anem a inserir la Universitat de
Harvard en aquest trie, que

141
00:06:41,999 --> 00:06:43,940
va ser fundada l'any 1636.

142
00:06:43,940 --> 00:06:48,220
Volem fer servir la clau,
1636, per dir-nos on som

143
00:06:48,220 --> 00:06:50,140
va a emmagatzemar Harvard al trie.

144
00:06:50,140 --> 00:06:51,470
Ara, com podem fer això?

145
00:06:51,470 --> 00:06:52,886
>> Podria ser alguna cosa com això.

146
00:06:52,886 --> 00:06:54,160
Comencem a l'arrel.

147
00:06:54,160 --> 00:06:56,920
I tenim aquests 10 llocs que podem anar.

148
00:06:56,920 --> 00:06:59,900
L'arrel és igual que qualsevol
un altre node del trie.

149
00:06:59,900 --> 00:07:02,850
Hi ha 10 llocs que podem anar des d'aquí.

150
00:07:02,850 --> 00:07:07,215
>> A on anem, probablement volem
per anar si la clau és 1636?

151
00:07:07,215 --> 00:07:08,340
No hi ha realment dues opcions.

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

153
00:07:08,450 --> 00:07:10,825
Podem construir la clau de
dreta a esquerra i començar amb 6.

154
00:07:10,825 --> 00:07:14,000
O podríem construir la clau de
esquerra a dreta i començar amb 1.

155
00:07:14,000 --> 00:07:16,140
>> És probablement més
intuïtiu com un ésser humà

156
00:07:16,140 --> 00:07:18,110
entendre que va a
simplement aneu a l'esquerra a dreta.

157
00:07:18,110 --> 00:07:21,140
I pel que si vull inserir
Harvard en aquest trie,

158
00:07:21,140 --> 00:07:23,560
Probablement Vull començar
començant a l'arrel,

159
00:07:23,560 --> 00:07:25,720
mirant els meus 10 opcions
davant meu, i dient:

160
00:07:25,720 --> 00:07:28,700
Jo vull anar pel camí gener.

161
00:07:28,700 --> 00:07:29,700
D'ACORD.

162
00:07:29,700 --> 00:07:31,810
>> Ara, 1 camí és actualment nul.

163
00:07:31,810 --> 00:07:35,920
Així que si vull continuar per aquest camí
per inserir aquest element en el trie,

164
00:07:35,920 --> 00:07:42,040
He de malloc un nou node, tenen 1
Assenyalo allà, i llavors vull sortir.

165
00:07:42,040 --> 00:07:46,460
>> Així que, bàsicament, estic en una
punt en el que estic de peu

166
00:07:46,460 --> 00:07:50,270
a l'arrel de l'arbre o la
trie i hi ha 10 sucursals.

167
00:07:50,270 --> 00:07:52,260
Però cada branca té una
porta de davant d'ella.

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

169
00:07:53,060 --> 00:07:54,850
Perquè no hi ha res més que hi ha.

170
00:07:54,850 --> 00:07:56,522
No pas segur.

171
00:07:56,522 --> 00:07:58,980
Això vol dir que no hi ha res
per qualsevol d'aquestes branques.

172
00:07:58,980 --> 00:08:02,532
Si vull començar a construir
alguna cosa, vull treure la porta.

173
00:08:02,532 --> 00:08:04,490
Vull treure la porta
davant del número 1.

174
00:08:04,490 --> 00:08:05,698
I vull caminar per això.

175
00:08:05,698 --> 00:08:08,060
I jo vull construir
un altre lloc per a mi per anar.

176
00:08:08,060 --> 00:08:09,470
>> I això és el que he fet aquí.

177
00:08:09,470 --> 00:08:11,430
Així que 1 ja no apunta a null.

178
00:08:11,430 --> 00:08:13,830
He dit que és segur anar per aquí ara.

179
00:08:13,830 --> 00:08:15,789
Jo vaig construir un altre node.

180
00:08:15,789 --> 00:08:18,330
I quan arribi a aquest node, I
tenir una altra decisió que prendre.

181
00:08:18,330 --> 00:08:20,890
On aniré d'aquí?

182
00:08:20,890 --> 00:08:22,700
>> Bé, jo ja he passat per l'1.

183
00:08:22,700 --> 00:08:24,470
Així que ara, probablement, vull anar per la 6.

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

185
00:08:24,970 --> 00:08:27,100
Un cop més, tinc 10 llocs que puc triar.

186
00:08:27,100 --> 00:08:30,060
Així que ara anirem cap avall el número 6.

187
00:08:30,060 --> 00:08:32,280
Així que puc esborrar la porta
davant del número 6.

188
00:08:32,280 --> 00:08:33,250
I entro aquí baix.

189
00:08:33,250 --> 00:08:34,580
I vaig a construir un altre node.

190
00:08:34,580 --> 00:08:37,630
I he arribat a un punt d'unió.

191
00:08:37,630 --> 00:08:40,289
>> Un cop més, tinc 10 opcions
d'on puc anar.

192
00:08:40,289 --> 00:08:42,799
M'he mudat d'1 a 6.

193
00:08:42,799 --> 00:08:44,215
Així que ara, probablement, vull anar a la 3.

194
00:08:44,215 --> 00:08:45,381
3, no hi ha cap lloc que puc anar.

195
00:08:45,381 --> 00:08:48,980
Així que he de netejar el camí
i construir-me un nou espai.

196
00:08:48,980 --> 00:08:50,870
I després de 3, per on vull anar?

197
00:08:50,870 --> 00:08:52,450
Vull baixar juny.

198
00:08:52,450 --> 00:08:54,770
>> I, de nou, vaig haver de
aclarir el camí per fer-ho.

199
00:08:54,770 --> 00:08:59,179
Així que ara que he fet servir el meu clau per a inserir crear
nodes i començar a construir aquest trie.

200
00:08:59,179 --> 00:09:00,220
He començat a l'arrel.

201
00:09:00,220 --> 00:09:03,666
He anat fins 1636.

202
00:09:03,666 --> 00:09:05,540
I ara estic a la part inferior
allà en aquell node.

203
00:09:05,540 --> 00:09:06,610
I vostè pot ser capaç de
veure-ho a la pantalla.

204
00:09:06,610 --> 00:09:07,735
>> Ha ressaltat en groc.

205
00:09:07,735 --> 00:09:10,020
Aquí és on actualment sóc.

206
00:09:10,020 --> 00:09:11,300
El meu clau està fet.

207
00:09:11,300 --> 00:09:13,030
He esgotat totes les posicions de la clau.

208
00:09:13,030 --> 00:09:15,040
Així que no puc anar més lluny.

209
00:09:15,040 --> 00:09:17,720
Així que en aquest punt, tot el que
realment heu de fer és dir, a D'acord.

210
00:09:17,720 --> 00:09:18,990
És com espècie de mira
cap a terra,

211
00:09:18,990 --> 00:09:21,115
si estàs imaginant
a tu mateix ja que aquest tipus de ruta

212
00:09:21,115 --> 00:09:22,350
amb diferents connexions.

213
00:09:22,350 --> 00:09:25,800
Ordenar de mirar cap avall i una mena de
ruixar pintura de Harvard a terra.

214
00:09:25,800 --> 00:09:26,800
Aquest és el nom d'aquesta.

215
00:09:26,800 --> 00:09:28,300
Saber que és el que està en aquest lloc.

216
00:09:28,300 --> 00:09:31,870
Si comencem a l'arrel i baixem
1 i després 6 i després 3 i després 6,

217
00:09:31,870 --> 00:09:32,780
On estem?

218
00:09:32,780 --> 00:09:35,640
Bé, si mirem cap avall
i veiem Harvard, llavors

219
00:09:35,640 --> 00:09:38,960
sabem que Harvard era
fundada el 1636 amb seu al camí

220
00:09:38,960 --> 00:09:41,400
estem implementant aquesta estructura de dades.

221
00:09:41,400 --> 00:09:43,177
Així que era d'esperar senzill.

222
00:09:43,177 --> 00:09:44,760
Anem a fer dues insercions més.

223
00:09:44,760 --> 00:09:50,060
I és d'esperar que va a ajudar a
veure aquest fet dues vegades més.

224
00:09:50,060 --> 00:09:52,210
>> Ara, anem a inserir una altra universitat.

225
00:09:52,210 --> 00:09:54,630
Anem a inserir Yale en aquest trie.

226
00:09:54,630 --> 00:09:57,037
Yale va ser fundada el 1701.

227
00:09:57,037 --> 00:09:58,870
Així que anem a començar en el
arrel, com sempre ho fem.

228
00:09:58,870 --> 00:09:59,890
I ens vam posar un punter recorregut.

229
00:09:59,890 --> 00:10:01,624
Farem servir això per moure a través de.

230
00:10:01,624 --> 00:10:03,790
El primer que volem
fer és anar pel camí gener.

231
00:10:03,790 --> 00:10:05,830
Aquest és el primer dígit de la clau.

232
00:10:05,830 --> 00:10:08,420
Afortunadament, però, no ho fem
haver de fer cap treball en aquesta ocasió.

233
00:10:08,420 --> 00:10:09,919
La ruta 1 ja ha estat aprovat.

234
00:10:09,919 --> 00:10:13,520
Em vaig aclarir prèviament quan
va ser la inserció de la Universitat d'Harvard en 1636.

235
00:10:13,520 --> 00:10:18,090
Així que em puc moure amb seguretat
baix 1 i acaba d'anar-hi.

236
00:10:18,090 --> 00:10:20,150
Si es pot moure per l'1.

237
00:10:20,150 --> 00:10:22,930
>> Ara, però, jo vull anar a 7.

238
00:10:22,930 --> 00:10:24,280
Em vaig aclarir la forma a les 6.

239
00:10:24,280 --> 00:10:27,050
Sé que puc amb seguretat
continuar pel camí juny.

240
00:10:27,050 --> 00:10:29,220
Però necessito per continuar en el camí juliol.

241
00:10:29,220 --> 00:10:30,580
Llavors, què he de fer?

242
00:10:30,580 --> 00:10:35,070
Bé, igual que abans, només necessito
per aclarir la porta, sortir del camí,

243
00:10:35,070 --> 00:10:38,740
i construir un nou node de la ruta 7.

244
00:10:38,740 --> 00:10:40,250
Igual que aquest.

245
00:10:40,250 --> 00:10:42,930
>> Així que ara m'he mudat 1 i 7.

246
00:10:42,930 --> 00:10:45,550
I ara compte, jo sóc una mena
d'aquesta nova subbranca.

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

248
00:10:46,050 --> 00:10:49,260
Tota la resta de 16
, Jo no em preocupo.

249
00:10:49,260 --> 00:10:50,720
No faré res 16.

250
00:10:50,720 --> 00:10:51,750
Estic fent 17 coses.

251
00:10:51,750 --> 00:10:58,380
>> Així que ara des del 17 en endavant, he de
espècie d'obrir nous camins aquí.

252
00:10:58,380 --> 00:11:00,462
El següent dígit meva clau és 0.

253
00:11:00,462 --> 00:11:01,670
Jo clarament no puc arribar enlloc.

254
00:11:01,670 --> 00:11:02,628
Acabo de construir aquest node.

255
00:11:02,628 --> 00:11:04,550
Així que sé que no hi ha
camins a seguir d'aquí.

256
00:11:04,550 --> 00:11:06,370
Així que he de fer un jo mateix.

257
00:11:06,370 --> 00:11:09,360
>> Així que malloc un nou node
i tenen 0 punt allà.

258
00:11:09,360 --> 00:11:12,770
I a continuació, una vegada més, em malloc 1
nou node i tenen un punt allà.

259
00:11:12,770 --> 00:11:15,870
Un cop més, he esgotat el meu clau, 1701.

260
00:11:15,870 --> 00:11:18,472
Així que miro cap avall i jo pintura d'aerosol de Yale.

261
00:11:18,472 --> 00:11:19,680
Aquest és el nom d'aquest node.

262
00:11:19,680 --> 00:11:24,660
>> I ara si mai necessito per veure si Yale
És en aquest trie, començo a l'arrel,

263
00:11:24,660 --> 00:11:27,060
Vaig per 1701, i miro cap avall.

264
00:11:27,060 --> 00:11:30,030
I si veig aerosol Yale
pintada al terra, a continuació,

265
00:11:30,030 --> 00:11:32,200
Sigues Yale existeix en aquest trie.

266
00:11:32,200 --> 00:11:32,950
Anem a fer una més.

267
00:11:32,950 --> 00:11:36,430
Anem a inserir Dartmouth en això
trie, que va ser fundada el 1769.

268
00:11:36,430 --> 00:11:37,750
>> Comenceu a l'arrel de nou.

269
00:11:37,750 --> 00:11:39,445
El meu primer dígit de la meva clau es 1.

270
00:11:39,445 --> 00:11:40,820
Em puc moure amb seguretat per aquest camí.

271
00:11:40,820 --> 00:11:42,400
Que ja existeix.

272
00:11:42,400 --> 00:11:44,040
El següent dígit de la meva clau és 7.

273
00:11:44,040 --> 00:11:45,890
Em puc moure amb seguretat per aquest camí.

274
00:11:45,890 --> 00:11:47,540
Existeix també.

275
00:11:47,540 --> 00:11:49,000
>> El meu següent és 6.

276
00:11:49,000 --> 00:11:52,860
Des d'aquí, des d'on actualment sóc
en groc allà en aquell node central,

277
00:11:52,860 --> 00:11:56,060
6 està actualment bloquejat apagat.

278
00:11:56,060 --> 00:11:58,830
Si vull anar per aquest camí,
He de construir jo mateix.

279
00:11:58,830 --> 00:12:02,250
Així que vaig a malloc un nou node
i tenen 6 punts allà.

280
00:12:02,250 --> 00:12:04,250
I llavors, un cop més, estic
camins per obrir aquí.

281
00:12:04,250 --> 00:12:10,750
>> Així que malloc un nou node perquè des
aquest nombre ruta node-- 9-- i llavors ara

282
00:12:10,750 --> 00:12:13,584
si viatjo 1769, i miro cap avall.

283
00:12:13,584 --> 00:12:15,500
No hi ha res actualment
aerosol pintat allà.

284
00:12:15,500 --> 00:12:16,930
Puc escriure Dartmouth.

285
00:12:16,930 --> 00:12:20,710
I he inserit
Dartmouth al trie.

286
00:12:20,710 --> 00:12:23,450
>> Així que aquesta és la inserció
coses al trie.

287
00:12:23,450 --> 00:12:25,384
Ara volem buscar coses.

288
00:12:25,384 --> 00:12:27,050
Com busquem coses al trie?

289
00:12:27,050 --> 00:12:29,170
Bé, és més o menys la mateixa idea.

290
00:12:29,170 --> 00:12:33,620
Ara només utilitzem els dígits de la clau
per veure si podem navegar des de l'arrel

291
00:12:33,620 --> 00:12:37,170
cap a on volem anar en el trie.

292
00:12:37,170 --> 00:12:41,620
>> Si arribem a un carreró sense sortida en qualsevol moment, a continuació,
sabem que no pot existeix aquest element

293
00:12:41,620 --> 00:12:44,500
o del que ho faria camí
ja s'han aclarit.

294
00:12:44,500 --> 00:12:45,930
Si ho fem tot el camí fins
Al final, tot el que ha de fer

295
00:12:45,930 --> 00:12:48,471
és mirar cap avall i veure si això és
l'element que estem buscant.

296
00:12:48,471 --> 00:12:49,335
Si ho és, l'èxit.

297
00:12:49,335 --> 00:12:52,610
Si no ho és, fallar.

298
00:12:52,610 --> 00:12:54,940
>> Així que anem a la recerca per
Harvard en aquest trie.

299
00:12:54,940 --> 00:12:56,020
Comencem a l'arrel.

300
00:12:56,020 --> 00:12:58,228
I, de nou, anem a
crear un punter recorregut

301
00:12:58,228 --> 00:12:59,390
fer els nostres moviments per a nosaltres.

302
00:12:59,390 --> 00:13:02,080
Des de l'arrel sabem que el
primer lloc hem d'anar és 1,

303
00:13:02,080 --> 00:13:03,390
podem fer això?

304
00:13:03,390 --> 00:13:03,982
Sí, podem.

305
00:13:03,982 --> 00:13:04,690
Si hi ha segura.

306
00:13:04,690 --> 00:13:06,660
Podem anar-hi.

307
00:13:06,660 --> 00:13:08,440
>> Ara, el següent lloc on cal anar és 6.

308
00:13:08,440 --> 00:13:10,557
Existeix la ruta 6 des d'aquí?

309
00:13:10,557 --> 00:13:11,140
Sí, ho fa.

310
00:13:11,140 --> 00:13:12,690
Podem anar pel camí juny.

311
00:13:12,690 --> 00:13:13,905
I acabem aquí.

312
00:13:13,905 --> 00:13:16,130
>> Podem anar pel camí de 3 des d'aquí?

313
00:13:16,130 --> 00:13:18,450
Bé, resulta que,
sí, que existeix també.

314
00:13:18,450 --> 00:13:20,790
I podem aconseguir en el camí juny des d'aquí?

315
00:13:20,790 --> 00:13:21,982
Sí, podem.

316
00:13:21,982 --> 00:13:24,002
>> Encara no hem contestat
la qüestió encara.

317
00:13:24,002 --> 00:13:25,710
Encara hi ha una més
pas, que és ara

318
00:13:25,710 --> 00:13:28,520
hem de mirar cap avall i
veure si això és actually--

319
00:13:28,520 --> 00:13:32,660
si estem a la recerca de Harvard, és que
el que trobem després que vam esgotar la clau?

320
00:13:32,660 --> 00:13:35,430
En l'exemple que estem utilitzant aquí,
els anys són sempre quatre dígits.

321
00:13:35,430 --> 00:13:40,280
Però és possible que estigui utilitzant el exemple en què
vostè està guardant un diccionari de paraules.

322
00:13:40,280 --> 00:13:44,060
>> I així, en lloc de tenir 10 punters
per la meva ubicació, és possible que tingui 26.

323
00:13:44,060 --> 00:13:46,040
Un per cada lletra de l'alfabet.

324
00:13:46,040 --> 00:13:50,350
I hi ha algunes paraules com ratpenat,
que és un subconjunt de lot, per exemple.

325
00:13:50,350 --> 00:13:53,511
I pel que fins i tot si s'arriba a la
final de la clau i es mira cap avall,

326
00:13:53,511 --> 00:13:55,260
pot ser que no vegi el que
que vostè està buscant.

327
00:13:55,260 --> 00:13:58,500
>> Així que sempre cal recórrer
tot el camí i després

328
00:13:58,500 --> 00:14:01,540
si vostè fos capaç d'èxit
per recórrer tot el camí,

329
00:14:01,540 --> 00:14:03,440
mirar cap avall i faci una confirmació final.

330
00:14:03,440 --> 00:14:05,120
¿Això és el que estic buscant?

331
00:14:05,120 --> 00:14:07,740
Bé, jo miro cap avall després de començar
a la part superior i anant 1.636.

332
00:14:07,740 --> 00:14:08,240
Miro cap avall.

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

334
00:14:09,400 --> 00:14:11,689
Així que, sí, ho vaig aconseguir.

335
00:14:11,689 --> 00:14:13,980
¿I si el que estic buscant
no està en el trie, però.

336
00:14:13,980 --> 00:14:17,200
Què passa si estic buscant Princeton,
que va ser fundada el 1746.

337
00:14:17,200 --> 00:14:20,875
I així, 1746 es converteix en la clau
per navegar pel trie.

338
00:14:20,875 --> 00:14:22,040
Bé, em poso a l'arrel.

339
00:14:22,040 --> 00:14:24,760
I el primer lloc vull
que va pel camí gener.

340
00:14:24,760 --> 00:14:25,590
Puc fer-ho?

341
00:14:25,590 --> 00:14:26,490
Sí, jo puc.

342
00:14:26,490 --> 00:14:28,730
>> Puc anar pel camí de 7 a partir d'aquí?

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

344
00:14:29,230 --> 00:14:30,750
Que hi ha també.

345
00:14:30,750 --> 00:14:32,460
Però puc anar pel camí 4 de aquí?

346
00:14:32,460 --> 00:14:35,550
Això és com demanar-li a la pregunta, pot
Procedeixo per aquest petit quadrat

347
00:14:35,550 --> 00:14:37,114
que he ressaltat en groc?

348
00:14:37,114 --> 00:14:38,030
No hi ha res allà.

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

350
00:14:38,610 --> 00:14:41,310
>> No hi ha manera d'avançar pel camí abril.

351
00:14:41,310 --> 00:14:46,480
Si Princeton va ser en aquest trie, que 4
hauria estat buidat per a nosaltres ja.

352
00:14:46,480 --> 00:14:49,130
I així, en aquest punt
hem arribat a un carreró sense sortida.

353
00:14:49,130 --> 00:14:50,250
No podem anar més enllà.

354
00:14:50,250 --> 00:14:53,440
I així es pot dir, en definitiva, no.

355
00:14:53,440 --> 00:14:56,760
Princeton no existeix en aquest trie.

356
00:14:56,760 --> 00:14:58,860
>> Llavors, què significa tot això?

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

358
00:14:59,360 --> 00:15:01,000
Hi ha molt per fer aquí.

359
00:15:01,000 --> 00:15:02,500
Hi ha punters de tot el lloc.

360
00:15:02,500 --> 00:15:04,249
I, com es pot veure
simplement a partir del diagrama,

361
00:15:04,249 --> 00:15:07,010
hi ha una gran quantitat de nodes que
són una mena de volar al voltant.

362
00:15:07,010 --> 00:15:13,480
Però noti cada vegada que volíem
comprovar si hi havia alguna cosa en el trie,

363
00:15:13,480 --> 00:15:15,000
només vam haver de fer 4 moviments.

364
00:15:15,000 --> 00:15:17,208
>> Cada vegada que volíem
inserir alguna cosa en el trie,

365
00:15:17,208 --> 00:15:20,440
hem de fer 4 moviments, possiblement
mallocing algunes coses en el camí.

366
00:15:20,440 --> 00:15:23,482
Però com vam veure quan ens inserim
Dartmouth al trie,

367
00:15:23,482 --> 00:15:25,940
de vegades alguns de la ruta
podria ja ser netejat per a nosaltres.

368
00:15:25,940 --> 00:15:30,520
I així com la nostra trie fa més gran i
més gran, hem de fer menys feina cada vegada

369
00:15:30,520 --> 00:15:32,270
inserir noves coses
perquè ja hem

370
00:15:32,270 --> 00:15:35,746
construït una gran quantitat de la substància intermèdia
branques en el camí.

371
00:15:35,746 --> 00:15:38,370
Si tan sols alguna vegada hem de mirar
4 coses, 4 és només una constant.

372
00:15:38,370 --> 00:15:41,750
Realment estem apropant tipus de
inserció constant de temps

373
00:15:41,750 --> 00:15:44,501
i la recerca constant de temps.

374
00:15:44,501 --> 00:15:47,500
El desavantatge, és clar, és que
aquest trie, com vostè probablement pot dir,

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

376
00:15:49,030 --> 00:15:51,040
Cada un d'aquests nodes
ocupa molt espai.

377
00:15:51,040 --> 00:15:52,090
>> Però aquesta és la disjuntiva.

378
00:15:52,090 --> 00:15:55,260
Si volem realment ràpid
inserció, deleció molt ràpid,

379
00:15:55,260 --> 00:15:59,630
i les operacions de recerca molt ràpid, hem de
té una gran quantitat de dades que volen voltant.

380
00:15:59,630 --> 00:16:03,590
Hem de deixar de banda un munt d'espai
i la memòria perquè l'estructura de dades

381
00:16:03,590 --> 00:16:04,290
d'existir.

382
00:16:04,290 --> 00:16:05,415
>> I això és l'equilibri.

383
00:16:05,415 --> 00:16:07,310
Però sembla que
podria haver trobat.

384
00:16:07,310 --> 00:16:09,560
Podríem haver trobat que
Sant Grial de les estructures de dades

385
00:16:09,560 --> 00:16:12,264
amb la inserció ràpida,
eliminació i cerca.

386
00:16:12,264 --> 00:16:14,430
I potser això serà un
estructura de dades apropiada

387
00:16:14,430 --> 00:16:18,890
a utilitzar per a qualsevol informació
estem tractant d'emmagatzemar.

388
00:16:18,890 --> 00:16:21,860
Sóc Doug Lloyd, això és CS50.

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