Tries y árboles de prefijos

Organiza cadenas por sus caracteres, no por valores completos. Los prefijos compartidos comparten ramas.

El costo es la longitud de la llave, no el tamaño del diccionario

• Cada arista = un carácter; cada camino = un prefijo
• insert / search / starts_with: O(L)
• autocompletado: O(L + coincidencias) — solo visita las palabras que coinciden
• Independiente de N (funciona igual con 10 que con 10M palabras)

Mira cómo los prefijos comparten ramas

cat, car, card, care comparten c-a-r. Verde = fin de palabra. "do" es a la vez una palabra y un prefijo de "dog"/"dot".

Trie O(L) vs scan O(N·L)

El scan sube con N; el trie se mantiene plano. 8× más rápido con 320000 palabras, y creciendo.

Cuándo sí (y cuándo no)

• Sí: prefijos — autocompletado, corrector ortográfico, ruteo IP, diccionarios
• No: pura membresía (un hash set es O(L), con menos memoria)
• Tragón de memoria → trie comprimido / radix tree (routers IP)

Para llevar

Elige la estructura cuyo costo no crece con lo que sí crece. Para prefijos, eso es un trie. Siguiente: árboles de consultas por rango (segment, Fenwick).