⏱️ Lectura: 15 min
Cuando escribís prog en la paleta de comandos de VS Code y la lista se filtra al instante a program, progress y profile, no hay un hash table detrás: hay un trie, un árbol que indexa palabras letra por letra en vez de resumir la palabra completa en un número.
📑 En este artículo
Un trie (del inglés retrieval, aunque casi todos lo pronuncian try) es la estructura detrás del autocompletado de tu IDE, del corrector ortográfico de tu teléfono y de las tablas de ruteo IP que deciden por dónde sale cada paquete en internet. Esta guía lo explica desde cero, con código funcional en JavaScript y Python.
TL;DR
- Vas a entender cómo un trie indexa palabras letra por letra, sin usar hashing.
- Vas a implementar un trie desde cero en JavaScript con insertar, buscar y prefijos.
- Vas a construir un autocompletador real que devuelve sugerencias por prefijo en Python.
- Vas a saber cuándo un trie gana a un hash table y cuándo pierde en memoria.
- Vas a distinguir un trie de un radix tree (PATRICIA) y por qué existe la compresión de nodos.
- Vas a identificar los errores más comunes al implementar un trie en producción.
- Vas a poder explicar por qué el ruteo IP usa tries en vez de tablas hash.
Qué es un trie y por qué importa
Un trie es un árbol donde cada camino desde la raíz hasta un nodo representa un prefijo, y cada nodo marcado como fin de palabra representa una clave completa almacenada. La definición formal de Wikipedia lo describe como un árbol de búsqueda ordenado que usa las claves como cadenas de texto, donde la posición de un nodo en el árbol define con qué clave está asociado. A diferencia de un árbol binario de búsqueda, en un trie no se compara la clave completa contra cada nodo: se avanza un carácter a la vez.
La ventaja central es que la búsqueda no depende de cuántas palabras tenga el diccionario, depende solo de la longitud de la palabra buscada. Buscar casa en un trie con diez palabras o con diez millones de palabras toma el mismo número de pasos: cuatro, uno por cada letra. Esa propiedad, complejidad O(L) donde L es la longitud de la clave y no O(N) sobre el total de claves, es lo que hace al trie ideal para autocompletado, correctores ortográficos y sistemas donde el prefijo importa más que la igualdad exacta.
Un hash table, en cambio, resuelve bien la pregunta existe esta clave exacta, pero no responde eficientemente qué claves empiezan con este prefijo. Para eso tendrías que recorrer todas las claves del hash y filtrar una por una. Un trie responde esa segunda pregunta de forma nativa: te parás en el nodo del prefijo y recorrés todo lo que cuelga de ahí.
Cómo funciona un trie por dentro
Cada nodo de un trie tiene dos cosas: una colección de hijos, uno por cada carácter posible que puede seguir, y una marca booleana que indica si el camino hasta ese nodo forma una palabra completa. La raíz representa la cadena vacía. Insertar una palabra significa caminar carácter por carácter desde la raíz, creando nodos hijos cuando no existen, y marcar el último nodo como fin de palabra.
flowchart TD
raiz(("raiz")) --> c["c"]
c --> ca["a"]
c --> cu["u"]
ca --> car["r (car)"]
car --> care["e (care)"]
ca --> cat["t (cat)"]
cu --> cup["p (cup)"]El diagrama anterior muestra un trie con car, care y cat, más cup. Fijate que car y care comparten el mismo camino hasta la r, y ahí se separan: care sigue con una e extra, car ya termina ahí, en un nodo marcado como fin de palabra. Ese compartir-hasta-donde-se-pueda es la esencia del trie: cuantas más palabras compartan prefijo, menos memoria extra necesita el árbol por cada palabra nueva.
flowchart TD
A["Inicio: insertar palabra"] --> B["nodo = raiz"]
B --> C{"Quedan letras en la palabra?"}
C -- "si" --> D["tomar siguiente letra"]
D --> E{"El nodo tiene hijo con esa letra?"}
E -- "no" --> F["crear nodo hijo"]
E -- "si" --> G["avanzar al nodo hijo"]
F --> G
G --> C
C -- "no" --> H["marcar nodo actual como fin de palabra"]El algoritmo de inserción es siempre el mismo bucle: por cada carácter de la palabra, preguntar si el nodo actual ya tiene un hijo con ese carácter. Si no lo tiene, lo crea. Si lo tiene, avanza. Al llegar al final de la palabra, marca el nodo actual como fin de palabra. La búsqueda de una palabra completa hace exactamente el mismo recorrido, pero en vez de crear nodos, falla si un carácter no tiene el hijo correspondiente. La búsqueda de un prefijo es idéntica, salvo que no exige que el nodo final esté marcado como fin de palabra.
Ejemplos prácticos: código progresivo
El primer ejemplo implementa lo mínimo indispensable: insertar palabras y confirmar si una palabra existe. El segundo agrega la parte que realmente usás todos los días: sugerencias por prefijo, como el autocompletado de una barra de búsqueda.
class TrieNode {
constructor() {
this.children = new Map();
this.esFinDePalabra = false;
}
}
class Trie {
constructor() {
this.raiz = new TrieNode();
}
insertar(palabra) {
let nodo = this.raiz;
for (const letra of palabra) {
if (!nodo.children.has(letra)) {
nodo.children.set(letra, new TrieNode());
}
nodo = nodo.children.get(letra);
}
nodo.esFinDePalabra = true;
}
buscar(palabra) {
let nodo = this.raiz;
for (const letra of palabra) {
if (!nodo.children.has(letra)) return false;
nodo = nodo.children.get(letra);
}
return nodo.esFinDePalabra;
}
}
const diccionario = new Trie();
diccionario.insertar("casa");
diccionario.insertar("caso");
console.log(diccionario.buscar("casa")); // true
console.log(diccionario.buscar("cas")); // falseEste trie usa un Map en vez de un array fijo de 26 posiciones, para no desperdiciar memoria si trabajás con acentos, ñ o unicode. buscar(cas) devuelve false porque cas nunca se marcó como fin de palabra, aunque el camino c-a-s sí existe en el árbol: esa es la clase de error que confunde a quien recién empieza con tries.
class NodoTrie:
def __init__(self):
self.hijos = {}
self.fin_palabra = False
class Autocompletador:
def __init__(self):
self.raiz = NodoTrie()
def insertar(self, palabra):
nodo = self.raiz
for letra in palabra:
nodo = nodo.hijos.setdefault(letra, NodoTrie())
nodo.fin_palabra = True
def _recolectar(self, nodo, prefijo, resultados, limite):
if len(resultados) >= limite:
return
if nodo.fin_palabra:
resultados.append(prefijo)
for letra, hijo in nodo.hijos.items():
self._recolectar(hijo, prefijo + letra, resultados, limite)
def sugerir(self, prefijo, limite=5):
nodo = self.raiz
for letra in prefijo:
if letra not in nodo.hijos:
return []
nodo = nodo.hijos[letra]
resultados = []
self._recolectar(nodo, prefijo, resultados, limite)
return resultados
buscador = Autocompletador()
for palabra in ["python", "pytest", "pyplot", "java", "javascript"]:
buscador.insertar(palabra)
print(buscador.sugerir("py")) # ['python', 'pytest', 'pyplot']sugerir(prefijo) primero camina hasta el nodo del prefijo, igual que buscar, y desde ahí hace una recorrida en profundidad (DFS) recolectando todas las palabras completas que cuelgan de ese punto. Este es literalmente el algoritmo que corre detrás de cualquier barra de búsqueda con sugerencias en tiempo real.
Cómo empezar: implementar y usar un trie paso a paso
No hace falta instalar nada para probar los ejemplos anteriores: node autocomplete.js o python autocomplete.py corren directo. Para un caso real, seguí estos pasos:
- Definí el alfabeto: ¿tu clave usa solo minúsculas a-z, o necesitás soportar tildes, ñ y unicode completo? Si es lo segundo, usá un Map o dict para los hijos en vez de un array fijo de 26 posiciones.
- Insertá el diccionario completo al arrancar: la inserción es O(L) por palabra, pero repetirla en cada request es trabajo desperdiciado.
- Exponé dos métodos públicos: buscar(clave) para existencia exacta, y sugerir(prefijo, limite) para autocompletado. Limitá siempre el número de resultados: un prefijo de una sola letra puede colgar miles de palabras.
- Usá una librería madura si existe: en Python, pygtrie (mantenida por Google) implementa tries con soporte para claves compuestas por listas, no solo strings. Se instala con pip install pygtrie.
Para confirmar que tu trie realmente evita el recorrido completo, medí cuántos nodos visita sugerir(): debería ser igual a la longitud del prefijo más el tamaño del subárbol resultante, nunca el tamaño total del diccionario. Un contador simple dentro de _recolectar alcanza para verificarlo.
Casos de uso reales
Autocompletado y corrección ortográfica: cualquier barra de búsqueda que sugiere mientras escribís, sea un IDE, un buscador de comandos o el teclado de un teléfono, recorre un trie o una variante comprimida de uno. El motor de búsqueda de Apache Lucene, base de Elasticsearch y Solr, usa autómatas de estados finitos (FST) que son, en esencia, tries comprimidos y ordenados alfabéticamente.
Ruteo IP: las tablas de ruteo de un router no buscan una IP exacta, buscan el prefijo de red más largo que coincide (longest prefix match). Cada bit de la dirección IP funciona como un carácter de un alfabeto binario, y el router camina un trie binario para decidir por qué interfaz de red sale el paquete.
Diccionarios de juegos de palabras y correctores: resolutores de Scrabble, verificadores ortográficos y los sistemas T9 de teclados antiguos usan tries para validar si una secuencia de letras puede seguir formando una palabra válida, sin recorrer el diccionario completo en cada tecla.
💡 Tip: si tu prefijo típico tiene pocos caracteres pero el diccionario es enorme, un trie gana claramente. Si tus claves son en su mayoría aleatorias y solo buscás igualdad exacta, un hash table simple suele ser más rápido y más simple de mantener.
Errores comunes y buenas prácticas
- Olvidar la marca de fin de palabra: si insertás casa y buscás cas, un trie mal implementado puede devolver true solo porque el camino existe. Siempre distinguí el camino existe de esto es una palabra completa.
- Usar un array fijo de 26 posiciones con texto en español: eso excluye tildes y ñ directamente, o te obliga a normalizar el texto antes de insertar, lo cual puede ser válido, pero tiene que ser una decisión explícita, no un error accidental.
- No limitar los resultados de sugerir(): un prefijo corto en un diccionario grande puede colgar decenas de miles de palabras. Sin un límite, o sin ordenar por frecuencia de uso, el recorrido completo se vuelve costoso aunque el algoritmo en sí sea eficiente.
- Usar un trie para claves aleatorias sin prefijos compartidos: ahí un trie desperdicia memoria, un nodo por dígito sin nada que compartir, y un hash table simple gana en todos los frentes.
- No comprimir cadenas de un solo hijo: un trie ingenuo crea un nodo por cada carácter aunque no haya ninguna bifurcación. Para diccionarios grandes con poco solapamiento, eso es memoria desperdiciada; la solución es un radix tree.
Comparativa con alternativas
| Estructura | Cuándo usarla | Ventaja | Limitación |
|---|---|---|---|
| Trie | Autocompletado, prefijos, diccionarios | Búsqueda por prefijo nativa en O(L) | Un nodo por carácter: memoria alta con muchas palabras únicas |
| Hash table | Igualdad exacta, claves sin relación entre sí | Búsqueda y escritura O(1) en promedio | No resuelve búsquedas por prefijo sin recorrer todo |
| Árbol binario de búsqueda balanceado | Rangos ordenados, iteración en orden | Recorrido ordenado nativo en O(log N) | Compara la clave completa en cada nodo: más lento que un trie para prefijos |
| Radix tree (PATRICIA trie) | Tablas de ruteo IP, diccionarios muy grandes | Comprime cadenas sin bifurcación: menos nodos que un trie plano | Implementación más compleja que un trie ingenuo |
Profundizando
El problema práctico de un trie ingenuo es que, si tenés muchas palabras largas con poco solapamiento, terminás con una cadena larga de nodos de un solo hijo cada uno, gastando un nodo entero por letra sin ninguna bifurcación real. Un radix tree o PATRICIA trie resuelve esto colapsando esas cadenas en un único nodo que almacena el substring completo, no un solo carácter.
flowchart LR
subgraph "Trie plano"
A1["c"] --> A2["a"]
A2 --> A3["r"]
A3 --> A4["r"]
A4 --> A5["o"]
end
subgraph "Radix tree comprimido"
B1["carro"]
endEsa compresión es la razón por la que las tablas de ruteo IP reales no usan un trie binario ingenuo bit por bit: usan variantes tipo PATRICIA, donde un solo nodo puede representar un bloque completo de bits sin bifurcación, reduciendo drásticamente la cantidad de nodos a recorrer y la memoria usada.
Otra variante es el trie de sufijos, o su versión comprimida, el árbol de sufijos, que en vez de indexar palabras completas indexa todos los sufijos de un texto. Eso permite responder si una subcadena aparece en el texto en tiempo proporcional al largo de la subcadena buscada, sin importar qué tan largo sea el texto original: es la base de herramientas de búsqueda genómica y de algunos motores de búsqueda de código fuente.
📌 Nota: un trie con un Map por nodo en JavaScript tiene un costo real de memoria: cada Map vacío consume memoria propia. Para diccionarios de millones de palabras en producción, medí el uso de memoria real con tu motor de JavaScript o Python antes de asumir que un trie ahorra memoria solo por compartir prefijos; a veces un radix tree es más compacto.
📖 Resumen en Telegram: Ver resumen
Tu próximo paso: agregale a la clase Autocompletador un método que ordene sugerir(prefijo) por frecuencia de uso en vez de por orden alfabético, guardando un contador en cada nodo de fin de palabra.
Preguntas frecuentes
¿Qué significa la palabra trie?
Viene de retrieval, recuperación en inglés. Edward Fredkin propuso el término en 1960 para distinguirlo de tree, aunque en la práctica casi todo el mundo lo pronuncia igual que try.
¿Cuál es la complejidad de búsqueda en un trie?
O(L), donde L es la longitud de la clave buscada. No depende de cuántas claves totales tenga el trie, a diferencia de un árbol binario de búsqueda balanceado, que es O(log N).
¿Un trie ocupa más memoria que un hash table?
Depende de cuánto solapan las claves. Si comparten muchos prefijos, como palabras de un mismo idioma, un trie puede ser más compacto. Si las claves son mayormente aleatorias sin prefijos comunes, un trie desperdicia memoria en nodos que casi no se reutilizan.
¿Qué diferencia hay entre un trie y un árbol binario de búsqueda?
Un árbol binario de búsqueda compara la clave completa en cada nodo para decidir ir a la izquierda o a la derecha. Un trie no compara claves: usa cada carácter para decidir a qué hijo bajar, y puede tener más de dos hijos por nodo.
¿Dónde se usan los tries en el mundo real?
Autocompletado de barras de búsqueda y de comandos, correctores ortográficos, tablas de ruteo IP como radix trees, motores de búsqueda de texto que usan FSTs derivados de tries, y diccionarios de juegos de palabras.
¿Cómo optimizo la memoria de un trie muy grande?
Usá un radix tree (PATRICIA trie) para comprimir cadenas sin bifurcación en un solo nodo, o cambiá los hijos de cada nodo de un array fijo a un Map o dict si tu alfabeto es grande pero disperso.
Referencias
- Wikipedia: Trie: definición formal, historia del término y propiedades de complejidad.
- Wikipedia: Radix tree: la variante comprimida (PATRICIA) usada en tablas de ruteo IP.
- Apache Lucene: motor de búsqueda que usa autómatas de estados finitos derivados de tries para indexar texto.
- Wikipedia: Autocomplete: contexto sobre los sistemas de sugerencia que se apoyan en estructuras como el trie.
📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.
Imagen destacada: Foto de Rahul Mishra en Unsplash
0 Comentarios