Overview
Un Trie (árbol de prefijos) almacena cadenas de forma que las palabras con prefijos comunes comparten nodos. Búsqueda e inserción en O(k) donde k es la longitud de la palabra.
Analogy
Como un diccionario organizado por prefijos: "ba" lleva a "ball", "bat", "bar" — comparten la rama "ba".
Step-by-step
- Nodo raíz vacío; cada nodo tiene un mapa hijo de caracteres
- Insertar: recorre cada carácter; crea nodos si no existen; marca el final de palabra
- Buscar: recorre cada carácter; devuelve False si falta algún nodo
- Prefijo: igual que buscar pero sin comprobar el marcador de fin de palabra
Visual
Insertar "cat","car","dog":
root
├─c─a─t(fin)
│ └─r(fin)
└─d─o─g(fin)
Common mistakes
- Olvidar el marcador is_end para distinguir prefijo de palabra completa
- No manejar caracteres unicode (tamaño de alfabeto > 26)
Practice questions
- Implementa autocompletado con Trie
- Implementa búsqueda de palabras con comodines
Time
O(k) inserción y búsqueda (k = longitud de clave)
Space
O(ALPHABET × N × k) en el peor caso