Árbol trie

Implementación de la estructura de datos Trie en varios lenguajes de programación

Implementación de Trie en Python

clase TrieNodo: 
    def __init__(self): self.children = collections.defaultdict(TrieNode) self.is_end = False

Uso de la estructura de datos Trie en Java

class TrieNode { public TrieNode[] children = new TrieNode[26]; public boolean isEnd;

Guía paso a paso para la implementación de Trie en Java

Paso

class Trie { TrieNode root; Trie() { root = new TrieNode(); } } Paso

void insert(String word) { TrieNode node = root; for (int i=0;

Sigue sistemáticamente patrones similares para crear otros métodos. Por ejemplo, la función de búsqueda requeriría recorrer el Trie de forma similar a la función de inserción, pero devolvería una bandera "isEnd" una vez alcanzado el final de la palabra de entrada; la función startsWith requeriría de nuevo recorrer el Trie a lo largo de los caracteres del prefijo de entrada y devolvería true una vez alcanzado el final del prefijo, sin comprobar la bandera "isEnd".

Nota: El índice de la matriz viene determinado por el valor ASCII del carácter.
 La complejidad temporal constante de las operaciones Trie se deriva de este enfoque: no importa cuántas entradas tenga una Trie, sólo se necesita \( O(k) \) complejidad temporal para comprobar si una cadena de longitud \( k \) está en la Trie. Esto hace que Trie sea extremadamente eficiente para determinadas operaciones. 
 Aplicaciones prácticas de Trie en 
informática Las estructuras de datos Trie tienen diversas aplicaciones en informática, en gran parte debido a su configuración única y a su capacidad de recuperación rápida. Utilizando Trie, se pueden rectificar rápidamente cuestiones relacionadas con la búsqueda de cadenas, las funciones de autocompletar y los mecanismos de corrección ortográfica. Las siguientes secciones profundizan en los detalles de estas aplicaciones y demuestran cómo Trie simplifica sustancialmente dichas operaciones.
 Buscar con Trie: el algoritmo de búsqueda 
de Trie Una de las principales ventajas de la estructura de datos Trie es su eficacia de búsqueda. La operación de búsqueda en Trie consiste en recorrer desde el nodo raíz hasta un nodo concreto que represente una clave de búsqueda determinada (una cadena). Cabe destacar que las operaciones de búsqueda en una Trie dependen de la longitud de la palabra, no del número de palabras almacenadas en la Trie. Esto contrasta con otras estructuras de datos en las que la complejidad de la búsqueda depende del número de entradas de la estructura de datos. Una operación de búsqueda en Trie sigue la siguiente secuencia:
 
 Inicializa el recorrido en el nodo raíz. 
 Para cada carácter de la clave de búsqueda, 
 
 Recorre hasta el nodo hijo correspondiente al carácter 
 
actual 
 
 Si no existe tal nodo hijo, devuelve un fallo o "no encontrado". 
 
 
 Al final del recorrido de la clave de búsqueda, si el nodo actual está marcado como final de palabra, devuelve un éxito o 'encontrado'. 
 En caso contrario, si el nodo actual no está marcado como final de palabra, devuelve un fallo o "no encontrado". 


Todo este proceso puede realizarse en \( O(n) \) tiempo, donde \( n \) es la longitud de la clave de búsqueda, lo que representa una situación óptima para listas largas de entradas.
 Un ejemplo de algoritmo de búsqueda 
en trie Consideremos un trie que almacena las palabras "try", "tried", "tries" y "trie", y quieres buscar la palabra "tries". He aquí una forma concisa de lo que ocurre:
function trie_buscar(raíz, clave) { let nivel; let longitud = longitud.clave; let índice; let pCrawl = raíz; for (nivel = 0; nivel < longitud; nivel++) { índice = clave[nivel] - 'a'; if (!pCrawl.children[index]) return false; pCrawl = pCrawl.children[index]; } if (pCrawl != null && pCrawl.isEndOfWord) return true; return false; }
Con esta función, puedes buscar en una estructura Trie en la que cada carácter de una palabra sirve de clave en la matriz children[] del nodo. El proceso finaliza cuando encuentra la última letra de la palabra buscada marcada como final de palabra (isEndOfWord == true) o explora todos los caracteres sin encontrar la clave.
 Uso de Trie en funciones 
de autocompletar La función de autocompletar, un elemento frecuente en el mundo digital actual, es un ejemplo excelente de la aplicación práctica de Trie. Desde la búsqueda en buscadores web hasta la escritura en editores de texto, la función de autocompletar ahorra tiempo y esfuerzo al predecir posibles terminaciones de palabras basándose en la entrada del usuario. El componente central de la función de autocompletar es la estructura de datos Trie. Cuando un usuario teclea determinados caracteres, el sistema completa el recorrido hasta llegar al último nodo de caracteres tecleado. A continuación, el sistema devuelve todos los descendientes de este nodo como posibles complementos de palabras. Este procesamiento es posible gracias a la propiedad "prefijo" de Trie, en la que todos los descendientes de un nodo comparten un prefijo común de la cadena asociada a ese nodo. Esto permite modificar el algoritmo de búsqueda de Trie para las funciones de autocompletar, garantizando una compleción de palabras eficaz y rápida.
 Trie en los mecanismos de 
corrección ortográfica Al igual que el autocompletado, los algoritmos de corrección ortográfica también se benefician en gran medida de las estructuras de datos de Trie. Los correctores ortográficos pueden detectar rápidamente las faltas de ortografía y sugerir correcciones, y una parte importante de esta eficacia proviene del uso de estructuras de datos Trie. Mediante esta estructura, se puede validar rápidamente la existencia misma de una palabra en un diccionario, que es la lógica subyacente utilizada en estas funciones para determinar si su ortografía es correcta o no. En algunos sistemas avanzados de corrección ortográfica, también se utilizan Trie para sugerir correcciones a las palabras mal escritas. Esto se hace buscando palabras en el Trie que estén a una cierta "distancia" de la palabra mal escrita (por ejemplo, añadiendo, quitando o cambiando unos pocos caracteres). Esta "distancia" suele definirse mediante un algoritmo como el de la distancia de Levenshtein. En un entorno así, la rapidez y la franqueza de Trie las convierten en una opción excelente para facilitar una revisión ortográfica y una autocorrección rápidas y eficaces.
 Comparación de Trie y otras estructuras 
de datos Para comprender la importancia y la singularidad de Trie, resulta útil compararla con otras estructuras de datos comunes. Esta sección examina Trie en comparación con
 hashmap 
y arroja luz sobre dónde se sitúa Trie en términos de eficiencia. Trie
 vs Hashmap: 
 Una Comparación Detallada 
Trie y Hashmap, dos potentes estructuras de datos, proporcionan cada una ventajas significativas, dependiendo de los casos de uso y de la naturaleza de los datos con los que estés tratando. En particular, la decisión entre ambas recae en algunos parámetros clave, como se explica a continuación.
 Comprender las diferencias entre Hashmap y 
Trie
Hashmap, una colección desordenada de pares clave-valor, ofrece operaciones eficaces de búsqueda, inserción y eliminación. Pero estas operaciones dependen en gran medida de la calidad de la función hash y del factor de carga. Los hashmaps son sumamente flexibles, ya que almacenan cualquier tipo de datos -números, caracteres, objetos- como claves y valores.
Sin embargo, los hashmaps no son adeptos a los problemas relacionados con las cadenas, en particular a las utilidades basadas en pref
ijos. En
cambio, un Trie, también conocido como árbol de prefijos, destaca cuando se trata de cadenas de caracteres. Los Trie almacenan caracteres como elementos, con rutas de la raíz a la hoja que constituyen cadenas de la colección. Esto hace que Trie sea eficiente para muchas operaciones, como la búsqueda de prefijos, de las que los hashmaps carecen intrínsecamente.



Aquí tienes una comparación exhaustiva: