[REPRODUCCIÓN DE MÚSICA] DOUG LLOYD: Así que hemos estado cada vez más cerca y más cerca de que el santo grial de los datos estructuras, uno que podemos insertar en, eliminar de, y mirar hacia arriba en tiempo constante. Correcto. En cierto modo es la meta. Queremos ser capaces de hacer cosas muy, muy rápidamente. 

Tenemos lo encontramos aquí cuando estamos hablando de intentos? Bueno, vamos a echar un vistazo. Así que hemos visto varias diferentes estructuras de datos que manejan el mapeo de los llamados pares clave-valor, cartografía de alguna pieza de datos a alguna otra pieza de datos así que sabemos dónde encontrar la información en la estructura. 

Así que para array, por ejemplo, el clave es el índice de elemento o conjunto ubicación 0 o matriz 1 y así sucesivamente. Y el valor de los datos es que existe en esa ubicación. Así que lo que se almacena en el array 0? Lo que se almacena en la matriz 1 frente a sólo 0 y 1, lo que sería las teclas. 

Con una tabla hash es especie de la misma idea. Con una tabla hash, tenemos este hash función que genera códigos hash. Así que la clave es el código hash de los datos. Y el valor, en particular hablamos de encadenamiento en el video en tablas hash, es que la lista enlazada de datos que hashes a ese código hash. Correcto. ¿Qué pasa con otro enfoque este método, sin embargo? ¿Qué pasa con un método en el que el clave se garantiza que sea único, a diferencia de una tabla hash, donde podíamos terminar con dos piezas de datos que tienen el mismo código hash. Y entonces tenemos que hacer frente a que por cualquiera de sondeo o más preferentemente de encadenamiento para arreglar ese problema. 

Así que ahora podemos garantizar que nuestra clave será único. ¿Y si nuestro valor era sólo algo tan fácil como verdadero y falso que nos dice si o no esa información existe en la estructura? Booleano podría ser tan simple como un poco. Siendo realistas es probablemente una byte más probable que un poco. Pero eso es mucho menor que almacenar tal vez una cadena de 50 caracteres, por ejemplo. 

Así que intenta, a hashish, mesas, que combinan las matrices y lista enlazada, tries combinan matrices, estructuras y punteros juntos para almacenar datos en una forma interesante que es bastante diferente de cualquier cosa que hayamos visto hasta ahora. Ahora usamos los datos como una hoja de ruta para navegar esta estructura de datos. Y si podemos seguir la hoja de ruta, si podemos seguir los datos de principio a fin, vamos a saber si esos datos existir en el trie. 

Y si no podemos seguir el mapa de lo que significa para poner fin a todos, no pueden existir los datos. Una vez más, las teclas son aquí garantiza que sea único. Y así, a diferencia de una tabla hash, nunca tener que lidiar con colisiones aquí. Y no hay dos piezas de datos tener exactamente la misma hoja de ruta a menos que los datos son idénticos. 

Si insertamos John, entonces buscamos Juan. Eso es dos piezas idénticas de datos, la derecha, estamos mirando a través. Pero por lo demás, ninguna dos piezas de datos son la garantía de tener hojas de ruta únicos a través de esta estructura de datos. Y vamos a echar un vistazo a una imagen visual de esto en un momento. 

Haremos esto al tratar de crear una nueva estructura de datos, la cartografía de los siguientes pares de valores clave. En este caso, nosotros no vamos a usar algo tan simple como un valor booleano. En realidad vamos a almacenar la cadena. Y esa cadena se va a ser el nombre de una universidad. 

Y la clave va a ser el año cuando se fundó esa universidad. Todos los años para las universidades van a ser de cuatro dígitos. Y así vamos a utilizar esos cuatro dígitos a navegar a través de esta estructura de datos. Y vamos a ver, una vez más, cómo hacemos que en tan sólo un segundo. 

Al final de la ruta, vamos a ver el nombre de la Universidad que corresponde a esa tecla, esos cuatro dígitos. La idea básica detrás de un trie es que tenemos una ruta central. Así que pensar en ello como un árbol. Y esto es similar en la ortografía y en concepto a un árbol. Generalmente cuando pensamos en árboles en el mundo real, tienen una raíz que está en el suelo y crecen hacia arriba y tienen sucursales y tienen hojas. Y, básicamente, la idea de un trie es exactamente el mismo, excepto que la raíz está anclado en algún lugar en el cielo. Y las hojas están en el fondo. 

Así que es algo así como tomar un árbol y acaba de mover de un tirón al revés. Pero todavía hay ramas. Y esos serían nuestros caminos, esos serán nuestras conexiones desde la raíz hasta las hojas. En este caso, aquellos caminos, aquellas ramas se etiquetan con los dígitos que nos dicen que manera de ir desde donde estamos. 

Si vemos un 0, bajamos esta rama, si vemos un 1, bajamos esta rama, y así y así sucesivamente. Bueno, ¿qué significa esto? Bueno, eso significa que en cada punto de unión y cada nodo en el media y todas las ramas, hay 10 posibles lugares que podemos ir. Así que hay 10 punteros de cada lugar. 

Y aquí es donde tries pueden obtener una poco intimidante para alguien quién no tiene una gran cantidad de experiencia en ciencias de la computación antes. Pero intentos son realmente bastante impresionante. Y si usted tiene la oportunidad de trabajar con ellos y que está dispuesto a excavar en y experimentar con ellos, son realmente muy interesante estructuras de datos para trabajar. Si queremos insertar un elemento en el trie, todo lo que tiene que hacer es construir el camino correcto desde la raíz a la hoja. Esto es lo que cada paso a lo largo de el camino podría ser similar. Vamos a definir un nuevo datos estructura para un nuevo nodo llamado un trie. 

Y dentro de esos datos estructura hay dos piezas. Vamos a almacenar el nombre de una universidad. Y vamos a almacenar una matriz de punteros a otros nodos del mismo tipo. Así, de nuevo, esto es que especie del concepto de todas partes somos, a las 10 posibles lugares que podemos ir. Si vemos un 0, bajamos esta rama. Si vemos un 1, esta rama, y así sucesivamente y así sucesivamente y así sucesivamente. Si decimos 9, bajamos esta rama. Así que en cada punto de unión, podemos ir 10 lugares posibles. Así que cada nodo debe contener 10 punteros a otros nodos, a otros 10 nodos. 

Y los datos que estamos almacenando es sólo el nombre de la universidad. Así que vamos a construir un trie. Vamos a insertar un par de elementos en nuestra trie. Así que en la parte superior, este es nuestro nodo raíz. Esta es, probablemente, va a ser algo vas globalmente declare. Y usted va a mantener globalmente un puntero a este nodo siempre. 

Usted va a decir, es igual a la raíz, y ya está va a malloc mismo nodo trie. Y nunca vas tocar la raíz de nuevo. Cada vez que desee comenzar a navegar a través de, configura otro puntero igual a la raíz, como trav, que es el ejemplo que utilizar en muchas de mis videos aquí en pilas y colas y listas de enlaces y así sucesivamente. 

Se establece otro puntero llamada trav de recorrido. Y utiliza trav para navegar a través de la estructura de datos. Así que vamos a ver cómo esto podría mirar. Así que ahora mismo, lo que no un nodo parece? Bueno, al igual que nuestros datos declaración de estructura indicada, tenemos una cadena, que en este caso es vacía. No hay nada aquí. 

Y un conjunto de 10 indicadores. Y en este momento, sólo tienen 1 nodo en este trie. No hay nada más en él. Así que todos los 10 de los punta punteros a NULL. Eso es lo que indica el rojo. 

Vamos a insertar la cadena de Harvard. Vamos a insertar la Universidad de Harvard en este trie, que fue fundada en el año 1636. Queremos usar la llave, 1636, para decirnos dónde estamos va a almacenar Harvard en el trie. Ahora, ¿cómo podemos hacer eso? 

Podría ser algo como esto. Comenzamos en la raíz. Y tenemos estos 10 lugares que podemos ir. La raíz es igual que cualquier otro nodo del trie. Hay 10 lugares que podemos ir desde aquí. 

¿A dónde vamos, probablemente queremos para ir si la clave es 1636? No hay realmente dos opciones. Correcto. Podemos construir la llave de derecha a izquierda y comenzar con 6. O podríamos construir la llave de izquierda a derecha y comenzar con 1. 

Es probablemente más intuitivo como un ser humano entender que va a simplemente vaya a la izquierda a derecha. Y por lo que si quiero insertar Harvard en este trie, Probablemente Quiero empezar comenzando en la raíz, mirando mis 10 opciones delante de mí, y diciendo: Yo quiero ir por el camino 1. OK. 

Ahora, 1 camino es actualmente nulo. Así que si quiero continuar por ese camino para insertar este elemento en el trie, Tengo que malloc un nuevo nodo, tienen 1 Señalo allí, y entonces estoy listo para salir. 

Así que, básicamente, estoy en una punto en el que estoy de pie en la raíz del árbol o la trie y hay 10 sucursales. Pero cada rama tiene una puerta de en frente de ella. Correcto. Porque no hay nada más que hay. No paso seguro. Eso significa que no hay nada por cualquiera de esas ramas. Si quiero empezar a construir algo, quiero quitar la puerta. Quiero quitar la puerta frente al número 1. Y quiero caminar por eso. Y yo quiero construir otro lugar para mí para ir. 

Y eso es lo que he hecho aquí. Así que 1 ya no apunta a null. He dicho que es seguro ir por aquí ahora. Yo construí otro nodo. Y cuando llegue a ese nodo, I tener otra decisión que tomar. ¿Dónde voy a ir de aquí? 

Bueno, yo ya he pasado por el 1. Así que ahora, probablemente, quiero ir por la 6. Correcto. Una vez más, tengo 10 lugares que puedo elegir. Así que ahora vamos a ir hacia abajo el número 6. Así que puedo borrar la puerta delante del número 6. Y entro ahí abajo. Y voy a construir otro nodo. Y he llegado a otro punto de unión. 

Una vez más, tengo 10 opciones de donde puedo ir. Me he mudado de 1 a 6. Así que ahora, probablemente, quiero ir a la 3. 3, no hay ningún lugar que puedo ir. Así que tengo que limpiar el camino y construirme un nuevo espacio. Y después de 3, ¿por dónde quiero ir? Quiero bajar 6. 

Y, de nuevo, tuve que despejar el camino para hacerlo. Así que ahora que he usado mi llave para insertar crear nodos y empezar a construir este trie. He empezado en la raíz. He ido hasta 1636. Y ahora estoy en la parte inferior allí en ese nodo. Y usted puede ser capaz de verlo en su pantalla. 

Ha resaltado en amarillo. Ahí es donde actualmente soy. Mi llave está hecho. He agotado todas las posiciones de la llave. Así que no puedo ir más lejos. Así que en este punto, todo lo que realmente necesita hacer es decir, en Aceptar. Es como especie de mira hacia el suelo, si estás imaginando a ti mismo ya que este tipo de ruta con diferentes conexiones. Ordenar de mirar hacia abajo y una especie de rociar pintura de Harvard en el suelo. Ese es el nombre de esta. Saber que es lo que está en este lugar. Si empezamos en la raíz y bajamos 1 y luego 6 y luego 3 y luego 6, ¿dónde estamos? Bueno, si miramos hacia abajo y vemos Harvard, entonces sabemos que Harvard era fundada en 1636 con sede en el camino estamos implementando esta estructura de datos. Así que era de esperar sencillo. Vamos a hacer dos inserciones más. Y es de esperar que va a ayudar a ver este hecho dos veces más. 

Ahora, vamos a insertar otra universidad. Vamos a insertar Yale en este trie. Yale fue fundada en 1701. Así que vamos a empezar en el raíz, como siempre lo hacemos. Y nos pusimos un puntero recorrido. Vamos a usar eso para moverse a través de. Lo primero que queremos hacer es ir por el camino 1. Ese es el primer dígito de la llave. Afortunadamente, sin embargo, no lo hacemos tener que hacer ningún trabajo en esta ocasión. La ruta 1 ya ha sido aprobado. Me aclaré previamente cuando fue la inserción de la Universidad de Harvard en 1636. Así que me puedo mover con seguridad abajo 1 y acaba de ir allí. Si se puede mover por el 1. 

Ahora, sin embargo, yo quiero ir a 7. Me aclaré la forma a las 6. Sé que puedo con seguridad continuar por el camino 6. Pero necesito para continuar en el camino 7. Entonces, ¿qué tengo que hacer? Bueno, al igual que antes, sólo necesito para despejar la puerta, salir del camino, y construir un nuevo nodo de la ruta 7. Al igual que este. 

Así que ahora me he mudado 1 y 7. Y ahora cuenta, yo soy una especie de esta nueva subrama. Correcto. Todo lo demás de 16 , yo no me preocupo. No voy a hacer nada 16. Estoy haciendo 17 cosas. 

Así que ahora desde el 17 en adelante, tengo que especie de abrir nuevos caminos aquí. El siguiente dígito mi clave es 0. Yo claramente no puedo llegar a ninguna parte. Acabo de construir este nodo. Así que sé que no hay caminos a seguir de aquí. Así que tengo que hacer uno yo mismo. 

Así que malloc un nuevo nodo y tienen 0 punto allí. Y a continuación, una vez más, me malloc un nuevo nodo y tienen un punto allí. Una vez más, he agotado mi llave, 1701. Así que miro hacia abajo y yo pintura de aerosol de Yale. Ese es el nombre de este nodo. 

Y ahora si alguna vez necesito para ver si Yale Es en este trie, empiezo en la raíz, Voy por 1701, y miro hacia abajo. Y si veo aerosol Yale pintada en el suelo, a continuación, Sé Yale existe en este trie. Vamos a hacer una más. Vamos a insertar Dartmouth en esto trie, que fue fundada en 1769. 

Comience en la raíz de nuevo. Mi primer dígito de mi clave es 1. Me puedo mover con seguridad por ese camino. Que ya existe. El siguiente dígito de mi clave es 7. Me puedo mover con seguridad por ese camino. Existe también. 

Mi siguiente es 6. Desde aquí, desde donde actualmente soy en amarillo allí en ese nodo central, 6 está actualmente bloqueado apagado. Si quiero ir por ese camino, Tengo que construir yo mismo. Así que voy a malloc un nuevo nodo y tienen 6 puntos allí. Y entonces, una vez más, estoy caminos por abrir aquí. 

Así que malloc un nuevo nodo para que desde ese número ruta node-- 9-- y entonces ahora si viajo 1769, y miro hacia abajo. No hay nada actualmente aerosol pintado allí. Puedo escribir Dartmouth. Y he insertado Dartmouth en el trie. 

Así que esa es la inserción cosas en el trie. Ahora queremos buscar cosas. ¿Cómo buscamos cosas en el trie? Bueno, es más o menos la misma idea. Ahora sólo utilizamos los dígitos de la clave para ver si podemos navegar desde la raíz hacia donde queremos ir en el trie. 

Si llegamos a un callejón sin salida en cualquier momento, a continuación, sabemos que no puede existe ese elemento o de lo que lo haría camino ya se han despejado. Si lo hacemos todo el camino hasta Al final, todo lo que tiene que hacer es mirar hacia abajo y ver si eso es el elemento que estamos buscando. Si lo es, el éxito. Si no lo es, fallar. 

Así que vamos a la búsqueda para Harvard en este trie. Comenzamos en la raíz. Y, de nuevo, vamos a crear un puntero recorrido hacer nuestros movimientos para nosotros. Desde la raíz sabemos que el primer lugar tenemos que ir es 1, podemos hacer eso? Si podemos. Si existe segura. Podemos ir allí. 

Ahora, el siguiente lugar al que hay que ir es 6. ¿Existe la ruta 6 desde aquí? Sí, lo hace. Podemos ir por el camino 6. Y terminamos aquí. 

¿Podemos ir por el camino de 3 desde aquí? Bueno, resulta que, sí, que existe también. Y podemos conseguir en el camino 6 desde aquí? Si podemos. 

Todavía no hemos contestado la cuestión todavía. Todavía hay una más paso, que es ahora tenemos que mirar hacia abajo y ver si eso es actually-- si estamos en busca de Harvard, es que lo que encontramos después de que agotamos la clave? En el ejemplo que estamos utilizando aquí, los años son siempre cuatro dígitos. Pero es posible que esté utilizando el ejemplo en el que usted está guardando un diccionario de palabras. 

Y así, en lugar de tener 10 punteros para mi ubicación, es posible que tenga 26. Uno para cada letra del alfabeto. Y hay algunas palabras como murciélago, que es un subconjunto de lote, por ejemplo. Y por lo que incluso si se llega a la final de la llave y se mira hacia abajo, puede que no vea lo que estas buscando. 

Así que siempre hay que recorrer todo el camino y luego si usted fuera capaz de éxito para recorrer todo el camino, mirar hacia abajo y realice una confirmación final. ¿Eso es lo que estoy buscando? Bueno, yo miro hacia abajo después de comenzar en la parte superior y yendo 1.636. Miro hacia abajo. Veo Harvard. Así que, sí, lo logré. ¿Y si lo que estoy buscando no está en el trie, sin embargo. ¿Qué pasa si estoy buscando Princeton, que fue fundada en 1746. Y así, 1746 se convierte en la llave para navegar por el trie. Bueno, me pongo en la raíz. Y el primer lugar quiero que va por el camino 1. ¿Puedo hacerlo? Si puedo. 

¿Puedo ir por el camino de 7 a partir de ahí? Si, yo puedo. Que existe también. Pero puedo ir por el camino 4 de aquí? Eso es como pedirle a la pregunta, ¿puede Procedo por ese pequeño cuadrado que he resaltado en amarillo? No hay nada allí. Correcto. 

No hay manera de avanzar por el camino 4. Si Princeton fue en este trie, que 4 habría sido despejado para nosotros ya. Y así, en este punto hemos llegado a un callejón sin salida. No podemos ir más allá. Y así se puede decir, en definitiva, no. Princeton no existe en este trie. 

Entonces, ¿qué significa todo esto? Correcto. Hay mucho que hacer aquí. Hay punteros de todo el lugar. Y, como se puede ver simplemente a partir del diagrama, hay una gran cantidad de nodos que son una especie de volar alrededor. Pero note cada vez que queríamos comprobar si había algo en el trie, sólo tuvimos que hacer 4 movimientos. 

Cada vez que queríamos insertar algo en el trie, tenemos que hacer 4 movimientos, posiblemente mallocing algunas cosas en el camino. Pero como vimos cuando nos insertamos Dartmouth en el trie, a veces algunos de la ruta podría ya ser limpiado para nosotros. Y así como nuestra trie hace más grande y más grande, tenemos que hacer menos trabajo cada vez insertar nuevas cosas porque ya hemos construido una gran cantidad de la sustancia intermedia ramas en el camino. Si tan sólo alguna vez tenemos que mirar 4 cosas, 4 es sólo una constante. Realmente estamos acercando tipo de inserción constante de tiempo y la búsqueda constante de tiempo. La desventaja, por supuesto, es que este trie, como usted probablemente puede decir, es enorme. Cada uno de estos nodos ocupa mucho espacio. 

Pero esa es la disyuntiva. Si queremos realmente rápido inserción, deleción muy rápido, y las operaciones de búsqueda muy rápido, tenemos que tiene una gran cantidad de datos que vuelan alrededor. Tenemos que dejar de lado un montón de espacio y la memoria para que la estructura de datos existir. 

Y eso es el equilibrio. Pero parece que podría haber encontrado. Podríamos haber encontrado que santo grial de las estructuras de datos con la inserción rápida, eliminación y búsqueda. Y tal vez esto va a ser un estructura de datos apropiada a utilizar para cualquier información estamos tratando de almacenar. Soy Doug Lloyd, esto es CS50.