Estructura de Datos 2 Trabajo Práctico

Estructura de Datos 2

Trabajo Práctico

Prof: Ing. Roberto Sánchez

Definición y diferentes implementaciones.

Un Trie es un tipo de árbol utilizado para representar listas de palabras sobre un alfabeto finito. Los árboles Trie se introdujeron por primera vez a mediados de 1960 para implementar búsquedas rápidas en conjunto de datos pequeños. El nombre Trie nace de RETRIEVAL (recuperación).

Los Tries son una buena opción para representar conjuntos de palabras y proporcionan buenos resultados en cuanto al tiempo de búsqueda. Este será proporcional a la longitud de la palabra.

Implementación de Tries mediante Arreglos.

La idea es usar un array de punteros, donde cada casilla representa un símbolo del alfabeto. Así la raíz corresponderá al primer carácter de la palabra, luego este apunta a un nodo del Trie (que es otro arreglo de punteros) a la casilla donde se almacena el símbolo del alfabeto correspondiente al segundo carácter de la palabra, y así sucesivamente hasta llegar a la raíz. Es de acceso rápido pero desperdicia mucha memoria. La siguiente figura muestra esta idea:

[pic 1]

Implementación de Tries mediante Listas Enlazadas.

Cada nodo del árbol es una lista enlazada. Tiene menor costo de espacio pero disminuye el desempeño  para acceder a los hijos.

[pic 2]

Como representación de diccionarios.

Una aplicación frecuente de los tries es el almacenamiento de diccionarios, como los que se encuentran en los teléfonos móviles. Estas aplicaciones se aprovechan de la capacidad de los tries para hacer búsquedas, inserciones y borrados rápidos.

Los tries también son útiles en la implementación de algoritmos de correspondencia aproximada, como los usados en el software de corrección ortográfica.

Objetivos del Trabajo Práctico (20 puntos)

Realice un programa que implemente un árbol TRIE como un diccionario. El programa deberá realizar las siguientes acciones:

• Insertar palabras en el diccionario. Si la palabra ya existe el programa no hace nada.
• Saber si una palabra ingresada por el usuario está o no en el diccionario.
• Si el usuario ingresa un prefijo, el programa deberá listar todas las palabras del diccionario que empiecen con el prefijo ingresado.
• Leer desde un archivo externo las palabras del diccionario.
• Imprimir todos los prefijos de n letras.
• Implementar un menú en modo texto de manera que el usuario pueda elegir las acciones que quiera realizar y le de la oportunidad de salir del programa.

Forma de Entrega

El trabajo tendrá dos entregas una de cinco puntos (5) y u        na entrega final de quince puntos (15). En cada etapa se deben cumplir ciertos requisitos para lograr los puntos.

Primera Etapa (5 puntos)

Definición de las estructuras a utilizar (2 puntos)

Implementación de la función de Insertar (2 puntos)

Implementación de la función Imprimir todas las palabras del TRIE (1 punto)

...