O que é uma self-balancing tree
Uma self-balancing binary search tree é uma BST que se remodela depois de todo insert e delete para que sua height fique proporcional a log n. Nada na regra de ordenação muda; o que muda é que a tree se recusa a ficar alta.
O mecanismo é uma operação local, aplicada um punhado de vezes por escrita. Ela não reconstrói a tree, não ordena nada, e nunca move mais de três pointers. Ela se chama rotação, e é o assunto inteiro deste artigo.
Imagine uma estante onde você sempre adiciona livros novos na ponta direita. Para pegar um livro você caminha a estante desde a esquerda — tranquilo no começo, tedioso quando a estante fica longa.
Agora imagine que a estante se reorganiza: toda vez que ela nota que um lado ficou mais alto que o outro, ela desloca um livro para virar o novo meio, e pendura as duas metades nele. Nada é ordenado, nada é reconstruído — um livro muda de posição e a estante inteira fica mais rasa. Isso é uma rotação.
O problema que uma Binary Search Tree não resolvia
O artigo anterior terminou numa estrutura com excelente comportamento médio e nenhum piso sob o pior caso. Insira valores em ordem crescente e todos vão para a direita, produzindo uma tree de height n − 1 — uma linked list com um pointer sem uso por node.
A parte incômoda não era que existe um caso ruim. É que o caso ruim é o banal: dados vêm de um ORDER BY, de um id auto-incremental, de um timestamp, de um arquivo ordenado. Uma estrutura cuja performance colapsa na forma de entrada mais comum não é uma estrutura que você põe atrás de uma query em produção.
Então o objetivo é estreito e específico: manter toda garantia que a BST já oferece — iteração ordenada, range queries, operações O(h) — enquanto torna h comprovadamente O(log n), não importa em que ordem os dados cheguem.
Rotações
Uma rotação pega um parent e um dos seus children e troca qual dos dois fica em cima, reconectando as subtrees de forma que a regra de ordenação continue valendo. É só isso.
Uma rotação à direita
O child da esquerda sobe, o parent desce para virar o child direito dele.
o balance factor de 30 é +2, que é um passo além do limite
os mesmos três valores, um level mais curta
Três escritas de pointer, e a height caiu. Nenhuma comparação de valores foi necessária para decidir o remodelamento — só a observação de que um lado estava alto demais.
Uma rotação à esquerda é o espelho exato: o child da direita sobe e o parent vira o child esquerdo dele. Tudo abaixo se aplica às duas, com esquerda e direita trocadas, e é por isso que implementações escrevem uma e derivam a outra.
Por que a invariante sobrevive
A razão de uma rotação ser segura vale ser explicitada, porque é a única coisa que torna a operação legal em vez de meramente conveniente.
Quando o parent tem uma subtree pendurada no child que sobe, essa subtree tem que se mover. Veja onde ela pousa:
25 fica entre 20 e 30, que é o que torna o próximo passo legal
os mesmos cinco valores na mesma ordem — um rearranjo, não uma edição
O valor 25 estava na subtree direita de 20, então pela invariante ele é maior que 20. E ele estava na subtree esquerda de 30, então é menor que 30. Essas são exatamente as duas condições para ser um membro legal da subtree esquerda de 30 depois da rotação. A subtree não precisa ser verificada; a posição dela já provou.
Esse é o argumento geral. Uma rotação só move a subtree do meio, e a subtree do meio é por definição limitada pelos dois nodes que trocam de lugar — então ela é legal nos dois lados da operação. Leia os valores da esquerda para a direita antes e depois e você obtém a mesma sequência, que é a forma mais forte de ver que nada quebrou.
AVL trees
Uma AVL tree — nome de Adelson-Velsky e Landis, 1962, a primeira BST auto-balanceada — impõe a condição útil mais estrita: para todo node, suas duas subtrees diferem em height por no máximo um.
O balance factor
Cada node carrega, ou consegue calcular, um balance factor: a height da subtree esquerda menos a da direita. Valores legais são -1, 0 e +1. Qualquer outra coisa significa que aquele node precisa de trabalho.
50 pende à esquerda por um e 30 pende à esquerda por um — os dois legais, então nenhuma rotação
Depois de um insert, só os nodes no caminho do leaf novo de volta até a root podem ter mudado de height, então só esses precisam ser verificados. São O(log n) nodes, e a correção em cada um é O(1) — o que é o que mantém o insert inteiro logarítmico.
Os quatro casos
Quando o factor de um node chega a ±2, para que lado rotacionar depende de onde a height em excesso está de fato. Existem quatro configurações, e são duas formas mais os espelhos delas.
Left-left. O node pende à esquerda, e seu child esquerdo também pende à esquerda. Uma rotação à direita resolve — é a figura do começo do artigo.
30 pende à esquerda, 20 pende à esquerda · uma rotação à direita
Left-right. O node pende à esquerda, mas seu child esquerdo pende à direita. Uma única rotação à direita aqui não ajuda — ela só move o problema para o outro lado. Primeiro rotacione o child para a esquerda, o que transforma isso no caso left-left, depois rotacione o node para a direita.
30 pende à esquerda, 10 pende à direita · rotacione 10 à esquerda primeiro, depois 30 à direita
Right-right e right-left são os espelhos desses dois. Então a tabela de decisão inteira é: olhe o pendor do node, olhe o pendor do child dele, e se eles discordam faça uma rotação extra primeiro para fazê-los concordar.
Deleção
Delete funciona do mesmo jeito — faça o delete de BST do artigo anterior, e depois caminhe de volta para cima rebalanceando. Existe uma diferença que vale saber: um insert precisa de no máximo uma rotação para restaurar a tree inteira, enquanto um delete pode precisar de uma em cada level subindo, então O(log n) delas.
Essa assimetria é a semente da próxima seção.
Red-black trees
AVL não é o que sua biblioteca padrão usa. std::map, TreeMap, e o scheduler do kernel do Linux todos usam red-black trees, que impõem uma condição mais frouxa por um mecanismo diferente: todo node é pintado de vermelho ou preto, e as cores obedecem regras que limitam a height indiretamente.
As cinco regras
- Todo node é vermelho ou preto.
- A root é preta.
- Todos os leaves — os children nulos — contam como pretos.
- Os children de um node vermelho são os dois pretos. Ou seja, nunca dois vermelhos seguidos.
- Todo caminho de um node até qualquer descendente nulo passa pelo mesmo número de nodes pretos.
nenhum node vermelho tem child vermelho, e todo caminho root-até-nulo cruza dois pretos
A regra 5 é a que faz o trabalho. Ela diz que a tree é perfeitamente balanceada se você só contar nodes pretos. A regra 4 então limita quantos vermelhos podem preencher um caminho — no máximo um vermelho entre pretos — então o caminho mais longo é no máximo o dobro do mais curto. A height fica limitada por 2 · log₂(n+1), que é O(log n) com uma constante pior que a do AVL.
Por que as bibliotecas escolheram red-black
AVL trees são mais curtas, então seus lookups são marginalmente mais rápidos. Red-black trees ganharam de todo jeito, e a razão é a assimetria mencionada acima.
Reparos em red-black usam recoloração primeiro e só rotacionam quando recolorir não é suficiente. Trocar uma cor é de graça — não move pointer nenhum — então muitas inserções e deleções se resolvem sem nenhuma mudança estrutural. Um delete de red-black precisa de no máximo três rotações, sempre; um delete de AVL pode precisar de O(log n).
Então o trade é: AVL é mais rápida para ler, red-black é mais rápida para escrever e tem um limite mais apertado no trabalho que uma única operação pode fazer. Para um container de propósito geral numa biblioteca padrão, onde escritas são comuns e latência previsível importa, esse é o padrão melhor.
Teste você mesmo
O mesmo playground do artigo anterior, com balanceamento ligado. Aperte Inserir em ordem crescente — a entrada que produziu height 6 da última vez — e veja ela ficar logarítmica. A linha de status nomeia a rotação cada vez que uma dispara, e todo node mostra seu balance factor.
insira, busque ou delete — o caminho acende conforme ele caminha
Vale tentar: insira valores um por um e veja os balance factors subirem em direção a ±2 antes de uma rotação resetá-los. Esse momento, em que a tree nota e reage, é a ideia inteira.
Operações comuns e seus custos
O ponto da tabela é a coluna que deixou de existir. O artigo anterior precisava de uma coluna "degenerate" mostrando O(n); aqui não há caso ruim para mostrar.
| Operação | AVL | Red-black |
|---|---|---|
| Search | ||
| Insert | ||
| Delete | ||
| Rotações por escrita | ||
| Limite de height |
Toda célula é O(log n). As diferenças são fatores constantes, e apontam em direções opostas — que é exatamente por que as duas estruturas ainda existem.
Balanced Trees no mundo real
Containers ordenados em bibliotecas padrão
std::map e std::set em C++, TreeMap e TreeSet em Java, BTreeMap em Rust. Quando uma linguagem oferece um map ordenado ao lado de um hash map, o ordenado é uma balanced tree, e normalmente red-black.
O kernel do Linux
O completely fair scheduler mantém tasks executáveis numa red-black tree indexada por quanto tempo de CPU já tiveram, então "quem roda agora" é o node mais à esquerda. O epoll usa uma para rastrear file descriptors observados, e o sistema de memória virtual usa uma para faixas de endereço. Pior caso previsível é o porquê — um scheduler não pode se permitir um O(n) ocasional.
Índices de banco, e onde B-trees entram
O CREATE INDEX da sua migration é quase certamente uma B-tree, não uma binária. Mesma ideia, constante diferente: em vez de um valor e dois children por node, um node de B-tree guarda centenas de valores e centenas de children, dimensionado para um node encher uma página de disco.
A razão é que o modelo de custo muda. Em memória, o custo são comparações; em disco, o custo são leituras de página, e uma leitura de página custa o mesmo se você usar um valor dela ou quinhentos. Fazer nodes enormes faz a tree ficar rasa — alguns levels cobrem milhões de linhas — então um lookup são poucas leituras de página em vez de vinte.
É para isso que o artigo de hash tables estava apontando ao notar que o PostgreSQL usa índices B-tree por padrão e oferece índices hash apenas como especialização. O padrão B-tree te dá ORDER BY sem sort e BETWEEN sem scan, os dois vindo da propriedade de ordenação, e um índice hash não oferece nenhum.
Quando Balanced Trees deixam a desejar
Você paga em toda escrita. Manter a invariante é trabalho que uma BST comum não faz. Se sua carga é dominada por escrita e lookups são raros, ou se você sabe que sua ordem de inserção já é aleatória, o rebalanceamento é overhead comprando uma garantia de que você não ia precisar.
Uma hash table ainda é mais rápida para lookup exato. O(1) médio bate O(log n) garantido, e a distância é maior do que a notação sugere. Balancear não muda a decisão do artigo anterior: escolha uma tree por ordenação, uma hash table por acesso puro chave-valor.
Continua pointer chasing. Uma balanced tree garante que você toca só log n nodes, não que esses nodes estejam perto um do outro na memória. Vinte cache misses garantidos é melhor que um milhão, e pior que a leitura sequencial que um array dá. É precisamente por isso que o caso orientado a disco virou B-trees em vez de balanced binary trees.
Carga em massa de dados ordenados merece melhor. Se você já tem n valores ordenados, inseri-los um por um custa O(n log n) e uma pilha de rotações, quando você poderia construir uma tree perfeitamente balanceada direto em O(n) pegando o valor do meio como root e recursando. Bibliotecas expõem isso como construtor de faixa; use quando existir.
Correção é genuinamente difícil. Delete é onde balanced trees escritas à mão quebram, e as falhas são silenciosas — a tree continua uma BST válida enquanto perde a garantia de height, então ela funciona e vai ficando devagar. Esta é uma estrutura do tipo use-a-biblioteca.
Resumo
Balanced trees mantêm tudo que uma BST oferece e adicionam um piso sob o pior caso:
- Uma rotação troca um parent com um child — três escritas de pointer, e ela só pode mover a subtree do meio, que a invariante já provou legal nos dois lados
- A sequência in-order é preservada exatamente — então iteração ordenada, range queries, mínimo e máximo todos sobrevivem; só a forma muda
- AVL mantém todo balance factor dentro de um — quatro casos de rotação, que são duas formas e seus espelhos, e os casos duplos existem só para transformar um pendor de dentro num de fora
- Red-black limita a height com cores — nunca dois vermelhos seguidos, contagem igual de pretos em todo caminho, dando
2 log n - Bibliotecas escolheram red-black — recolorir é de graça, então escritas raramente rotacionam, e um delete precisa de no máximo três rotações contra as
O(log n)do AVL - B-trees são a mesma ideia para disco — centenas de valores por node, porque a unidade de custo é leitura de página, não comparação
O insight central é que balancear converte uma garantia de caso médio numa de pior caso, e paga um fator constante nas escritas para isso. Uma BST comum já é O(log n) em entrada aleatória; o que ela não sobrevive é a entrada que você mais provavelmente tem. Rotações são seguro barato contra seus dados chegarem em ordem — e eles vão.
Isso fecha a história de busca. O próximo artigo muda a pergunta. Em vez de "onde está este valor", ele pergunta "qual é o menor valor agora" — e acontece que uma invariante bem mais fraca responde essa, fraca o suficiente para caber a tree inteira num array plano, sem pointer nenhum.