Árvores balanceadas
A BST da lição anterior tem um defeito fatal: com dados ordenados — que é como os dados chegam com muito mais frequência do que gostaríamos — ela vira uma lista ligada e o O(log n) prometido vira O(n). Esta lição mostra a solução: uma operação O(1) chamada rotação, e as regras que dizem quando aplicá-la.
Puxar a árvore pelo meio
Imagine segurar uma árvore desbalanceada — pesada de um lado — e puxá-la pelo nó do meio para cima. Os nós ao redor se reacomodam, o antigo topo desce de um lado, e a árvore fica mais baixa e mais larga. Isso é uma rotação: uma reorganização local de três nós que preserva a ordem mas reduz a altura.
A ideia é impressionantemente simples e é a base de todas as árvores balanceadas. O que diferencia uma AVL de uma rubro-negra não é a rotação em si — é a regra que decide quando o desequilíbrio já é grande o bastante para justificar uma. Regras mais rígidas dão árvores mais baixas (busca mais rápida) ao custo de mais rotações (escrita mais lenta).
A mesma sequência nas duas árvores
Insira os mesmos valores numa BST comum e numa AVL e compare as alturas. Clique em "sequência ordenada" para ver o pior caso: a BST vira uma corrente enquanto a AVL se mantém baixa. Os números ao lado dos nós são os fatores de balanceamento — quando algum passa de ±1, uma rotação dispara.
As duas árvores recebem exatamente os mesmos valores, na mesma ordem. A da direita se reequilibra sozinha com rotações sempre que a diferença de altura entre os filhos de algum nó passa de 1.
A rotação
# A rotação é a operação fundamental: reorganiza três nós # mudando quem é o pai, SEM quebrar a invariante da BST. # # y x # / \ rotação à direita / \ # x C ------------------> A y # / \ <------------------ / \ # A B rotação à esquerda B C # # Confira: em AMBAS as formas vale A < x < B < y < C. # A ordem em travessia em ordem é idêntica — só a ALTURA muda. def rotacionar_direita(y): x = y.esq B = x.dir x.dir = y # x sobe e adota y como filho direito y.esq = B # y adota a subárvore B que x largou atualizar_altura(y) # y primeiro: agora ele está mais embaixo atualizar_altura(x) return x # x é a nova raiz desta subárvore # Custo: 3 atribuições de ponteiro. O(1). Sempre.
AVL: a regra mais simples que funciona
# AVL (Adelson-Velsky e Landis, 1962) — a primeira árvore # auto-balanceada da história. # # INVARIANTE: em todo nó, |altura(esq) − altura(dir)| ≤ 1 # Esse número é o "fator de balanceamento". def fator(no): return altura(no.esq) - altura(no.dir) # deve ser -1, 0 ou +1 def inserir(no, v): if no is None: return No(v) if v < no.v: no.esq = inserir(no.esq, v) elif v > no.v: no.dir = inserir(no.dir, v) else: return no atualizar_altura(no) b = fator(no) # Quatro casos de desbalanceamento — e só quatro. if b > 1 and v < no.esq.v: # Esquerda-Esquerda return rotacionar_direita(no) if b < -1 and v > no.dir.v: # Direita-Direita return rotacionar_esquerda(no) if b > 1 and v > no.esq.v: # Esquerda-Direita (dupla) no.esq = rotacionar_esquerda(no.esq) return rotacionar_direita(no) if b < -1 and v < no.dir.v: # Direita-Esquerda (dupla) no.dir = rotacionar_direita(no.dir) return rotacionar_esquerda(no) return no # A inserção percorre de volta até a raiz atualizando alturas, # mas no máximo UMA rotação (simples ou dupla) é necessária. # Custo total: O(log n).
A prova de que a altura é O(log n)
# Por que a AVL garante altura O(log n)? # # Seja N(h) o MENOR número de nós numa AVL de altura h. # Uma AVL de altura h precisa de uma subárvore de altura h−1 e, # no mínimo, uma de altura h−2 (senão o fator passaria de 1): # # N(h) = 1 + N(h−1) + N(h−2) ← isso é Fibonacci! # N(0)=0, N(1)=1, N(2)=2, N(3)=4, N(4)=7, N(5)=12, N(6)=20 ... # # Como Fibonacci cresce como φ^h (φ ≈ 1,618), invertendo: # h ≤ 1,44 · log₂(n) # # Ou seja: a AVL nunca fica mais que ~44% mais alta que a árvore # perfeitamente balanceada. Para n = 1 milhão: # altura ideal: 20 # AVL, no pior: 28 # BST degenerada: 1.000.000
As primas: rubro-negra e B-tree
# RUBRO-NEGRA (red-black) — a alternativa mais usada na prática. # Cada nó é vermelho ou preto, e valem cinco regras. As que importam: # - a raiz é preta # - um nó vermelho não pode ter filho vermelho # - todo caminho da raiz até uma folha tem o MESMO número de pretos # # Consequência: o caminho mais longo é no máximo 2x o mais curto. # Garantia mais frouxa que a AVL (altura ≤ 2·log₂(n) vs 1,44·log₂(n)), # mas exige MENOS rotações para se manter — o que a torna mais rápida # para cargas com muita escrita. # # A escolha na prática: # AVL → mais rígida, busca mais rápida, escrita mais cara # Rubro-negra → equilíbrio geral. É o std::map do C++, o TreeMap # do Java, o escalonador CFS do Linux e o epoll. # B-TREE — quando os dados estão no DISCO, não na RAM. # # Ler 1 byte do disco custa quase o mesmo que ler 8 KB. Então em vez # de 2 filhos por nó, uma B-tree tem centenas — cada nó ocupa # exatamente uma página de disco. # # BST binária, 1 bilhão de chaves: altura 30 → 30 leituras de disco # B-tree com 256 filhos por nó: altura 4 → 4 leituras de disco # # O Big O é o mesmo, O(log n) — mas a BASE do logaritmo mudou de 2 # para 256, e é isso que decide o desempenho real. É por isso que # TODO índice de banco de dados é uma B-tree (ou B+tree).
Construindo do zero
Mini projeto: implemente rotacionar_esquerda e
rotacionar_direita isoladamente, sem nenhum balanceamento. Escreva um teste que monte
uma árvore, rotacione e verifique que a travessia em ordem não mudou — essa é a prova de
que a rotação preserva a invariante da BST. Depois imprima a altura antes e depois.
Projeto principal: implemente a AVL completa com inserção balanceada e conte as rotações. Insira 100 mil valores em três ordens diferentes — crescente, decrescente e embaralhada — e para cada uma imprima a altura final, o número de rotações e o tempo de 10 mil buscas. Compare com a BST sem balanceamento (para a ordem crescente, prepare-se para esperar, ou reduza para 10 mil valores e aumente o limite de recursão).
Desafio extra: implemente a remoção na AVL. Ela é significativamente mais difícil que a inserção por um motivo específico: enquanto a inserção precisa de no máximo uma rotação, a remoção pode exigir uma rotação em cada nível no caminho de volta até a raiz — até O(log n) rotações. Descubra por quê construindo um caso que force isso.
Teste sua intuição
Onde você encontra isso
O escalonador do kernel Linux
O CFS (Completely Fair Scheduler) mantém as tarefas prontas numa árvore rubro-negra ordenada por tempo virtual de execução. Escolher a próxima tarefa é pegar o nó mais à esquerda — a que rodou menos até agora. Como isso acontece milhares de vezes por segundo, a garantia de O(log n) no pior caso, e não apenas em média, é o que torna a árvore balanceada a escolha certa ali. O epoll e o gerenciador de memória virtual do kernel usam a mesma estrutura.
Índices e sistemas de arquivos
PostgreSQL, MySQL, SQLite, Oracle: todo índice padrão é uma B-tree ou B+tree. Sistemas de arquivos modernos também — NTFS, ext4, Btrfs (o "B" vem daí) e APFS organizam diretórios e metadados em B-trees. É a razão pela qual listar um diretório com 100 mil arquivos não fica 100 mil vezes mais lento que um com um arquivo.
Coleções ordenadas das linguagens
std::map e std::set em C++, TreeMap e TreeSet em Java: todos rubro-negras. A escolha da rubro-negra sobre a AVL nessas bibliotecas é deliberada — como são coleções de propósito geral, com mistura de leituras e escritas, o menor número de rotações compensa a árvore ligeiramente mais alta.