Implementando Árvore de Busca Binária com NodeJS e Javascript

Precisa manter dados ordenados enquanto insere e busca, sem reordenar o array inteiro? BST (árvore de busca binária) entrega busca em O(log n) se a árvore não degenerar.

O que você vai aprender:

• Regra esquerda < nó < direita
• Inserir, buscar e percursos (in-order)
• Por que dados já ordenados viram lista encadeada
• Ligação com índices de banco

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

BST: busca binária em árvore

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.

graph TD
  N8["8"]
  N3["3"]
  N10["10"]
  N1["1"]
  N6["6"]
  N14["14"]
  N4["4"]
  N7["7"]
  N13["13"]

  N8 --> N3
  N8 --> N10
  N3 --> N1
  N3 --> N6
  N6 --> N4
  N6 --> N7
  N10 --> N14
  N14 --> N13

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):

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:

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:

  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:

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:

node bst.js

Resultado esperado:

Percurso in-order (deve ser ordenado):
[
  1, 3,  4,  6,
  7, 8, 10, 13,
  14
]
 
Busca pelo 6:
Encontrado: 6
 
Busca 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:

1. Nó folha (sem filhos) — só remove.
2. Um filho — substitui o nó pelo filho.
3. 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.

TL;DR — BST

Próximos passos

• Trie (ep. 13): prefixo em vez de ordem total — Implementando Tries
• Busca binária em array (ep. 16): mesma ideia, sem ponteiros — Busca binária

Antes de fechar

Já debugou BST com in-order no console? Se viu erro no post ou implementou remoção, comenta.