Padrão 5: Trie (árvore de prefixos)

A Trie é uma árvore especializada em texto: cada aresta é um caractere, e cada caminho da raiz para baixo soletra um prefixo. Ela torna "esta palavra existe?" e "alguma palavra começa com este prefixo?" muito eficientes — e é a base de autocompletar.

🎯

Tente primeiro: Implement Trie (Prefix Tree)

Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.

Implemente uma Trie (árvore de prefixos) com insert, search (palavra exata) e startsWith (prefixo). Para testar, você recebe duas listas: operacoes (ex.: "Trie", "insert", "search", "startsWith") e args (o argumento de cada operação). Retorne a lista de resultados (None para construir/inserir, true/false para as buscas).

Exemplo: ops ["Trie","insert","search","search","startsWith"], args [[],["apple"],["apple"],["app"],["app"]] → [null,null,true,false,true].

Carregando editor…

Tentou? Guardar as palavras numa lista e procurar uma a uma é O(n·m) por busca. A teoria abaixo mostra como a estrutura de árvore por caractere torna cada busca proporcional só ao tamanho da palavra.

A teoria: caminhos que soletram palavras

Numa Trie, cada nó representa um prefixo, e seus filhos são os próximos caracteres possíveis. Palavras que compartilham um prefixo compartilham o mesmo caminho — daí a eficiência e a economia de espaço.

inserindo "casa", "caso", "cair":

        (raiz)
          │ c
          c
          │ a
          a
         / \
      s/   \i
      s     i
     / \     \
    a   o     r
   (casa)(caso)(cair)

Cada nó precisa de duas coisas:

um mapa de filhos ({caractere: próximo nó});
uma flag fim de palavra, marcando que algum caminho termina ali (para distinguir uma palavra completa de um simples prefixo).

As três operações seguem o mesmo caminhar letra a letra:

insert(palavra):  caminhe, criando nós que faltam; marque o último como fim.
search(palavra):  caminhe; existe o caminho inteiro E o último é fim?
startsWith(pref): caminhe; existe o caminho inteiro? (não precisa ser fim)

A diferença entre search e startsWith é só a flag de fim — essa flag é o que separa "a palavra cas existe?" de "existe palavra que começa com cas?".

Carregando editor…

Por que a Trie é eficiente?

Cada operação (insert/search/startsWith) caminha um nó por caractere da palavra/prefixo → O(L), onde L é o comprimento — independente de quantas palavras já estão guardadas! Comparar com uma lista de palavras seria O(n·L) por busca. O custo da Trie é o espaço: nós para cada caractere distinto dos prefixos (mitigado pelo compartilhamento de prefixos comuns).

Onde a Trie brilha

Autocompletar, corretor ortográfico, busca por prefixo, e problemas que casam muitas palavras de uma vez contra um texto/grid (como o Word Search II, que combina Trie + DFS no grid da seção Matriz — Trie para checar muitos prefixos ao mesmo tempo). Sempre que o problema for sobre prefixos ou um dicionário de palavras, pense em Trie.

🧠 Quiz de fixação

0/4

1. O que cada nó de uma Trie representa, e o que ele guarda?

2. Qual a ÚNICA diferença entre search(palavra) e startsWith(prefixo)?

3. Por que cada operação da Trie é O(L) (L = tamanho da palavra)?

4. Por que palavras que compartilham um prefixo economizam espaço numa Trie?

Resumo

Trie: árvore onde cada aresta é um caractere; um caminho soletra um prefixo.
Cada nó: mapa de filhos + flag fim de palavra (separa palavra de prefixo).
insert/search/startsWith caminham letra a letra: O(L), independente do número de palavras.
Brilha em autocompletar, busca por prefixo e casar muitas palavras (Word Search II).

Última parada: a síntese da seção Árvores e o quiz antes da prova.

Todas as aulas da seção