24 de Março
Trie
O que trie significa, quando prefixo importa mais do que palavra inteira e por que ela aparece tanto em dicionario e busca.
O que e
Trie e uma estrutura em árvore em que cada aresta representa um caractere.
O caminho da raiz até um no representa um prefixo.
Alguns nos marcam fim de palavra.
Quando usar
Ela aparece quando o problema fala de:
- busca por prefixo
- autocomplete
- dicionario de palavras
- wildcard por caractere
Erro comum
O erro clássico e achar que trie sempre substitui Set ou Map.
Se você só precisa buscar palavra exata, Set costuma ser mais simples.
Trie entra forte quando prefixo compartilhado realmente muda a busca.
Pergunta melhor
Antes de aplicar, vale perguntar:
- várias palavras compartilham prefixos relevantes?
- eu preciso responder prefixo, autocomplete ou wildcard por caractere?
- o custo extra de nos e ponteiros compensa a estrutura mais rica?
Compartilhar esta página
Copie o link manualmente no campo abaixo.