Implementando Árvore de Busca Binária com NodeJS e Javascript
Árvore de busca binária em JavaScript: inserção, busca, percorridas e limites na prática. Implementação completa com Node.js e exemplos.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
Estruturas de DadosJavaScript
Precisa manter dados ordenados enquanto insere e busca, sem reordenar o array inteiro? (árvore de busca binária) entrega busca em O(log n) a árvore não degenerar.
Você já viu árvores binárias nessa série. A Árvore de Busca Binária (BST) é uma árvore binária com uma regra extra: para cada nó, todos os valores na subárvore esquerda são menores, e todos os valores na subárvore direita são maiores. Essa regra simples é o que torna a busca tão eficiente.
Árvore de busca binária: raiz 8, subárvore esquerda menor, direita maior
Olha a árvore acima. A partir da raiz 8: tudo à esquerda (3, 1, 6, 4, 7) é menor que 8, e tudo à direita (10, 14, 13) é maior. Esse padrão se repete em cada nó. Se estou procurando o 6, começo em 8 → vou pra esquerda → chego em 3 → vou pra direita → chego em 6. Pronto—três comparações em vez de varrer a lista inteira.
Mão na Massa
A Teoria da Coisa (um pouco mais fundo)
A regra de ordenação da BST nos dá uma propriedade poderosa: um percurso in-order (esquerda → nó → direita) sempre retorna os valores em ordem crescente. Então a BST é basicamente uma estrutura que se mantém ordenada automaticamente conforme você insere e remove valores.
Operações em uma BST ideal (balanceada):
Operação
Tempo
Busca
O(log n)
Inserção
O(log n)
Remoção
O(log n)
Jon, qual é o problema?
O problema é o equilíbrio. Se você inserir valores em ordem crescente—tipo 1, 2, 3, 4, 5—cada novo nó vai só pra direita do anterior. A árvore vira uma lista encadeada e tudo cai pra O(n). Árvores auto-balanceadas (AVL, Red-Black) resolvem isso automaticamente, mas aqui vamos manter simples.
Agora a Prática
Abre aí o seu VSCode ou a IDE que você preferir, cria um arquivo chamado bst.js, e cola o código abaixo:
código
class Node { constructor(value) { this.value = value this.left = null this.right = null }}class BST { constructor() { this.root = null } insert(value) { const newNode = new Node(value) if (!this.root) { this.root = newNode return this } let current = this.root while (true) { if (value === current.value) return this // ignora duplicatas if (value < current.value) { if (!current.left) { current.left = newNode; return this } current = current.left } else { if (!current.right) { current.right = newNode; return this } current = current.right } } } search(value) { let current = this.root while (current) { if (value === current.value) return current current = value < current.value ? current.left : current.right } return null }}
Explicando:
Node é o contêiner—um valor, filho esquerdo e filho direito.
BST guarda a root e os métodos.
insert percorre a árvore comparando valores: menor vai pra esquerda, maior vai pra direita. Quando acha uma posição vazia, insere o novo nó.
search segue o mesmo caminho—esquerda se menor, direita se maior—até achar o valor ou cair fora da árvore.
Agora vamos adicionar o percurso in-order. Ele lê a árvore de volta em ordem crescente. Adiciona esse método dentro da classe BST:
código
inOrder(node = this.root, result = []) { if (node) { this.inOrder(node.left, result) result.push(node.value) this.inOrder(node.right, result) } return result }
O padrão é: visita a subárvore esquerda primeiro, depois empurra o nó atual, depois visita a subárvore direita. Por causa da regra de ordenação da BST, isso sempre retorna um array ordenado.
Vamos testar tudo. Depois da classe BST, adiciona:
código
const tree = new BST()tree.insert(8)tree.insert(3)tree.insert(10)tree.insert(1)tree.insert(6)tree.insert(14)tree.insert(4)tree.insert(7)tree.insert(13)console.log('Percurso in-order (deve ser ordenado):')console.log(tree.inOrder())console.log('\nBusca pelo 6:')const found = tree.search(6)console.log(found ? `Encontrado: ${found.value}` : 'Não encontrado')console.log('\nBusca pelo 99:')const notFound = tree.search(99)console.log(notFound ? `Encontrado: ${notFound.value}` : 'Não encontrado')
Roda o arquivo:
código
node bst.js
Resultado esperado:
código
Percurso in-order (deve ser ordenado):[ 1, 3, 4, 6, 7, 8, 10, 13, 14]Busca pelo 6:Encontrado: 6Busca pelo 99:Não encontrado
Olha o resultado do in-order—[1, 3, 4, 6, 7, 8, 10, 13, 14], perfeitamente ordenado, mesmo inserindo os valores em ordem aleatória. Isso é a regra da BST fazendo o trabalho silenciosamente a cada inserção.
Jon, e a remoção de um nó?
Remoção é a operação mais complicada na BST porque tem três casos:
Nó folha (sem filhos) — só remove.
Um filho — substitui o nó pelo filho.
Dois filhos — substitui o valor do nó pelo seu sucessor in-order (o menor valor na subárvore direita), depois deleta esse sucessor.
Fica de desafio pra você implementar—se travar, deixa um comentário que a gente resolve junto!
Aonde Você Pode Usar/Ver
Índices de Banco de Dados
Estruturas reais de índice de banco de dados, como B-Trees e B+-Trees, são descendentes diretas da ideia da BST. Elas mantêm as chaves em ordem para que consultas de intervalo (WHERE idade BETWEEN 25 AND 40) possam usar busca binária em vez de varrer tudo. Entender BSTs é pré-requisito pra entender como índices funcionam de verdade.
Coleções Ordenadas
Sempre que precisar de uma coleção que se mantém ordenada enquanto você insere e deleta—sem reordenar em cada acesso—uma BST (ou variante balanceada) é a escolha natural. Runtimes de linguagens usam isso pra TreeMap/TreeSet no Java, std::map/std::set no C++, e estruturas similares.
Autocomplete e Buscas por Intervalo
BSTs permitem encontrar eficientemente todas as chaves que começam com um prefixo ou caem num intervalo. Uma trie (próximo post!) é especializada em busca de prefixo, mas pra intervalos numéricos ou comparáveis em geral, BSTs são a pedida.
Edge cases: BST degenerada e remoção
Inserir 1,2,3,4,5... em BST simples vira lista — O(n). Em produção: árvore balanceada (Red-Black) ou Map ordenado da runtime.
Remover nó com dois filhos exige substituto (sucessor in-order) — é o bug mais comum em implementação manual.
