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

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

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Así que hemos estado cada vez más cerca
y más cerca de que el santo grial de los datos

4
00:00:08,550 --> 00:00:13,050
estructuras, uno que podemos insertar
en, eliminar de, y mirar hacia arriba

5
00:00:13,050 --> 00:00:15,440
en tiempo constante.

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

7
00:00:16,270 --> 00:00:17,280
En cierto modo es la meta.

8
00:00:17,280 --> 00:00:19,720
Queremos ser capaces de hacer
cosas muy, muy rápidamente.

9
00:00:19,720 --> 00:00:22,580
>> Tenemos lo encontramos aquí cuando
estamos hablando de intentos?

10
00:00:22,580 --> 00:00:23,670
Bueno, vamos a echar un vistazo.

11
00:00:23,670 --> 00:00:25,628
Así que hemos visto varias
diferentes estructuras de datos

12
00:00:25,628 --> 00:00:28,680
que manejan el mapeo de
los llamados pares clave-valor,

13
00:00:28,680 --> 00:00:32,080
cartografía de alguna pieza de datos
a alguna otra pieza de datos

14
00:00:32,080 --> 00:00:36,020
así que sabemos dónde encontrar
la información en la estructura.

15
00:00:36,020 --> 00:00:40,060
>> Así que para array, por ejemplo, el
clave es el índice de elemento o conjunto

16
00:00:40,060 --> 00:00:42,600
ubicación 0 o matriz 1 y así sucesivamente.

17
00:00:42,600 --> 00:00:46,140
Y el valor de los datos es
que existe en esa ubicación.

18
00:00:46,140 --> 00:00:48,550
Así que lo que se almacena en el array 0?

19
00:00:48,550 --> 00:00:54,290
Lo que se almacena en la matriz 1 frente a sólo
0 y 1, lo que sería las teclas.

20
00:00:54,290 --> 00:00:56,360
>> Con una tabla hash es
especie de la misma idea.

21
00:00:56,360 --> 00:01:00,690
Con una tabla hash, tenemos este hash
función que genera códigos hash.

22
00:01:00,690 --> 00:01:03,670
Así que la clave es el código hash de los datos.

23
00:01:03,670 --> 00:01:06,530
Y el valor, en particular
hablamos de encadenamiento

24
00:01:06,530 --> 00:01:10,590
en el video en tablas hash,
es que la lista enlazada de datos

25
00:01:10,590 --> 00:01:12,550
que hashes a ese código hash.

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

27
00:01:14,050 --> 00:01:16,050
¿Qué pasa con otro enfoque
este método, sin embargo?

28
00:01:16,050 --> 00:01:21,000
¿Qué pasa con un método en el que el
clave se garantiza que sea único,

29
00:01:21,000 --> 00:01:25,410
a diferencia de una tabla hash, donde podíamos
terminar con dos piezas de datos

30
00:01:25,410 --> 00:01:27,200
que tienen el mismo código hash.

31
00:01:27,200 --> 00:01:30,020
Y entonces tenemos que hacer frente a
que por cualquiera de sondeo o más

32
00:01:30,020 --> 00:01:33,340
preferentemente de encadenamiento para arreglar ese problema.

33
00:01:33,340 --> 00:01:37,520
>> Así que ahora podemos garantizar
que nuestra clave será único.

34
00:01:37,520 --> 00:01:39,690
¿Y si nuestro valor era
sólo algo tan fácil

35
00:01:39,690 --> 00:01:44,080
como verdadero y falso que nos dice si
o no esa información

36
00:01:44,080 --> 00:01:45,610
existe en la estructura?

37
00:01:45,610 --> 00:01:48,180
Booleano podría ser tan simple como un poco.

38
00:01:48,180 --> 00:01:52,660
Siendo realistas es probablemente una
byte más probable que un poco.

39
00:01:52,660 --> 00:01:55,410
Pero eso es mucho menor que
almacenar tal vez una cadena de 50 caracteres,

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

41
00:01:57,360 --> 00:02:02,210
>> Así que intenta, a hashish, mesas,
que combinan las matrices y lista enlazada,

42
00:02:02,210 --> 00:02:05,790
tries combinan matrices,
estructuras y punteros

43
00:02:05,790 --> 00:02:08,509
juntos para almacenar datos en
una forma interesante que es

44
00:02:08,509 --> 00:02:11,550
bastante diferente de
cualquier cosa que hayamos visto hasta ahora.

45
00:02:11,550 --> 00:02:16,750
Ahora usamos los datos como una hoja de ruta
para navegar esta estructura de datos.

46
00:02:16,750 --> 00:02:18,710
Y si podemos seguir
la hoja de ruta, si podemos

47
00:02:18,710 --> 00:02:22,390
seguir los datos de
principio a fin, vamos a

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

49
00:02:24,945 --> 00:02:28,310
>> Y si no podemos seguir el mapa
de lo que significa para poner fin a todos,

50
00:02:28,310 --> 00:02:30,600
no pueden existir los datos.

51
00:02:30,600 --> 00:02:32,890
Una vez más, las teclas son aquí
garantiza que sea único.

52
00:02:32,890 --> 00:02:36,020
Y así, a diferencia de una tabla hash, nunca
tener que lidiar con colisiones aquí.

53
00:02:36,020 --> 00:02:39,090
Y no hay dos piezas de datos
tener exactamente la misma hoja de ruta

54
00:02:39,090 --> 00:02:40,530
a menos que los datos son idénticos.

55
00:02:40,530 --> 00:02:44,580
>> Si insertamos John, entonces
buscamos Juan.

56
00:02:44,580 --> 00:02:47,430
Eso es dos piezas idénticas de
datos, la derecha, estamos mirando a través.

57
00:02:47,430 --> 00:02:49,880
Pero por lo demás, ninguna
dos piezas de datos son

58
00:02:49,880 --> 00:02:52,750
la garantía de tener hojas de ruta únicos
a través de esta estructura de datos.

59
00:02:52,750 --> 00:02:56,210
Y vamos a echar un vistazo a
una imagen visual de esto en un momento.

60
00:02:56,210 --> 00:02:58,810
>> Haremos esto al tratar de
crear una nueva estructura de datos,

61
00:02:58,810 --> 00:03:00,564
la cartografía de los siguientes pares de valores clave.

62
00:03:00,564 --> 00:03:03,480
En este caso, nosotros no vamos a usar
algo tan simple como un valor booleano.

63
00:03:03,480 --> 00:03:06,200
En realidad vamos a almacenar la cadena.

64
00:03:06,200 --> 00:03:08,690
Y esa cadena se va a
ser el nombre de una universidad.

65
00:03:08,690 --> 00:03:12,140
>> Y la clave va a ser el año
cuando se fundó esa universidad.

66
00:03:12,140 --> 00:03:15,380
Todos los años para las universidades
van a ser de cuatro dígitos.

67
00:03:15,380 --> 00:03:19,840
Y así vamos a utilizar esos cuatro dígitos a
navegar a través de esta estructura de datos.

68
00:03:19,840 --> 00:03:22,270
Y vamos a ver, una vez más, cómo
hacemos que en tan sólo un segundo.

69
00:03:22,270 --> 00:03:25,110
>> Al final de la ruta,
vamos a ver el nombre

70
00:03:25,110 --> 00:03:30,250
de la Universidad que corresponde
a esa tecla, esos cuatro dígitos.

71
00:03:30,250 --> 00:03:34,390
La idea básica detrás de un trie
es que tenemos una ruta central.

72
00:03:34,390 --> 00:03:35,640
Así que pensar en ello como un árbol.

73
00:03:35,640 --> 00:03:39,211
Y esto es similar en la ortografía
y en concepto a un árbol.

74
00:03:39,211 --> 00:03:41,460
Generalmente cuando pensamos en
árboles en el mundo real,

75
00:03:41,460 --> 00:03:44,090
tienen una raíz que está en el
suelo y crecen hacia arriba

76
00:03:44,090 --> 00:03:46,830
y tienen sucursales
y tienen hojas.

77
00:03:46,830 --> 00:03:49,450
Y, básicamente, la idea de
un trie es exactamente el mismo,

78
00:03:49,450 --> 00:03:51,755
excepto que la raíz está anclado
en algún lugar en el cielo.

79
00:03:51,755 --> 00:03:53,130
Y las hojas están en el fondo.

80
00:03:53,130 --> 00:03:55,750
>> Así que es algo así como tomar un árbol
y acaba de mover de un tirón al revés.

81
00:03:55,750 --> 00:03:56,880
Pero todavía hay ramas.

82
00:03:56,880 --> 00:03:59,463
Y esos serían nuestros caminos,
esos serán nuestras conexiones

83
00:03:59,463 --> 00:04:02,220
desde la raíz hasta las hojas.

84
00:04:02,220 --> 00:04:04,200
En este caso, aquellos
caminos, aquellas ramas

85
00:04:04,200 --> 00:04:08,490
se etiquetan con los dígitos que nos dicen
que manera de ir desde donde estamos.

86
00:04:08,490 --> 00:04:11,800
>> Si vemos un 0, bajamos esta rama,
si vemos un 1, bajamos esta rama,

87
00:04:11,800 --> 00:04:12,900
y así y así sucesivamente.

88
00:04:12,900 --> 00:04:14,060
Bueno, ¿qué significa esto?

89
00:04:14,060 --> 00:04:16,519
Bueno, eso significa que
en cada punto de unión

90
00:04:16,519 --> 00:04:19,260
y cada nodo en el
media y todas las ramas,

91
00:04:19,260 --> 00:04:23,020
hay 10 posibles
lugares que podemos ir.

92
00:04:23,020 --> 00:04:27,690
Así que hay 10 punteros
de cada lugar.

93
00:04:27,690 --> 00:04:30,610
>> Y aquí es donde tries pueden obtener una
poco intimidante para alguien

94
00:04:30,610 --> 00:04:34,460
quién no tiene una gran cantidad de
experiencia en ciencias de la computación antes.

95
00:04:34,460 --> 00:04:35,960
Pero intentos son realmente bastante impresionante.

96
00:04:35,960 --> 00:04:37,793
Y si usted tiene la
oportunidad de trabajar con ellos

97
00:04:37,793 --> 00:04:40,420
y que está dispuesto a excavar en
y experimentar con ellos,

98
00:04:40,420 --> 00:04:44,234
son realmente muy interesante
estructuras de datos para trabajar.

99
00:04:44,234 --> 00:04:46,900
Si queremos insertar un elemento
en el trie, todo lo que tiene que hacer

100
00:04:46,900 --> 00:04:51,360
es construir el camino correcto
desde la raíz a la hoja.

101
00:04:51,360 --> 00:04:55,390
Esto es lo que cada paso a lo largo de
el camino podría ser similar.

102
00:04:55,390 --> 00:04:59,660
Vamos a definir un nuevo datos
estructura para un nuevo nodo llamado un trie.

103
00:04:59,660 --> 00:05:02,560
>> Y dentro de esos datos
estructura hay dos piezas.

104
00:05:02,560 --> 00:05:05,460
Vamos a almacenar el
nombre de una universidad.

105
00:05:05,460 --> 00:05:09,410
Y vamos a almacenar
una matriz de punteros

106
00:05:09,410 --> 00:05:12,190
a otros nodos del mismo tipo.

107
00:05:12,190 --> 00:05:14,780
Así, de nuevo, esto es que especie
del concepto de todas partes

108
00:05:14,780 --> 00:05:18,567
somos, a las 10 posibles
lugares que podemos ir.

109
00:05:18,567 --> 00:05:20,150
Si vemos un 0, bajamos esta rama.

110
00:05:20,150 --> 00:05:22,690
Si vemos un 1, esta rama,
y así sucesivamente y así sucesivamente y así sucesivamente.

111
00:05:22,690 --> 00:05:25,160
Si decimos 9, bajamos esta rama.

112
00:05:25,160 --> 00:05:28,220
Así que en cada punto de unión,
podemos ir 10 lugares posibles.

113
00:05:28,220 --> 00:05:35,740
Así que cada nodo debe contener 10 punteros
a otros nodos, a otros 10 nodos.

114
00:05:35,740 --> 00:05:39,810
>> Y los datos que estamos almacenando es
sólo el nombre de la universidad.

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

116
00:05:41,060 --> 00:05:44,860
Vamos a insertar un par
de elementos en nuestra trie.

117
00:05:44,860 --> 00:05:46,740
Así que en la parte superior,
este es nuestro nodo raíz.

118
00:05:46,740 --> 00:05:49,740
Esta es, probablemente, va a ser algo
vas globalmente declare.

119
00:05:49,740 --> 00:05:53,450
Y usted va a mantener globalmente
un puntero a este nodo siempre.

120
00:05:53,450 --> 00:05:55,360
>> Usted va a decir,
es igual a la raíz, y ya está

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

122
00:05:57,580 --> 00:05:59,850
Y nunca vas
tocar la raíz de nuevo.

123
00:05:59,850 --> 00:06:02,300
Cada vez que desee
comenzar a navegar a través de,

124
00:06:02,300 --> 00:06:05,802
configura otro puntero
igual a la raíz, como trav,

125
00:06:05,802 --> 00:06:07,760
que es el ejemplo que
utilizar en muchas de mis videos

126
00:06:07,760 --> 00:06:11,090
aquí en pilas y colas
y listas de enlaces y así sucesivamente.

127
00:06:11,090 --> 00:06:13,320
>> Se establece otro puntero
llamada trav de recorrido.

128
00:06:13,320 --> 00:06:15,890
Y utiliza trav para navegar
a través de la estructura de datos.

129
00:06:15,890 --> 00:06:17,500
Así que vamos a ver cómo esto podría mirar.

130
00:06:17,500 --> 00:06:19,880
Así que ahora mismo, lo que
no un nodo parece?

131
00:06:19,880 --> 00:06:22,920
Bueno, al igual que nuestros datos
declaración de estructura indicada,

132
00:06:22,920 --> 00:06:26,906
tenemos una cadena, que
en este caso es vacía.

133
00:06:26,906 --> 00:06:27,780
No hay nada aquí.

134
00:06:27,780 --> 00:06:29,550
>> Y un conjunto de 10 indicadores.

135
00:06:29,550 --> 00:06:31,790
Y en este momento, sólo
tienen 1 nodo en este trie.

136
00:06:31,790 --> 00:06:33,110
No hay nada más en él.

137
00:06:33,110 --> 00:06:36,020
Así que todos los 10 de los
punta punteros a NULL.

138
00:06:36,020 --> 00:06:38,090
Eso es lo que indica el rojo.

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

140
00:06:39,500 --> 00:06:41,999
Vamos a insertar la Universidad de
Harvard en este trie, que

141
00:06:41,999 --> 00:06:43,940
fue fundada en el año 1636.

142
00:06:43,940 --> 00:06:48,220
Queremos usar la llave,
1636, para decirnos dónde estamos

143
00:06:48,220 --> 00:06:50,140
va a almacenar Harvard en el trie.

144
00:06:50,140 --> 00:06:51,470
Ahora, ¿cómo podemos hacer eso?

145
00:06:51,470 --> 00:06:52,886
>> Podría ser algo como esto.

146
00:06:52,886 --> 00:06:54,160
Comenzamos en la raíz.

147
00:06:54,160 --> 00:06:56,920
Y tenemos estos 10 lugares que podemos ir.

148
00:06:56,920 --> 00:06:59,900
La raíz es igual que cualquier
otro nodo del trie.

149
00:06:59,900 --> 00:07:02,850
Hay 10 lugares que podemos ir desde aquí.

150
00:07:02,850 --> 00:07:07,215
>> ¿A dónde vamos, probablemente queremos
para ir si la clave es 1636?

151
00:07:07,215 --> 00:07:08,340
No hay realmente dos opciones.

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

153
00:07:08,450 --> 00:07:10,825
Podemos construir la llave de
derecha a izquierda y comenzar con 6.

154
00:07:10,825 --> 00:07:14,000
O podríamos construir la llave de
izquierda a derecha y comenzar con 1.

155
00:07:14,000 --> 00:07:16,140
>> Es probablemente más
intuitivo como un ser humano

156
00:07:16,140 --> 00:07:18,110
entender que va a
simplemente vaya a la izquierda a derecha.

157
00:07:18,110 --> 00:07:21,140
Y por lo que si quiero insertar
Harvard en este trie,

158
00:07:21,140 --> 00:07:23,560
Probablemente Quiero empezar
comenzando en la raíz,

159
00:07:23,560 --> 00:07:25,720
mirando mis 10 opciones
delante de mí, y diciendo:

160
00:07:25,720 --> 00:07:28,700
Yo quiero ir por el camino 1.

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

162
00:07:29,700 --> 00:07:31,810
>> Ahora, 1 camino es actualmente nulo.

163
00:07:31,810 --> 00:07:35,920
Así que si quiero continuar por ese camino
para insertar este elemento en el trie,

164
00:07:35,920 --> 00:07:42,040
Tengo que malloc un nuevo nodo, tienen 1
Señalo allí, y entonces estoy listo para salir.

165
00:07:42,040 --> 00:07:46,460
>> Así que, básicamente, estoy en una
punto en el que estoy de pie

166
00:07:46,460 --> 00:07:50,270
en la raíz del árbol o la
trie y hay 10 sucursales.

167
00:07:50,270 --> 00:07:52,260
Pero cada rama tiene una
puerta de en frente de ella.

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

169
00:07:53,060 --> 00:07:54,850
Porque no hay nada más que hay.

170
00:07:54,850 --> 00:07:56,522
No paso seguro.

171
00:07:56,522 --> 00:07:58,980
Eso significa que no hay nada
por cualquiera de esas ramas.

172
00:07:58,980 --> 00:08:02,532
Si quiero empezar a construir
algo, quiero quitar la puerta.

173
00:08:02,532 --> 00:08:04,490
Quiero quitar la puerta
frente al número 1.

174
00:08:04,490 --> 00:08:05,698
Y quiero caminar por eso.

175
00:08:05,698 --> 00:08:08,060
Y yo quiero construir
otro lugar para mí para ir.

176
00:08:08,060 --> 00:08:09,470
>> Y eso es lo que he hecho aquí.

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

178
00:08:11,430 --> 00:08:13,830
He dicho que es seguro ir por aquí ahora.

179
00:08:13,830 --> 00:08:15,789
Yo construí otro nodo.

180
00:08:15,789 --> 00:08:18,330
Y cuando llegue a ese nodo, I
tener otra decisión que tomar.

181
00:08:18,330 --> 00:08:20,890
¿Dónde voy a ir de aquí?

182
00:08:20,890 --> 00:08:22,700
>> Bueno, yo ya he pasado por el 1.

183
00:08:22,700 --> 00:08:24,470
Así que ahora, probablemente, quiero ir por la 6.

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

185
00:08:24,970 --> 00:08:27,100
Una vez más, tengo 10 lugares que puedo elegir.

186
00:08:27,100 --> 00:08:30,060
Así que ahora vamos a ir hacia abajo el número 6.

187
00:08:30,060 --> 00:08:32,280
Así que puedo borrar la puerta
delante del número 6.

188
00:08:32,280 --> 00:08:33,250
Y entro ahí abajo.

189
00:08:33,250 --> 00:08:34,580
Y voy a construir otro nodo.

190
00:08:34,580 --> 00:08:37,630
Y he llegado a otro punto de unión.

191
00:08:37,630 --> 00:08:40,289
>> Una vez más, tengo 10 opciones
de donde puedo ir.

192
00:08:40,289 --> 00:08:42,799
Me he mudado de 1 a 6.

193
00:08:42,799 --> 00:08:44,215
Así que ahora, probablemente, quiero ir a la 3.

194
00:08:44,215 --> 00:08:45,381
3, no hay ningún lugar que puedo ir.

195
00:08:45,381 --> 00:08:48,980
Así que tengo que limpiar el camino
y construirme un nuevo espacio.

196
00:08:48,980 --> 00:08:50,870
Y después de 3, ¿por dónde quiero ir?

197
00:08:50,870 --> 00:08:52,450
Quiero bajar 6.

198
00:08:52,450 --> 00:08:54,770
>> Y, de nuevo, tuve que
despejar el camino para hacerlo.

199
00:08:54,770 --> 00:08:59,179
Así que ahora que he usado mi llave para insertar crear
nodos y empezar a construir este trie.

200
00:08:59,179 --> 00:09:00,220
He empezado en la raíz.

201
00:09:00,220 --> 00:09:03,666
He ido hasta 1636.

202
00:09:03,666 --> 00:09:05,540
Y ahora estoy en la parte inferior
allí en ese nodo.

203
00:09:05,540 --> 00:09:06,610
Y usted puede ser capaz de
verlo en su pantalla.

204
00:09:06,610 --> 00:09:07,735
>> Ha resaltado en amarillo.

205
00:09:07,735 --> 00:09:10,020
Ahí es donde actualmente soy.

206
00:09:10,020 --> 00:09:11,300
Mi llave está hecho.

207
00:09:11,300 --> 00:09:13,030
He agotado todas las posiciones de la llave.

208
00:09:13,030 --> 00:09:15,040
Así que no puedo ir más lejos.

209
00:09:15,040 --> 00:09:17,720
Así que en este punto, todo lo que
realmente necesita hacer es decir, en Aceptar.

210
00:09:17,720 --> 00:09:18,990
Es como especie de mira
hacia el suelo,

211
00:09:18,990 --> 00:09:21,115
si estás imaginando
a ti mismo ya que este tipo de ruta

212
00:09:21,115 --> 00:09:22,350
con diferentes conexiones.

213
00:09:22,350 --> 00:09:25,800
Ordenar de mirar hacia abajo y una especie de
rociar pintura de Harvard en el suelo.

214
00:09:25,800 --> 00:09:26,800
Ese es el nombre de esta.

215
00:09:26,800 --> 00:09:28,300
Saber que es lo que está en este lugar.

216
00:09:28,300 --> 00:09:31,870
Si empezamos en la raíz y bajamos
1 y luego 6 y luego 3 y luego 6,

217
00:09:31,870 --> 00:09:32,780
¿dónde estamos?

218
00:09:32,780 --> 00:09:35,640
Bueno, si miramos hacia abajo
y vemos Harvard, entonces

219
00:09:35,640 --> 00:09:38,960
sabemos que Harvard era
fundada en 1636 con sede en el camino

220
00:09:38,960 --> 00:09:41,400
estamos implementando esta estructura de datos.

221
00:09:41,400 --> 00:09:43,177
Así que era de esperar sencillo.

222
00:09:43,177 --> 00:09:44,760
Vamos a hacer dos inserciones más.

223
00:09:44,760 --> 00:09:50,060
Y es de esperar que va a ayudar a
ver este hecho dos veces más.

224
00:09:50,060 --> 00:09:52,210
>> Ahora, vamos a insertar otra universidad.

225
00:09:52,210 --> 00:09:54,630
Vamos a insertar Yale en este trie.

226
00:09:54,630 --> 00:09:57,037
Yale fue fundada en 1701.

227
00:09:57,037 --> 00:09:58,870
Así que vamos a empezar en el
raíz, como siempre lo hacemos.

228
00:09:58,870 --> 00:09:59,890
Y nos pusimos un puntero recorrido.

229
00:09:59,890 --> 00:10:01,624
Vamos a usar eso para moverse a través de.

230
00:10:01,624 --> 00:10:03,790
Lo primero que queremos
hacer es ir por el camino 1.

231
00:10:03,790 --> 00:10:05,830
Ese es el primer dígito de la llave.

232
00:10:05,830 --> 00:10:08,420
Afortunadamente, sin embargo, no lo hacemos
tener que hacer ningún trabajo en esta ocasión.

233
00:10:08,420 --> 00:10:09,919
La ruta 1 ya ha sido aprobado.

234
00:10:09,919 --> 00:10:13,520
Me aclaré previamente cuando
fue la inserción de la Universidad de Harvard en 1636.

235
00:10:13,520 --> 00:10:18,090
Así que me puedo mover con seguridad
abajo 1 y acaba de ir allí.

236
00:10:18,090 --> 00:10:20,150
Si se puede mover por el 1.

237
00:10:20,150 --> 00:10:22,930
>> Ahora, sin embargo, yo quiero ir a 7.

238
00:10:22,930 --> 00:10:24,280
Me aclaré la forma a las 6.

239
00:10:24,280 --> 00:10:27,050
Sé que puedo con seguridad
continuar por el camino 6.

240
00:10:27,050 --> 00:10:29,220
Pero necesito para continuar en el camino 7.

241
00:10:29,220 --> 00:10:30,580
Entonces, ¿qué tengo que hacer?

242
00:10:30,580 --> 00:10:35,070
Bueno, al igual que antes, sólo necesito
para despejar la puerta, salir del camino,

243
00:10:35,070 --> 00:10:38,740
y construir un nuevo nodo de la ruta 7.

244
00:10:38,740 --> 00:10:40,250
Al igual que este.

245
00:10:40,250 --> 00:10:42,930
>> Así que ahora me he mudado 1 y 7.

246
00:10:42,930 --> 00:10:45,550
Y ahora cuenta, yo soy una especie
de esta nueva subrama.

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

248
00:10:46,050 --> 00:10:49,260
Todo lo demás de 16
, yo no me preocupo.

249
00:10:49,260 --> 00:10:50,720
No voy a hacer nada 16.

250
00:10:50,720 --> 00:10:51,750
Estoy haciendo 17 cosas.

251
00:10:51,750 --> 00:10:58,380
>> Así que ahora desde el 17 en adelante, tengo que
especie de abrir nuevos caminos aquí.

252
00:10:58,380 --> 00:11:00,462
El siguiente dígito mi clave es 0.

253
00:11:00,462 --> 00:11:01,670
Yo claramente no puedo llegar a ninguna parte.

254
00:11:01,670 --> 00:11:02,628
Acabo de construir este nodo.

255
00:11:02,628 --> 00:11:04,550
Así que sé que no hay
caminos a seguir de aquí.

256
00:11:04,550 --> 00:11:06,370
Así que tengo que hacer uno yo mismo.

257
00:11:06,370 --> 00:11:09,360
>> Así que malloc un nuevo nodo
y tienen 0 punto allí.

258
00:11:09,360 --> 00:11:12,770
Y a continuación, una vez más, me malloc un
nuevo nodo y tienen un punto allí.

259
00:11:12,770 --> 00:11:15,870
Una vez más, he agotado mi llave, 1701.

260
00:11:15,870 --> 00:11:18,472
Así que miro hacia abajo y yo pintura de aerosol de Yale.

261
00:11:18,472 --> 00:11:19,680
Ese es el nombre de este nodo.

262
00:11:19,680 --> 00:11:24,660
>> Y ahora si alguna vez necesito para ver si Yale
Es en este trie, empiezo en la raíz,

263
00:11:24,660 --> 00:11:27,060
Voy por 1701, y miro hacia abajo.

264
00:11:27,060 --> 00:11:30,030
Y si veo aerosol Yale
pintada en el suelo, a continuación,

265
00:11:30,030 --> 00:11:32,200
Sé Yale existe en este trie.

266
00:11:32,200 --> 00:11:32,950
Vamos a hacer una más.

267
00:11:32,950 --> 00:11:36,430
Vamos a insertar Dartmouth en esto
trie, que fue fundada en 1769.

268
00:11:36,430 --> 00:11:37,750
>> Comience en la raíz de nuevo.

269
00:11:37,750 --> 00:11:39,445
Mi primer dígito de mi clave es 1.

270
00:11:39,445 --> 00:11:40,820
Me puedo mover con seguridad por ese camino.

271
00:11:40,820 --> 00:11:42,400
Que ya existe.

272
00:11:42,400 --> 00:11:44,040
El siguiente dígito de mi clave es 7.

273
00:11:44,040 --> 00:11:45,890
Me puedo mover con seguridad por ese camino.

274
00:11:45,890 --> 00:11:47,540
Existe también.

275
00:11:47,540 --> 00:11:49,000
>> Mi siguiente es 6.

276
00:11:49,000 --> 00:11:52,860
Desde aquí, desde donde actualmente soy
en amarillo allí en ese nodo central,

277
00:11:52,860 --> 00:11:56,060
6 está actualmente bloqueado apagado.

278
00:11:56,060 --> 00:11:58,830
Si quiero ir por ese camino,
Tengo que construir yo mismo.

279
00:11:58,830 --> 00:12:02,250
Así que voy a malloc un nuevo nodo
y tienen 6 puntos allí.

280
00:12:02,250 --> 00:12:04,250
Y entonces, una vez más, estoy
caminos por abrir aquí.

281
00:12:04,250 --> 00:12:10,750
>> Así que malloc un nuevo nodo para que desde
ese número ruta node-- 9-- y entonces ahora

282
00:12:10,750 --> 00:12:13,584
si viajo 1769, y miro hacia abajo.

283
00:12:13,584 --> 00:12:15,500
No hay nada actualmente
aerosol pintado allí.

284
00:12:15,500 --> 00:12:16,930
Puedo escribir Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Y he insertado
Dartmouth en el trie.

286
00:12:20,710 --> 00:12:23,450
>> Así que esa es la inserción
cosas en el trie.

287
00:12:23,450 --> 00:12:25,384
Ahora queremos buscar cosas.

288
00:12:25,384 --> 00:12:27,050
¿Cómo buscamos cosas en el trie?

289
00:12:27,050 --> 00:12:29,170
Bueno, es más o menos la misma idea.

290
00:12:29,170 --> 00:12:33,620
Ahora sólo utilizamos los dígitos de la clave
para ver si podemos navegar desde la raíz

291
00:12:33,620 --> 00:12:37,170
hacia donde queremos ir en el trie.

292
00:12:37,170 --> 00:12:41,620
>> Si llegamos a un callejón sin salida en cualquier momento, a continuación,
sabemos que no puede existe ese elemento

293
00:12:41,620 --> 00:12:44,500
o de lo que lo haría camino
ya se han despejado.

294
00:12:44,500 --> 00:12:45,930
Si lo hacemos todo el camino hasta
Al final, todo lo que tiene que hacer

295
00:12:45,930 --> 00:12:48,471
es mirar hacia abajo y ver si eso es
el elemento que estamos buscando.

296
00:12:48,471 --> 00:12:49,335
Si lo es, el éxito.

297
00:12:49,335 --> 00:12:52,610
Si no lo es, fallar.

298
00:12:52,610 --> 00:12:54,940
>> Así que vamos a la búsqueda para
Harvard en este trie.

299
00:12:54,940 --> 00:12:56,020
Comenzamos en la raíz.

300
00:12:56,020 --> 00:12:58,228
Y, de nuevo, vamos a
crear un puntero recorrido

301
00:12:58,228 --> 00:12:59,390
hacer nuestros movimientos para nosotros.

302
00:12:59,390 --> 00:13:02,080
Desde la raíz sabemos que el
primer lugar tenemos que ir es 1,

303
00:13:02,080 --> 00:13:03,390
podemos hacer eso?

304
00:13:03,390 --> 00:13:03,982
Si podemos.

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

306
00:13:04,690 --> 00:13:06,660
Podemos ir allí.

307
00:13:06,660 --> 00:13:08,440
>> Ahora, el siguiente lugar al que hay que ir es 6.

308
00:13:08,440 --> 00:13:10,557
¿Existe la ruta 6 desde aquí?

309
00:13:10,557 --> 00:13:11,140
Sí, lo hace.

310
00:13:11,140 --> 00:13:12,690
Podemos ir por el camino 6.

311
00:13:12,690 --> 00:13:13,905
Y terminamos aquí.

312
00:13:13,905 --> 00:13:16,130
>> ¿Podemos ir por el camino de 3 desde aquí?

313
00:13:16,130 --> 00:13:18,450
Bueno, resulta que,
sí, que existe también.

314
00:13:18,450 --> 00:13:20,790
Y podemos conseguir en el camino 6 desde aquí?

315
00:13:20,790 --> 00:13:21,982
Si podemos.

316
00:13:21,982 --> 00:13:24,002
>> Todavía no hemos contestado
la cuestión todavía.

317
00:13:24,002 --> 00:13:25,710
Todavía hay una más
paso, que es ahora

318
00:13:25,710 --> 00:13:28,520
tenemos que mirar hacia abajo y
ver si eso es actually--

319
00:13:28,520 --> 00:13:32,660
si estamos en busca de Harvard, es que
lo que encontramos después de que agotamos la clave?

320
00:13:32,660 --> 00:13:35,430
En el ejemplo que estamos utilizando aquí,
los años son siempre cuatro dígitos.

321
00:13:35,430 --> 00:13:40,280
Pero es posible que esté utilizando el ejemplo en el que
usted está guardando un diccionario de palabras.

322
00:13:40,280 --> 00:13:44,060
>> Y así, en lugar de tener 10 punteros
para mi ubicación, es posible que tenga 26.

323
00:13:44,060 --> 00:13:46,040
Uno para cada letra del alfabeto.

324
00:13:46,040 --> 00:13:50,350
Y hay algunas palabras como murciélago,
que es un subconjunto de lote, por ejemplo.

325
00:13:50,350 --> 00:13:53,511
Y por lo que incluso si se llega a la
final de la llave y se mira hacia abajo,

326
00:13:53,511 --> 00:13:55,260
puede que no vea lo que
estas buscando.

327
00:13:55,260 --> 00:13:58,500
>> Así que siempre hay que recorrer
todo el camino y luego

328
00:13:58,500 --> 00:14:01,540
si usted fuera capaz de éxito
para recorrer todo el camino,

329
00:14:01,540 --> 00:14:03,440
mirar hacia abajo y realice una confirmación final.

330
00:14:03,440 --> 00:14:05,120
¿Eso es lo que estoy buscando?

331
00:14:05,120 --> 00:14:07,740
Bueno, yo miro hacia abajo después de comenzar
en la parte superior y yendo 1.636.

332
00:14:07,740 --> 00:14:08,240
Miro hacia abajo.

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

334
00:14:09,400 --> 00:14:11,689
Así que, sí, lo logré.

335
00:14:11,689 --> 00:14:13,980
¿Y si lo que estoy buscando
no está en el trie, sin embargo.

336
00:14:13,980 --> 00:14:17,200
¿Qué pasa si estoy buscando Princeton,
que fue fundada en 1746.

337
00:14:17,200 --> 00:14:20,875
Y así, 1746 se convierte en la llave
para navegar por el trie.

338
00:14:20,875 --> 00:14:22,040
Bueno, me pongo en la raíz.

339
00:14:22,040 --> 00:14:24,760
Y el primer lugar quiero
que va por el camino 1.

340
00:14:24,760 --> 00:14:25,590
¿Puedo hacerlo?

341
00:14:25,590 --> 00:14:26,490
Si puedo.

342
00:14:26,490 --> 00:14:28,730
>> ¿Puedo ir por el camino de 7 a partir de ahí?

343
00:14:28,730 --> 00:14:29,230
Si, yo puedo.

344
00:14:29,230 --> 00:14:30,750
Que existe también.

345
00:14:30,750 --> 00:14:32,460
Pero puedo ir por el camino 4 de aquí?

346
00:14:32,460 --> 00:14:35,550
Eso es como pedirle a la pregunta, ¿puede
Procedo por ese pequeño cuadrado

347
00:14:35,550 --> 00:14:37,114
que he resaltado en amarillo?

348
00:14:37,114 --> 00:14:38,030
No hay nada allí.

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

350
00:14:38,610 --> 00:14:41,310
>> No hay manera de avanzar por el camino 4.

351
00:14:41,310 --> 00:14:46,480
Si Princeton fue en este trie, que 4
habría sido despejado para nosotros ya.

352
00:14:46,480 --> 00:14:49,130
Y así, en este punto
hemos llegado a un callejón sin salida.

353
00:14:49,130 --> 00:14:50,250
No podemos ir más allá.

354
00:14:50,250 --> 00:14:53,440
Y así se puede decir, en definitiva, no.

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

356
00:14:56,760 --> 00:14:58,860
>> Entonces, ¿qué significa todo esto?

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

358
00:14:59,360 --> 00:15:01,000
Hay mucho que hacer aquí.

359
00:15:01,000 --> 00:15:02,500
Hay punteros de todo el lugar.

360
00:15:02,500 --> 00:15:04,249
Y, como se puede ver
simplemente a partir del diagrama,

361
00:15:04,249 --> 00:15:07,010
hay una gran cantidad de nodos que
son una especie de volar alrededor.

362
00:15:07,010 --> 00:15:13,480
Pero note cada vez que queríamos
comprobar si había algo en el trie,

363
00:15:13,480 --> 00:15:15,000
sólo tuvimos que hacer 4 movimientos.

364
00:15:15,000 --> 00:15:17,208
>> Cada vez que queríamos
insertar algo en el trie,

365
00:15:17,208 --> 00:15:20,440
tenemos que hacer 4 movimientos, posiblemente
mallocing algunas cosas en el camino.

366
00:15:20,440 --> 00:15:23,482
Pero como vimos cuando nos insertamos
Dartmouth en el trie,

367
00:15:23,482 --> 00:15:25,940
a veces algunos de la ruta
podría ya ser limpiado para nosotros.

368
00:15:25,940 --> 00:15:30,520
Y así como nuestra trie hace más grande y
más grande, tenemos que hacer menos trabajo cada vez

369
00:15:30,520 --> 00:15:32,270
insertar nuevas cosas
porque ya hemos

370
00:15:32,270 --> 00:15:35,746
construido una gran cantidad de la sustancia intermedia
ramas en el camino.

371
00:15:35,746 --> 00:15:38,370
Si tan sólo alguna vez tenemos que mirar
4 cosas, 4 es sólo una constante.

372
00:15:38,370 --> 00:15:41,750
Realmente estamos acercando tipo de
inserción constante de tiempo

373
00:15:41,750 --> 00:15:44,501
y la búsqueda constante de tiempo.

374
00:15:44,501 --> 00:15:47,500
La desventaja, por supuesto, es que
este trie, como usted probablemente puede decir,

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

376
00:15:49,030 --> 00:15:51,040
Cada uno de estos nodos
ocupa mucho espacio.

377
00:15:51,040 --> 00:15:52,090
>> Pero esa es la disyuntiva.

378
00:15:52,090 --> 00:15:55,260
Si queremos realmente rápido
inserción, deleción muy rápido,

379
00:15:55,260 --> 00:15:59,630
y las operaciones de búsqueda muy rápido, tenemos que
tiene una gran cantidad de datos que vuelan alrededor.

380
00:15:59,630 --> 00:16:03,590
Tenemos que dejar de lado un montón de espacio
y la memoria para que la estructura de datos

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

382
00:16:04,290 --> 00:16:05,415
>> Y eso es el equilibrio.

383
00:16:05,415 --> 00:16:07,310
Pero parece que
podría haber encontrado.

384
00:16:07,310 --> 00:16:09,560
Podríamos haber encontrado que
santo grial de las estructuras de datos

385
00:16:09,560 --> 00:16:12,264
con la inserción rápida,
eliminación y búsqueda.

386
00:16:12,264 --> 00:16:14,430
Y tal vez esto va a ser un
estructura de datos apropiada

387
00:16:14,430 --> 00:16:18,890
a utilizar para cualquier información
estamos tratando de almacenar.

388
00:16:18,890 --> 00:16:21,860
Soy Doug Lloyd, esto es CS50.

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