Trie em JavaScript: insert, search, startsWith e autocomplete na prática. Árvore de prefixos com Node.js e casos de uso reais.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
Autocomplete que sugere a cada tecla não varre o dicionário inteiro — usa prefixo. (árvore de prefixos) compartilha nós entre palavras com começo igual.
O que você vai aprender:
insert, search, startsWithPré-requisitos: BST (ep. 12) e árvores (ep. 6).
Já se perguntou como sua IDE sugere completações enquanto você digita, ou como um buscador mostra sugestões antes de você terminar a frase? Boa parte da resposta é a Trie (pronuncia "trai", abreviação de retrieval—recuperação).
Uma Trie é uma árvore onde cada nó representa um único caractere. Você lê uma palavra seguindo um caminho da raiz até uma folha. Nós compartilhados entre palavras representam prefixos comuns—e é isso que torna a estrutura tão poderosa pra buscas de prefixo.
scene: en/data-structures-in-a-nutshell/trie-can-car-cat-bat
Interactive Excalidraw view is not available in this build.
graph LR root((root)) c((c)) b((b)) a1((a)) a2((a)) n((n)) r((r)) t((t)) end_can(["✓ can"]) end_car(["✓ car"]) end_cat(["✓ cat"]) end_bat(["✓ bat"]) root --> c root --> b c --> a1 a1 --> n --> end_can a1 --> r --> end_car a1 --> t --> end_cat b --> a2 a2 --> end_bat
Olha o diagrama acima. As palavras can, car e cat compartilham o prefixo ca—então elas compartilham o mesmo caminho c → a a partir da raiz. Você guarda o prefixo uma vez só e ramifica apenas onde as palavras divergem. Eficiente demais.
Tries trocam memória por velocidade. Pra um dicionário de strings, um hash map te dá O(1) pra lookup exato. Mas pra busca por prefixo ("me dá todas as palavras que começam com ca"), um hash map não tem atalho—você varre tudo. Uma Trie faz isso em O(k) onde k é o tamanho do prefixo.
Cada nó numa Trie é basicamente um mapa de caracteres para nós filhos, mais um flag que marca se uma palavra completa termina ali.
Abre a IDE, cria um arquivo chamado trie.js e cola o código abaixo:
class TrieNode {
constructor() {
this.children = {}
this.isEndOfWord = false
}
}
class Trie {
constructor() {
this.root = new TrieNode()
}
insert(word) {
let node = this.root
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode()
}
node = node.children[char]
}
node.isEndOfWord = true
}
}Explicando:
TrieNode tem um mapa children (caractere → nó filho) e o flag isEndOfWord.Trie começa com um nó root vazio.insert percorre caractere por caractere. Se um nó pro caractere atual não existir, ele cria. No fim da palavra seta isEndOfWord = true.Agora vamos adicionar search e startsWith:
search(word) {
let node = this.root
for (const char of word) {
if (!node.children[char]) return false
node = node.children[char]
}
return node.isEndOfWord
}
startsWith(prefix) {
let node = this.root
for (const char of prefix) {
if (!node.children[char]) return false
node = node.children[char]
}
return true
}A diferença entre os dois:
search retorna true só se a palavra exata foi inserida (verifica isEndOfWord).startsWith retorna true se qualquer palavra inserida começa com o prefixo dado (não liga pra isEndOfWord).Vamos adicionar também uma função de autocomplete que retorna todas as palavras com um dado prefixo:
autocomplete(prefix) {
let node = this.root
for (const char of prefix) {
if (!node.children[char]) return []
node = node.children[char]
}
const results = []
this._collectWords(node, prefix, results)
return results
}
_collectWords(node, current, results) {
if (node.isEndOfWord) results.push(current)
for (const char of Object.keys(node.children)) {
this._collectWords(node.children[char], current + char, results)
}
}Agora vamos testar tudo. Depois da classe Trie, cola o código abaixo:
const trie = new Trie()
trie.insert('can')
trie.insert('car')
trie.insert('cat')
trie.insert('bat')
trie.insert('ball')
trie.insert('band')
console.log('search("can"):', trie.search('can')) // true
console.log('search("ca"):', trie.search('ca')) // false (não é uma palavra completa)
console.log('search("dog"):', trie.search('dog')) // false
console.log('\nstartsWith("ca"):', trie.startsWith('ca')) // true
console.log('startsWith("ba"):', trie.startsWith('ba')) // true
console.log('startsWith("xy"):', trie.startsWith('xy')) // false
console.log('\nautocomplete("ca"):', trie.autocomplete('ca'))
console.log('autocomplete("ba"):', trie.autocomplete('ba'))Roda o arquivo:
node trie.jsResultado esperado:
search("can"): true
search("ca"): false
search("dog"): false
startsWith("ca"): true
startsWith("ba"): true
startsWith("xy"): false
autocomplete("ca"): [ 'can', 'car', 'cat' ]
autocomplete("ba"): [ 'bat', 'ball', 'band' ]autocomplete("ca") retornou ['can', 'car', 'cat']—exatamente as palavras que inserimos que começam com "ca". A Trie foi direto pro caminho c → a e coletou só o que estava lá, sem varrer o resto.
Jon, e se eu quiser os resultados em ordem alfabética?
O _collectWords itera Object.keys(node.children), e no V8 (Node.js) chaves string são iteradas na ordem de inserção. Se quiser ordem alfabética, ordena as chaves: for (const char of Object.keys(node.children).sort()). Uma linha só.
Esse é o caso de uso clássico. Toda vez que você digita numa caixa de busca e sugestões aparecem, provavelmente tem uma Trie (ou uma variante mais compacta como radix tree) fazendo o match de prefixo no servidor—ou até no cache do browser pra sugestões locais instantâneas.
Teclados de celular usam estruturas parecidas com Trie pra sugerir a próxima palavra com base no que você já digitou. Corretores ortográficos baseados em dicionário também as usam pra enumerar rapidamente candidatos de correção.
Roteadores de rede guardam prefixos de endereços IP numa variante de Trie chamada PATRICIA trie ou radix tree. Quando um pacote chega, o roteador faz um match do prefixo mais longo pra decidir pra onde encaminhar—uma Trie torna isso rápido mesmo com milhões de prefixos.
Object.create(null) e chaves perigosasUsar {} para filhos faz herdar toString, constructor do prototype — chave "toString" quebra tudo. Object.create(null) evita isso.
Trie esparsa com um filho por nível desperdiça memória — radix tree comprime caminhos lineares (tópico avançado).
| Método | Complexidade (palavra len = m) |
|---|---|
| insert | O(m) |
| search | O(m) |
| startsWith | O(m) |
| Espaço | Compartilha prefixos |
Já montou autocomplete ou filtro por prefixo? Comenta o gotcha que mais te pegou.
Receba notas de arquitetura e performance na sua caixa de entrada. Mesma lista do convite—inscreva-se aqui quando quiser.
