Trie — Estructura de datos especializada en cadenas

Al finalizar este tema

Podrás explicar la estructura y el funcionamiento del Trie, e implementar la inserción, la búsqueda y la búsqueda por prefijo para crear funciones como el autocompletado.

Problema — Búsqueda entre decenas de miles de palabras

El diccionario contiene 100 000 palabras. Si el usuario escribe "pro", queremos mostrar "program", "project", "process", etc.

¿Comparar uno por uno en una lista? 100 000 × comparación de cadenas = lento. Una tabla hash solo puede encontrar claves exactas, por lo que no es adecuada para la búsqueda por prefijo.

El Trie (derivado de "retrieval") es una estructura de datos diseñada para resolver este problema.

Estructura del Trie

En un Trie, hay un nodo por cada carácter. Las palabras que comparten el mismo prefijo siguen la misma ruta:

root
├── a
│   ├── p
│   │   └── p ★ ("app")
│   │       └── l
│   │           └── e ★ ("apple")
│   └── c
│       └── e ★ ("ace")
└── b
    ├── a
    │   └── t ★ ("bat")
    └── e ★ ("be")

El símbolo ★ indica que "aquí termina una palabra". "app" y "apple" comparten la misma ruta, pero terminan una vez en "app" y otra vez en "apple".

Implementación — Nodos

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

Cada nodo contiene un diccionario de nodos hijos (children) y un indicador de fin de palabra (is_end).

Inserción

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

trie = Trie()
for word in ["app", "apple", "ace", "bat", "be"]:
    trie.insert(word)

Recorre cada carácter; si no existe una ruta, crea un nuevo nodo. Marca el último carácter como is_end = True.

Exploración

def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end

print(trie.search("app"))    # True
print(trie.search("ap"))     # False — no hay palabras que terminen con "ap"
print(trie.search("apple"))  # True
print(trie.search("bat"))    # True
print(trie.search("bad"))    # False

Si no se encuentra durante el recorrido, False. Si se llega al final y no es is_end, entonces False (es solo un prefijo, no una palabra completa).

Búsqueda de prefijos: la clave del autocompletado

def starts_with(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]

    results = []
    self._collect(node, prefix, results)
    return results

def _collect(self, node, prefix, results):
    if node.is_end:
        results.append(prefix)
    for char, child in node.children.items():
        self._collect(child, prefix + char, results)

print(trie.starts_with("a"))    # ["app", "apple", "ace"]
print(trie.starts_with("ap"))   # ["app", "apple"]
print(trie.starts_with("b"))    # ["bat", "be"]
print(trie.starts_with("z"))    # []

Sigue el prefijo y, a continuación, recopila todas las palabras completas que se encuentran debajo. Este es el principio subyacente en el autocompletado de motores de búsqueda y el autocompletado de código de los IDE.

Complejidad temporal

m = longitud de la cadena, k = número de resultados bajo el prefijo.

El rendimiento de la búsqueda exacta es similar al de una tabla hash; sin embargo, solo un trie permite búsquedas basadas en prefijos. Para encontrar todas las claves que comienzan con "pro", una tabla hash requeriría una búsqueda exhaustiva.

Compensación de memoria (Trade-off)

La desventaja del trie es su consumo de memoria. Cada nodo contiene un diccionario y, incluso solo para letras minúsculas del alfabeto inglés, se requieren hasta 26 punteros a hijos.

Variantes para mejorar esto:

• Compressed Trie (Radix Tree): fusiona nodos con un único hijo para comprimir la ruta.
• Ternary Search Tree: combina un árbol de búsqueda binaria para ahorrar memoria.

En la práctica, la mayoría de las bibliotecas gestionan las optimizaciones, por lo que basta con comprender el principio.

Aplicaciones prácticas

Implementación de eliminación

def delete(self, word):
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end:
                return False
            node.is_end = False
            return len(node.children) == 0

        char = word[depth]
        if char not in node.children:
            return False

        should_remove = _delete(node.children[char], word, depth + 1)
        if should_remove:
            del node.children[char]
            return not node.is_end and len(node.children) == 0
        return False

    _delete(self.root, word, 0)

Al eliminar una palabra, solo se eliminan los nodos exclusivos de dicha palabra (que no son compartidos con otras). Aunque se elimine "apple", los nodos necesarios para "app" permanecen intactos.

Trie de conteo

Si se registra el número de inserciones, se obtiene un diccionario de frecuencias de palabras:

class CountTrie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.count = getattr(node, 'count', 0) + 1

    def count(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return 0
            node = node.children[char]
        return getattr(node, 'count', 0) if node.is_end else 0

Se utiliza para calcular la frecuencia de los términos de búsqueda y determinar el orden de las sugerencias de autocompletado.

Una alternativa sencilla a Trie en Python

No es necesario implementar un Trie directamente; se puede lograr un efecto similar mediante el uso de diccionarios anidados:

from collections import defaultdict

def make_trie(words):
    trie = lambda: defaultdict(trie)
    root = trie()
    for word in words:
        node = root
        for c in word:
            node = node[c]
        node['$'] = True
    return root

t = make_trie(["app", "apple", "bat"])
print("app" in str(t))  # True

Sin embargo, si se requiere una funcionalidad de prefijo como starts_with, una implementación basada en clases es más limpia. En las pruebas de codificación, la implementación mediante clases es el estándar.

El Trie es adecuado para cualquier caso que involucre el manejo de "un conjunto de cadenas que comparten prefijos".