O que é uma trie (árvore de prefixos) e quando é útil?

Question

Accepted Answer

Uma **trie** (árvore de prefixos) é uma árvore onde cada **aresta** representa um caractere e cada **caminho a partir da raiz** forma um prefixo. Palavras que compartilham um prefixo compartilham o mesmo caminho, tornando buscas de prefixo extremamente rápidas.

## Estrutura

```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
```

## Complexidade

| Operação | Tempo |
|---|---|
| inserção | O(L) |
| busca | O(L) |
| consulta de prefixo | O(L) |

Crucialmente, o custo depende do **comprimento da palavra L**, *não* do número de palavras armazenadas.

## Compensações

- **Pontos fortes:** busca rápida de prefixo; autocompletar; prefixos compartilhados economizam espaço para palavras similares.
- **Pontos fracos:** alto overhead de memória por nó (um mapa de filhos para cada); pode usar mais espaço que um hash set para chaves não relacionadas.

## Por que isso importa

Tries alimentam autocompletar, corretores ortográficos, tabelas de roteamento IP e busca baseada em dicionário onde a correspondência de **prefixo** importa.

Quando um hash set apenas responde "correspondência exata", uma trie adicionalmente responde "quais palavras começam com X?" eficientemente.