Árvores binárias de busca

Busca binária que aceita inserções

Você já conhece a busca binária: num array ordenado, compare com o meio e descarte metade. O problema é que manter o array ordenado a cada inserção custa O(n) — todo mundo tem que se deslocar.

A BST é a busca binária transformada em estrutura. Cada nó é um "meio": tudo que é menor fica à esquerda, tudo que é maior fica à direita. Buscar é descer comparando, descartando metade da árvore a cada passo. E inserir é a mesma descida — só que ao chegar num espaço vazio, você pendura o nó ali. Nada se move.

Construa, busque e percorra

Insira valores e acompanhe o caminho de descida. Compare a altura real com a altura mínima possível — e clique em "inserir já ordenado" para ver a árvore degenerar. Nas travessias, repare que a travessia em ordem sempre devolve os valores ordenados.

A invariante e as operações básicas

# A invariante da BST, válida em TODO nó:
#   tudo na subárvore esquerda  < nó
#   tudo na subárvore direita   > nó
#
# Não é só "filho esquerdo menor que o pai" — é a subárvore INTEIRA.
# É essa invariante que permite descartar metade a cada comparação.

class No:
    def __init__(self, v):
        self.v = v
        self.esq = None
        self.dir = None

def inserir(no, v):
    if no is None:  return No(v)     # chegou numa folha: pendura aqui
    if v < no.v:      no.esq = inserir(no.esq, v)
    elif v > no.v:    no.dir = inserir(no.dir, v)
    return no                          # v == no.v: já existe, ignora

def buscar(no, v):
    while no:
        if v == no.v:  return no
        no = no.esq if v < no.v else no.dir   # descarta metade
    return None

# Custo: proporcional à ALTURA da árvore, não ao número de nós.
#   árvore balanceada  → altura ≈ log₂(n)  → O(log n)
#   árvore degenerada  → altura = n        → O(n)

As travessias

# Três formas de visitar todos os nós — a diferença é QUANDO
# o nó é processado em relação às chamadas recursivas.

def em_ordem(no, saida):      # esquerda → NÓ → direita
    if not no: return
    em_ordem(no.esq, saida)
    saida.append(no.v)         #  ← processa no meio
    em_ordem(no.dir, saida)
# Numa BST, devolve os valores ORDENADOS. Essa é a propriedade
# mais importante da estrutura: a ordenação sai de graça.

def pre_ordem(no, saida):     # NÓ → esquerda → direita
    if not no: return
    saida.append(no.v)         #  ← processa antes
    pre_ordem(no.esq, saida)
    pre_ordem(no.dir, saida)
# Reinserir nessa ordem recria a árvore com a MESMA forma.
# Por isso é a travessia usada para serializar/copiar.

def pos_ordem(no, saida):     # esquerda → direita → NÓ
    if not no: return
    pos_ordem(no.esq, saida)
    pos_ordem(no.dir, saida)
    saida.append(no.v)         #  ← processa depois
# Filhos sempre antes do pai. Usada para liberar memória e para
# avaliar árvores de expressão (calcule os operandos antes do operador).

# E há a travessia em LARGURA (nível por nível), que não é recursiva:
from collections import deque
def em_largura(raiz):
    fila, saida = deque([raiz]), []
    while fila:
        no = fila.popleft()
        if not no: continue
        saida.append(no.v)
        fila.append(no.esq); fila.append(no.dir)
    return saida

Remoção: os três casos

# Remoção é a operação difícil da BST — há três casos.
def remover(no, v):
    if no is None: return None
    if v < no.v:
        no.esq = remover(no.esq, v)
    elif v > no.v:
        no.dir = remover(no.dir, v)
    else:
        # CASO 1: folha — some, e pronto
        if not no.esq and not no.dir:
            return None
        # CASO 2: um filho só — o filho toma o lugar
        if not no.esq: return no.dir
        if not no.dir: return no.esq
        # CASO 3: dois filhos — o difícil.
        # Substitui pelo SUCESSOR em ordem: o menor da subárvore direita.
        # Ele é o único valor que pode ficar no lugar sem quebrar a
        # invariante (é maior que toda a esquerda e menor que toda a direita).
        suc = no.dir
        while suc.esq: suc = suc.esq
        no.v = suc.v
        no.dir = remover(no.dir, suc.v)   # remove o sucessor (tem ≤1 filho)
    return no

BST vs hash table: o que se ganha com a ordem

# O que a BST dá e a hash table NÃO dá: ORDEM.
#
# Hash table: O(1) para buscar uma chave exata. Só isso.
# BST:        O(log n) para buscar — mas também, de graça:

min(arvore)                   # desce sempre à esquerda   — O(log n)
max(arvore)                   # desce sempre à direita    — O(log n)
sucessor(arvore, x)           # o próximo valor acima de x — O(log n)
intervalo(arvore, 10, 50)     # TODAS as chaves entre 10 e 50
em_ordem(arvore)              # todos os valores ordenados — O(n)

# Numa hash table, "me dê todas as chaves entre 10 e 50" exige
# varrer a tabela inteira: O(n). E "qual a menor chave?" também.
#
# É por isso que bancos de dados usam árvores (B-trees) e não hash
# tables como índice padrão: WHERE idade > 30 é uma consulta por
# INTERVALO, e só uma estrutura ordenada responde isso rápido.

# Em Python não existe BST na biblioteca padrão. Use:
import bisect            # busca binária sobre lista ordenada
# ou a biblioteca externa "sortedcontainers" (SortedDict/SortedSet),
# que resolve o mesmo problema com listas de listas em vez de árvore.
# Em C++ é std::map, em Java é TreeMap — ambos árvores rubro-negras.

Construindo do zero

Mini projeto: implemente a BST completa (inserir, buscar, remover, travessias) e escreva a função eh_bst_valida(no) que verifica a invariante. Cuidado com a armadilha clássica: checar apenas esq.v < no.v < dir.v está errado — isso aceita árvores inválidas. A verificação correta passa um intervalo (mínimo, máximo) pela recursão e o vai estreitando. Escreva um teste que produza um contraexemplo para a versão ingênua.

Projeto principal: use sua BST para construir um índice de intervalo. Carregue 10 mil registros com um campo numérico (por exemplo, timestamps de eventos) e implemente consultar(inicio, fim) que devolva todos os registros no intervalo em O(log n + k), onde k é o número de resultados — descendo até o início do intervalo e depois percorrendo em ordem. Compare o tempo com uma varredura linear sobre uma lista e com um dict.

Desafio extra: escreva serializar(raiz) e desserializar(texto) que salvem a árvore em uma string e a reconstruam com exatamente a mesma forma. Descubra por si mesmo por que a travessia em ordem sozinha não serve para isso (dica: árvores de formas diferentes podem ter a mesma travessia em ordem) e qual travessia resolve, ou qual combinação de duas.

Teste sua intuição

Onde você encontra isso