Árvores balanceadas

Na árvore binária de busca, buscar, inserir e remover custam , e a altura depende só da ordem em que as chaves chegam: entre , no melhor caso, e , quando as chaves chegam ordenadas. E chaves ordenadas ou quase ordenadas são comuns na prática: matrículas, datas, códigos sequenciais, registros lidos de um arquivo já ordenado.

As árvores balanceadas resolvem esse problema: são árvores de busca que modificam a inserção e a remoção para que a altura fique sempre , qualquer que seja a ordem das operações. Esta página apresenta o que elas têm em comum; as próximas tratam de duas delas, a árvore AVL e a árvore rubro-negra (na variante LLRB).

O que é estar balanceada

Repare que a definição fala de uma família de árvores, definida por alguma regra, e da garantia que a regra dá. Diferentes regras levam a diferentes famílias:

• balanceamento por altura: em todo nó, as alturas da SAE e da SAD diferem de no máximo 1. É o critério das árvores AVL;
• balanceamento por peso: em todo nó, o número de nós da SAE e o da SAD são iguais ou próximos;
• critérios mais relaxados, como o das árvores rubro-negras: nenhum caminho da raiz até um NULL tem mais que o dobro do comprimento de outro.

Fator de balanceamento

Para medir o quanto um nó está "torto", comparamos as alturas das suas subárvores.

Alguns livros usam a diferença ao contrário (SAD menos SAE), o que só troca os sinais. E a convenção de altura (folha com altura 0 ou 1) não muda nada: o fator é uma diferença de alturas.

Dois detalhes da figura. Em (a), a árvore não é cheia (40 e 70 têm um filho só), e mesmo assim todos os nós têm : estar balanceada no critério da AVL não exige que a árvore seja perfeita. Em (b), o desequilíbrio não aparece em um nó só: ele se propaga para cima, atingindo o 30 e o seu ancestral 50.

O programa abaixo insere as chaves da entrada em uma ABB comum e imprime, em ordem, a altura e o fator de cada nó. A entrada é a da árvore (b); troque por 7 e 50 30 70 20 40 80 35 para a árvore (a), ou por 7 e 1 2 3 4 5 6 7 para ver uma árvore degenerada.

Rebalancear, mas localmente

A inserção e a remoção da ABB não olham para a forma da árvore. Basta inserir 10, 20 e 30, nessa ordem, para a raiz ficar com . Uma árvore balanceada precisa, depois de cada inserção ou remoção, detectar os nós desequilibrados e reorganizar a árvore, sem perder a ordem das chaves.

O desafio que a AVL e a rubro-negra resolvem é rebalancear com mudanças locais: apenas nos nós do caminho entre a raiz e o ponto da inserção ou da remoção. Como esse caminho tem nós (a árvore está balanceada antes da operação), a operação inteira, incluindo o rebalanceamento, continua custando . A ferramenta para essas mudanças locais é a rotação.

Rotações

Uma rotação reorganiza um nó e um dos seus filhos, trocando quem é pai de quem, sem mudar a ordem das chaves.

Na rotação à direita em , o filho esquerdo sobe e desce para a direita de . A subárvore , que estava à direita de , passa para a esquerda de : é o único lugar em que ela pode ficar, porque as suas chaves estão entre e . A rotação à esquerda é o espelho, e uma desfaz a outra.

/* Rotação à direita em y: o filho esquerdo x sobe e y vira filho direito
   de x. Devolve a nova raiz da subárvore (x). */
No *rotacaoDireita(No *y) {
    No *x = y->esq;
    y->esq = x->dir;        /* a subárvore do meio (B) muda de pai */
    x->dir = y;
    return x;
}

/* Rotação à esquerda em x: o simétrico da anterior */
No *rotacaoEsquerda(No *x) {
    No *y = x->dir;
    x->dir = y->esq;        /* a subárvore do meio (B) muda de pai */
    y->esq = x;
    return y;
}

São só três atribuições de ponteiros, e nenhuma delas toca nas chaves nem nos valores: os nós mudam de lugar levando o seu par chave-valor junto.

O que a rotação muda são as profundidades:

É por isso que a rotação conserta um nó com a SAE alta demais: a parte mais funda, em , sobe, à custa de , que era mais baixa. Na AVL, o caso em que a parte funda está em , que não sobe, pede duas rotações, e esse é o assunto da próxima página.

O programa abaixo monta uma árvore com a SAE mais alta, aplica uma rotação à direita na raiz (a altura cai de 3 para 2) e depois a desfaz com uma rotação à esquerda. A em-ordem é a mesma nos dois momentos.

Panorama das árvores balanceadas

A AVL e a rubro-negra resolvem o mesmo problema com trocas diferentes: a AVL é balanceada com mais rigor e, por isso, um pouco mais baixa, o que favorece as buscas; a rubro-negra tolera mais desequilíbrio e, em troca, costuma reorganizar menos nas inserções e remoções. Nesta disciplina, estudaremos a AVL e a LLRB (left-leaning red-black tree), uma variante da rubro-negra proposta por Sedgewick em 2008, com código bem mais curto, que corresponde diretamente às árvores 2-3. As árvores B ficam para Estrutura de Dados II.

Exercícios

Encontre e corrija o erro

Programa 1

No *x = y->esq;
y->esq = x->dir;
x->dir = y;
return x;

Programa 2

raiz->esq = rotacaoDireita(raiz->esq);

Programa 3

if (fb < -1 || fb > 1)
    return false;
return ehBalanceada(r->esq) && ehBalanceada(r->dir);

Implemente

Fatores de balanceamento em O(n). Grave o fator de balanceamento de todos os nós de uma árvore, na ordem simétrica, em . Os testes incluem árvores degeneradas com 40 mil nós, nas quais chamar uma função altura em cada nó não termina a tempo.

Rotações. Implemente rotacaoDireita e rotacaoEsquerda. Os testes aplicam sequências de rotações em vários pontos de uma ABB (incluindo rotações sem subárvore do meio) e conferem a forma da árvore, a ordem das chaves e os valores. A última bateria faz 300 mil rotações aleatórias em uma árvore com 100 mil nós.

Referências

• W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
• A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
• R. Sedgewick e K. Wayne. Algorithms. 4ª ed. Addison-Wesley, 2011. Seção 3.3.
• R. Sedgewick. Left-leaning Red-Black Trees. 2008.
• D. Galles. Visualizações interativas: ABB, AVL e rubro-negra. University of San Francisco.