Implementando Tries com NodeJS e Javascript

Autocomplete que sugere a cada tecla não varre o dicionário inteiro — usa prefixo. Trie (árvore de prefixos) compartilha nós entre palavras com começo igual.

O que você vai aprender:

• Nó por caractere e flag de fim de palavra
• insert, search, startsWith
• Memória vs hash table para vocabulário grande
• Casos: busca, IDE, roteamento IP

Pré-requisitos: BST (ep. 12) e árvores (ep. 6).

Trie: árvore de prefixos em JavaScript

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.

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.

Mão na Massa

Um Pouco Mais de Teoria

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.

Agora a Prática

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.js

Resultado 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ó.

Aonde Você Pode Usar/Ver

Autocomplete em Buscas

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.

Correção Ortográfica e Texto Preditivo

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.

Tabelas de Roteamento IP

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.

Edge cases: Object.create(null) e chaves perigosas

Usar {} 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).

TL;DR — Trie

Próximos passos

• Algoritmos em grafos (ep. 14): outro tipo de travessia — BFS e DFS
• Resumo da série: Mapa das 15 estruturas

Antes de fechar

Já montou autocomplete ou filtro por prefixo? Comenta o gotcha que mais te pegou.