BST: Árvore Binária de Busca

BST é a árvore binária com uma propriedade extra: pra cada nó, todos os valores à esquerda são menores, e todos à direita são maiores. Essa propriedade única destrava busca, inserção e remoção em O(log n) - mas só se a árvore estiver balanceada.

O essencial 🟢

Propriedade BST: pra todo nó N:

• Todos os nós na subárvore esquerda têm valor menor que N.
• Todos os nós na subárvore direita têm valor maior que N.

Busca: começa na raiz. Se o valor procurado é menor, vai pra esquerda. Se é maior, vai pra direita. Repete até achar ou chegar em None (não existe). Em árvore balanceada, descarta metade a cada nível - O(log n).

def busca(no, valor):
    if no is None or no.valor == valor:
        return no
    if valor < no.valor:
        return busca(no.esquerda, valor)
    else:
        return busca(no.direita, valor)

Inserção: mesma lógica da busca - desce até achar uma posição None (onde a recursão parou) e cria o novo nó ali.

def inserir(no, valor):
    if no is None:
        return No(valor)
    if valor < no.valor:
        no.esquerda = inserir(no.esquerda, valor)
    elif valor > no.valor:
        no.direita = inserir(no.direita, valor)
    return no

Remoção: três casos, em ordem de complexidade:

1. Nó folha (sem filhos): só remove. O(1).
2. Nó com 1 filho: substitui pelo filho. O(1) (depois de achar).
3. Nó com 2 filhos: acha o sucessor em-ordem (menor valor da subárvore direita) ou o predecessor em-ordem (maior valor da subárvore esquerda), copia o valor pro nó a ser removido, e remove o sucessor/predecessor (que cai no caso 1 ou 2).

Achar mínimo: desce sempre pela esquerda até None. Retorna o último nó não-nulo. Usado pra sucessor em-ordem.

Aprofundamento 🟡

O "defeito" da BST pura: desbalanceamento. Se você inserir valores em ordem (1, 2, 3, 4, 5), a árvore vira uma lista ligada:

1
 \
  2
   \
    3
     \
      4
       \
        5

Busca vira O(n) - não tem ganho sobre array ordenado. O pior caso acontece com dados já ordenados (ou quase ordenados) - comum em cenários reais (timestamps, IDs sequenciais).

Solução: árvore auto-balanceada (próximo nó). Mas vale conhecer a operação que mantém a árvore balanceada: rotação.

Validação de BST: percorre em-ordem e checa se a sequência é estritamente crescente. O(n). Útil em entrevistas e em testes de propriedades invariantes.

def eh_bst(no, minimo=float('-inf'), maximo=float('inf')):
    if no is None: return True
    if no.valor <= minimo or no.valor >= maximo: return False
    return (eh_bst(no.esquerda, minimo, no.valor) and
            eh_bst(no.direita, no.valor, maximo))

Quando usar BST na vida real: quase nunca, em código de aplicação. Use SortedSet (Java), set ordenado (C++), SortedDict (Python via sortedcontainers - biblioteca de terceiros). Por baixo, eles usam árvore red-black (não BST pura) - então o O(log n) é garantido.

BST pura é boa pra:

• Aprender o conceito (entrevistas pedem).
• Problema com garantia externa de balanceamento (dados vêm em ordem aleatória, sem garantia mas com esperança estatística).
• Variações especializadas (treap, splay tree) que adicionam heurística de balanceamento.

Pra quem quer ir além 🔴

Análise da altura esperada de BST aleatória: se você inserir n valores em ordem aleatória numa BST pura, a altura esperada é Θ(log n). É um resultado contra-intuitivo (parece que altura poderia ser n), mas a probabilidade de desbalanceamento grave decresce rápido. Referência: capítulo 12 do CLRS.

Treap e Splay Tree: BST que se auto-balanceiam sem as regras rígidas de AVL/Red-Black. Treap usa prioridade aleatória por nó (heap + BST simultaneamente). Splay Tree move o nó acessado pra raiz (auto-otimiza pra acessos repetidos). Úteis em sistemas embarcados e caches.

Leitura recomendada:

• Capítulo 12 do Introduction to Algorithms (CLRS) - BST, análise de altura, remoção com sucessor em-ordem.
• Capítulo 3 do Algorithms (Sedgewick) - versão mais didática em Java.

Dica: BST pura é case study - você implementa uma vez pra aprender, depois usa a variação auto-balanceada. Em produção, quase nunca vale o risco de O(n) no pior caso.

No próximo nó, vamos ver como as árvores auto-balanceadas (AVL, Red-Black) garantem O(log n) sempre, via rotações.