¿Qué es un trie (árbol de prefijos) y cuándo es útil?

Question

Accepted Answer

Un **trie** (árbol de prefijos) es un árbol donde cada **arista** representa un carácter y cada **camino desde la raíz** forma un prefijo. Las palabras que comparten un prefijo comparten el mismo camino, lo que hace que la búsqueda de prefijos sea extremadamente rápida.

## Estructura

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## Código

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = word length
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## Complejidad

| Operación | Tiempo |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Crucialmente, el costo depende de la **longitud de la palabra L**, no del número de palabras almacenadas.

## Compensaciones

- **Fortalezas:** búsqueda rápida de prefijos; autocompletado; los prefijos compartidos ahorran espacio para palabras similares.
- **Debilidades:** sobrecarga de memoria alta por nodo (un mapa de hijos para cada uno); puede usar más espacio que un hash set para claves no relacionadas.

## Por qué es importante

Los tries impulsan el autocompletado, correctores ortográficos, tablas de enrutamiento IP y búsqueda basada en diccionario donde la coincidencia de **prefijos** es importante.

Mientras que un hash set solo responde "¿coincidencia exacta?", un trie responde eficientemente "¿qué palabras comienzan con X?".