Trie (árbol de prefijos) explicado: cómo funciona, código y complejidad

Qué problema resuelve un trie

Un conjunto hash responde rápido a "¿está guardada esta palabra exacta?", pero no puede responder "¿qué palabras guardadas empiezan por pre?" sin revisar todas. Una lista ordenada puede responder consultas de prefijo con búsqueda binaria, pero las inserciones son lentas. Un trie está organizado por prefijos, así que las preguntas de prefijo son su fortaleza natural: autocompletado en un cuadro de búsqueda, juegos de palabras, corrección ortográfica y coincidencia del prefijo más largo en rutas de red.

La idea en palabras sencillas

Piensa en la lista de contactos del teléfono que vas acotando letra a letra. Al escribir c aparecen todos los que empiezan por c, al escribir ca la lista se reduce, y así sucesivamente. Un trie guarda las palabras exactamente con esa forma. La raíz es el prefijo vacío. Cada nodo tiene un mapa del siguiente carácter a un nodo hijo, más una marca de fin de palabra, porque una palabra como car puede ser a la vez una palabra completa y un prefijo de cart.

Ejemplo resuelto: insertar car, cart, cat y dog

Las cuatro palabras suman 13 letras pero necesitan solo 8 nodos bajo la raíz (c, a, r, t, t, d, o, g), porque car, cart y cat comparten ca. Buscar ca recorre dos nodos y tiene éxito como prefijo, pero ca no es una palabra porque su nodo no está marcado como final. Buscar cow falla en el segundo paso: el nodo c no tiene hijo o.

Implementación en Python

Cada nodo guarda un dict de hijos, que maneja cualquier alfabeto, incluido Unicode. El método starts_with reúne todas las palabras bajo un prefijo, que es el núcleo del autocompletado.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with ordena su salida para obtener un orden estable. Un autocompletado real también se detendría tras los primeros resultados y los clasificaría, por ejemplo con contadores de popularidad guardados.

Complejidad temporal y espacial

El tiempo no depende del número de palabras n, que es la principal ventaja frente a un árbol balanceado de cadenas (O(m log n) comparaciones). El costo es la memoria: cada nodo es un objeto independiente con su propio diccionario, así que un trie puede usar muchas veces más memoria que las cadenas en bruto.

Variantes y errores comunes

• Hijos en arreglo: usa un arreglo fijo de 26 posiciones para inglés en minúsculas. Es más rápido que un dict, pero desperdicia espacio con alfabetos dispersos o grandes.
• Trie comprimido (radix tree, trie de Patricia): fusiona las cadenas de nodos con un solo hijo en una arista etiquetada con una cadena, lo que ahorra mucha memoria. Los radix trees se usan en tablas de enrutamiento IP y en algunos enrutadores HTTP.
• Árbol de búsqueda ternario: cada nodo tiene tres hijos (menor, igual, mayor), lo que usa menos memoria que un arreglo ancho.
• Trie con contadores: guarda un contador en cada nodo para responder "¿cuántas palabras empiezan por este prefijo?" en O(m).
• Trie bit a bit: guarda números bit por bit para resolver problemas de XOR máximo.

Cuándo usar un trie y problemas típicos de entrevista

Usa un trie cuando necesites consultas de prefijo, coincidencia del prefijo más largo o iteración ordenada sobre muchas cadenas con prefijos compartidos. Usa un set o un dict cuando solo necesites búsquedas de coincidencia exacta: es más simple y usa menos memoria en Python. Para listas de palabras pequeñas y estáticas, una lista ordenada con el módulo bisect también responde bien a las consultas de prefijo.

Problemas típicos: implementar un trie (insert, search, starts-with), buscar palabras en una cuadrícula con muchas palabras objetivo, reemplazar palabras por su raíz más corta, prefijo común más largo, diseñar un sistema de autocompletado de búsqueda y XOR máximo de dos números con un trie bit a bit.