Trie (también llamado prefix tree o digital tree) es una estructura de árbol donde cada nodo representa un carácter de una palabra. Las palabras se almacenan como caminos desde la raíz, compartiendo prefijos comunes.
Es ideal para búsqueda de palabras, autocompletado, y spell checkers.
Estructura
Cada nodo tiene:
- Un array/mapa de children (uno por carácter del alfabeto).
- Un flag
is_endque indica si este nodo termina una palabra.
Camino: raíz → c → a → r → is_end = true = palabra “car”.
Operaciones
| Operación | Complejidad | Descripción |
|---|---|---|
| Insert | O(L) | Recorre/crea nodos por cada carácter |
| Search | O(L) | Recorre nodos; verifica is_end |
| StartsWith | O(L) | Recorre nodos; no necesita is_end |
| Delete | O(L) | Borra nodos si no tienen más referencias |
Donde L = longitud de la palabra.
Ejemplo
Insertar car, cat, dog, doge:
(root)
/ \\
c d
/ \\ |\\
a a o o
/ \\ | |
r t g e
* * * *(* = is_end)
Prefix Search
Para startsWith("ca"): recorre c → a; si existe, todas las palabras bajo ese nodo tienen el prefijo.
Espacio
Worst-case: cada nodo tiene hasta ALPHABET_SIZE hijos. Para N palabras de longitud promedio L, espacio ≈ O(ALPHABET × N × L).
Optimización: usa Map<char, Node> en lugar de array fijo para alfabetos grandes o Unicode.
Comparación
| Estructura | Search | Insert | Prefix search | Espacio |
|---|---|---|---|---|
| Hash Table | O(L) | O(L) | No | O(N × L) |
| BST | O(L log N) | O(L log N) | No | O(N × L) |
| Trie | O(L) | O(L) | Sí | O(ALPHABET × N × L) |
Aplicaciones
- Autocompletado — Google Search, IDEs
- Spell checkers — diccionario de palabras válidas
- IP routing — longest prefix match (radix tree variant)
- Compression — Patricia trie, radix tree
- Games — word games (Scrabble, Boggle)
- Enseñanza — introduce árboles y espacios de caracteres
Casos Extremos
- Alfabeto grande — Unicode tiene ~140k caracteres; usa map dinámico.
- Palabras muy largas — L puede ser grande, pero O(L) sigue siendo rápido.
- Muchas palabras con mismo prefijo — trie comparte nodos, ahorra espacio.
- Delete — solo borra nodos si no son usados por otras palabras.
Trayectoria de Práctica
- Implementa trie con array fijo (a-z); inserta y busca palabras.
- Añade
startsWithpara autocompletado. - Extiende a delete: borra nodos innecesarios.
- Investiga radix tree: ¿cómo comprime cadenas de un solo hijo?
- Investiga suffix trie: ¿por qué es útil para pattern matching?