>> KEVIN SCHMID: A veces, cuando la construcción de una programa, es posible que desee utilizar un
estructura de datos conocida como un diccionario.
A Mapas Diccionario teclas, que son generalmente cuerdas, a los valores, enteros,
caracteres, un puntero a un objeto, lo que queramos.
Es igual que los diccionarios normales Ese mapa palabras a través de las definiciones.
>> Diccionarios nos dan la capacidad de almacenar información
asociado con algo y buscarlo más tarde.
Así que ¿cómo podemos poner en práctica un Diccionario en, por ejemplo, el código C que podemos
utilizar en uno de nuestros programas?
Bueno, hay un montón de maneras en que podríamos implementar un diccionario.
>> Por un lado, podríamos utilizar una matriz que dinámicamente cambiar el tamaño o podríamos utilizar un
lista enlazada, tabla hash o un árbol binario.
Pero cualquier cosa que elijamos, debemos tener en cuenta la eficiencia y
el rendimiento de la aplicación.
Debemos pensar en el algoritmo utilizado para insertar y buscar elementos en
nuestra estructura de datos.
>> Por ahora, vamos a suponer que desee utilizar cadenas como claves.
Vamos a hablar de una de las posibilidades, una estructura de datos llamada trie.
Así que aquí está una representación visual de un trie.
>> A medida que la imagen sugiere, un trie es una estructura de datos en árbol con
nodos enlazados.
Vemos que hay claramente una raíz nodo con algunos enlaces que se extiende a
otros nodos.
Pero ¿qué significa cada nodo consiste?
Si asumimos que estamos almacenando claves con sólo caracteres alfabéticos y
no nos preocupamos por capitalización, he aquí una definición de un nodo que
será suficiente.
>> Un objeto cuyo tipo es struct nodo tiene dos partes
llamada de datos y los niños.
Hemos dejado la parte de datos como un comentario para ser sustituido por un componente
declaración al nodo de estructura es incorporado en un programa en C.
La parte de datos de un nodo puede ser un Valor booleano para indicar si
no el nodo representa la finalización de una clave de diccionario o podría ser un
cadena que representa la definición de una palabra en el diccionario.
>> Usaremos una cara sonriente para indicar cuando los datos está presente en un nodo.
Hay 26 elementos en nuestro array niños, un índice
por carácter alfabético.
Veremos el significado de este pronto.
>> Vamos a tomar una mirada más cercana del nodo raíz en nuestro diagrama, que no dispone de datos
asociado con él, como se indica por la ausencia de la cara sonriente en el
porción de datos.
Las flechas que se extienden desde las partes de los hijos de la matriz representan libre de nodos
punteros a otros nodos.
Por ejemplo, la flecha que se extiende desde el segundo elemento de niños
representa la letra B en clave de un diccionario.
Y en el diagrama más grande lo etiquetamos con una B.
>> Tenga en cuenta que en el diagrama más grande, cuando dibujar un puntero a otro nodo,
no importa donde la punta de flecha cumple que otro nodo.
Nuestro trie diccionario muestra contiene dos palabras, eso y zoom.
Vamos a ver un ejemplo de la búsqueda de datos para una clave.
>> Supongamos que queremos buscar el valor correspondiente para el baño clave.
Comenzaremos nuestra mirada hacia arriba en el nodo raíz.
Entonces vamos a tomar la primera letra de nuestra clave, B, y encontrar los correspondientes
detectar en nuestra serie los niños.
Observe que hay exactamente 26 puntos en la matriz, uno por cada letra de
el alfabeto.
Y tendremos los puntos representan la letras del alfabeto en orden.
>> Miraremos el segundo índice de entonces, índice de uno, para B. En general, si nos
tener algún carácter alfabético C que podría determinar el lugar correspondiente
en la matriz de los niños utilizando un cálculo como éste.
Podríamos haber utilizado niños más grandes matriz si queríamos ofrecer mirada de
teclas con una gama más amplia de caracteres, como la totalidad
Conjunto de caracteres ASCII.
>> En este caso, el puntero en nuestra serie los niños en
índice no es nulo.
Así que vamos a seguir buscando el baño de la clave.
Si alguna vez nos encontramos con un puntero nulo en el lugar adecuado en los niños
array mientras atravesamos los nodos, entonces vamos a tener que decir que
No hemos podido encontrar nada para esa tecla.
>> Ahora, vamos a tomar la segunda letra del la llave, A, y continuar siguiendo
punteros de esta manera hasta que llegar al final de la llave.
Si llegamos a la final de la llave sin golpear ningún callejones sin salida, punteros nulos,
como es el caso aquí, entonces sólo tiene que comprobar una cosa más.
¿Es esto realmente clave en el diccionario?
>> Si es así, hay que encontrar un valor, bien un icono de cara sonriente en nuestro diagrama donde
la palabra termina.
Si hay algo más almacenado con los datos, entonces podemos devolverlo.
Por ejemplo, el zoológico llave no está en el diccionario, a pesar de que podríamos tener
alcanzado el final de esta tecla sin golpear a un puntero nulo, mientras que
recorrer el trie.
>> Si tratamos de buscar el baño de tecla, el segundo para el índice de matriz del último nodo,
correspondiente a la letra H, se han celebrado un puntero nulo.
Así baño no está en el diccionario.
Y así un trie es único en que las teclas nunca se almacenan de manera explícita en
la estructura de datos.
Entonces, ¿cómo insertamos algo en un trie?
>> Vamos a insertar la llave zoológico en nuestra trie.
Recuerde que una cara sonriente en un nodo podría corresponder en el código a un simple
Valor booleano para indicar que el zoológico está en el diccionario o podría
corresponden a más información que nos desee asociar con el zoo clave,
como la definición de la palabra o alguna otra cosa.
En cierto modo, el proceso para insertar algo en un trie es similar a
buscar algo en un trie.
>> Vamos a empezar con el nodo raíz de nuevo, siguientes indicadores correspondientes a
las cartas de la llave.
Por suerte, hemos sido capaces de seguir punteros todo el camino hasta que llegamos a
el extremo de la llave.
Desde el zoológico es un prefijo de la palabra de zoom, que es un miembro de la
diccionario, que no es necesario asignar los nuevos nodos.
>> Podemos modificar el nodo para indicar que el camino de caracteres que conducen a
representa una tecla en el diccionario.
Ahora, vamos a tratar de insertar el BAÑO llave en el trie.
Empezaremos en el nodo raíz y seguir los punteros de nuevo.
Pero en esta situación, llegamos a un muerto terminar antes de que somos capaces de llegar a la
extremo de la llave.
Ahora, tendremos que asignar un nuevo nodos tendrán que asignar una nueva
nodo para cada restante carta de la llave.
>> En este caso, sólo tenemos asignar un nodo nuevo.
Entonces tendremos que hacer que el índice H hacer referencia a este nuevo nodo.
Una vez más, podemos modificar el nodo a indicar que la ruta de acceso de caracteres
dando lugar a que representa un clave en nuestro diccionario.
Vamos a razonar acerca de la asintótica complejidad de nuestros procedimientos para estos
dos operaciones.
>> Nos damos cuenta de que en ambos casos el número de los pasos de nuestro algoritmo se tomó
proporcional al número de letras en la palabra clave.
Eso es correcto.
Cuando se quiere buscar una palabra en una trie sólo tiene que recorrer
las letras una por una hasta que ya sea llegar al final de la palabra o
un callejón sin salida en el trie.
>> Y cuando se desea introducir una clave par en un trie valor utilizando el
procedimiento ya comentamos, el peor de los casos tendrá que asignar un nuevo nodo
para cada letra.
Y vamos a suponer que la asignación es una operación constante de tiempo.
Así que si suponemos que la longitud de la clave es delimitada por una constante fija, tanto
inserción y mirar hacia arriba son constantes operaciones de tiempo para un trie.
>> Si no hacemos esta suposición de que la longitud de la clave está limitada por una fijo
constante, entonces la inserción y mirar hacia arriba, en el peor de los casos, son lineales en el
longitud de la clave.
Note que el número de elementos almacenados en el trie no afecta a la mirada hasta
o el tiempo de inserción.
Sólo ha afectado por la longitud de la clave.
>> Por el contrario, la adición de entradas a, digamos, una tabla hash tiende a hacer
futuro mirar hacia arriba más lento.
Si bien esto puede sonar atractivo al principio, debemos tener en cuenta que un
complejidad asintótica favorables no significa que en la práctica los datos
estructura es necesariamente irreprochable.
También hay que considerar que para almacenar un palabra en un trie que necesitamos, en el peor de los casos
caso, un número de nodos proporcional a la longitud de la palabra en sí misma.
>> Tries tienden a utilizar una gran cantidad de espacio.
Eso está en contraste con una tabla hash, donde sólo necesitamos uno nuevo nodo a
almacenar algún par de valores clave.
Ahora, de nuevo, en teoría, gran espacio el consumo no parece ser un gran
hacer frente, sobre todo teniendo en cuenta que moderno computadoras tienen gigabytes y
gigabytes de memoria.
Pero resulta que aún tenemos que preocuparse por el uso de memoria y
organización por el bien de rendimiento, ya que las computadoras modernas
contar con mecanismos en el marco del campana para acelerar el acceso de memoria.
>> Sin embargo, estos mecanismos funcionan mejor cuando accesos de memoria se hacen en compacto
regiones o zonas.
Y los nodos de un trie podrían residir en cualquier lugar de ese montón.
Pero estas son las compensaciones que debemos considerar.
>> Recuerde que, al elegir un dato estructura para una determinada tarea,
debe pensar en qué tipo de operaciones de la estructura de datos tiene que
el apoyo y la cantidad de las prestaciones de cada uno de los
materia de operaciones a nosotros.
Estas operaciones pueden incluso extenderse más allá de simplemente
básica mirada y la inserción.
Supongamos que queremos implementar un tipo de la funcionalidad de autocompletar, y mucho
como motor de búsqueda de Google hace.
Es decir, devolver todas las llaves y valores que potencialmente
tener un prefijo dado.
>> Un trie es únicamente útil para esta operación.
Es sencillo para recorrer trie para cada carácter de
el prefijo.
Al igual que una operación de mirar hacia arriba, podríamos seguir punteros
carácter por carácter.
Luego, cuando llegamos a la final de la prefijo, podríamos recorrer la
porción restante de la estructura de datos desde cualquiera de las teclas más allá
este punto tiene el prefijo.
>> También es fácil obtener este anuncio en orden alfabético desde la
elementos de la matriz niños se ordenan alfabéticamente.
Así que espero que usted considere dar intentó el intento.
Soy Kevin Schmid, y esto es CS50.
>> Ah, este es el comienzo de la disminución.
Lo siento.
>> Huelga de cuatro.
Estoy fuera.
Lo siento.
Lo siento por hacer la persona que tiene que editar este se vuelva loco.
>> Lo siento.
Lo siento.
>> ALTAVOZ 1: Bien hecho.
Eso estaba muy bien hecho.