Complejidad Temporal
Mejor: O(1)
Un Trie almacena cadenas compartiendo sus prefijos comunes. Cada arista es un carácter, y el camino desde la raíz hasta un nodo deletrea un prefijo. Las búsquedas cuestan O(L) donde L es la longitud de la palabra — independiente de cuántas palabras haya guardadas.
Cómo funciona:
1. Cada nodo guarda un mapa de hijos (carácter → nodo) y un flag isEnd
2. Insertar recorre la palabra carácter a carácter, creando nodos solo cuando faltan
3. isEnd marca dónde termina una palabra real, así "ca" puede ser un camino sin ser palabra
Por qué no una tabla hash:
Una tabla hash también busca una clave exacta en O(L),
pero no puede responder "¿qué palabras empiezan por ca?"
sin recorrer todas las claves. Un trie baja 2 nodos
y todo el subárbol es la respuesta.
Complejidad Temporal:
Mejor: O(1) cuando el primer carácter no coincide
Promedio: O(L) para insertar, buscar y startsWith
Peor: O(L) — nunca depende del número de palabras
Complejidad Espacial: O(n × L) — su principal debilidad. Los radix trees comprimen cadenas de un solo hijo para reducirla.
Aplicaciones: autocompletado, correctores ortográficos, tablas de enrutamiento IP (longest prefix match), teclados T9, juegos de palabras, autocompletado de símbolos en editores
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Trie (Árbol de Prefijos)?
- Un Trie almacena cadenas compartiendo sus prefijos comunes. Cada arista es un carácter, y el camino desde la raíz hasta un nodo deletrea un prefijo. Las búsquedas cuestan O(L) donde L es la longitud de la palabra — independiente de cuántas palabras haya guardadas.
- ¿Cuál es la complejidad de Trie (Árbol de Prefijos)?
- Tiempo (promedio): O(L) para insertar, buscar y startsWith · Espacio: O(n × L)
- ¿Para quién es este visualizador de Trie (Árbol de Prefijos)?
- La visualización de Trie (Árbol de Prefijos) está pensada para nivel intermedio, dentro de la categoría Estructuras de Datos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Trie (Árbol de Prefijos)?
- En la misma categoría (Estructuras de Datos) puedes explorar: Stack, Queue, Linked List. Todos tienen visualización interactiva.