¿Qué es un Trie?

Un trie (pronunciado "try", abreviatura de retrieval o recuperación) es una estructura de datos en forma de árbol diseñada para almacenar y buscar cadenas por sus caracteres. Cada arista del árbol está etiquetada con un solo carácter, y cada camino desde la raíz hasta un nodo marcado deletrea una palabra almacenada.

Esa estructura hace que las consultas de prefijos sean extremadamente rápidas. Comprobar si el trie contiene alguna palabra que comience con "car" son solo tres búsquedas de caracteres desde la raíz, sin importar cuántos miles de palabras estén almacenadas. Los tries son el motor detrás de funciones como el autocompletado, el corrector ortográfico y las tablas de enrutamiento IP.

Cada nodo en el trie contiene dos elementos de estado:

• children: un mapa de un carácter al siguiente TrieNode.
• isEndOfWord: una bandera que es true cuando el camino desde la raíz hasta este nodo deletrea una palabra completa que fue insertada.

Las cinco operaciones principales en un trie son:

1. Insert: Añadir una palabra, creando cualquier nodo faltante en el camino.
2. Search: Comprobar si una palabra completa está almacenada.
3. StartsWith: Comprobar si alguna palabra almacenada tiene el prefijo dado.
4. Delete: Eliminar una palabra y podar cualquier rama muerta.
5. WordCount: Contar cuántas palabras distintas están almacenadas.

¡Vamos a construir una clase Trie!