Tema 7
Tries (árboles de prefijos)
Patrón de examen
Usa Trie cuando el problema involucre prefijos de strings, autocompletado, o contar palabras por prefijo. Usa Trie binario para XOR máximo entre pares de números.
Explicación
¿Qué es un Trie?
Estructura de árbol donde cada nodo representa un carácter. Permite operaciones sobre prefijos de strings en tiempo proporcional a la longitud del string, no al número de strings almacenados.
Operaciones y complejidad
| Operación | Complejidad |
|---|---|
| Insertar string | O(L) |
| Buscar string | O(L) |
| Buscar por prefijo | O(L) |
| Eliminar string | O(L) |
Donde L = longitud del string. Independiente de cuántos strings hay en el trie.
Estructura del nodo
Cada nodo tiene:
- Un arreglo de hijos (26 para letras minúsculas, o un mapa)
- Un marcador de "fin de palabra"
- Opcionalmente: un contador de cuántas palabras pasan por ese nodo
Cuándo usar Trie
- Autocompletado (encontrar todas las palabras con un prefijo)
- Verificar si un string es prefijo de otro
- Contar palabras con un prefijo dado
- Longest common prefix entre múltiples strings
- XOR máximo entre pares (trie binario)
Trie binario
Variante donde cada nodo tiene solo 2 hijos (bit 0 y bit 1). Se insertan los bits de un número de mayor a menor. Permite encontrar el XOR máximo con cualquier número insertado en O(30) para enteros de 30 bits.