Árvores AVL e vermelho-pretas

Uma BST simples pode ter altura linear. Uma árvore equilibrada conserva a ordem de pesquisa e acrescenta um invariante que força altura logarítmica. Uma rotação, ou seja, um rearranjo local que troca uma raiz com um filho, corrige a forma sem mudar a sequência em-ordem.

A escolha da rotação depende do lado pesado do filho. Se o filho está pesado do lado exterior, uma rotação chega; se está pesado do lado interior, são precisas duas. A tabela seguinte fixa essa decisão antes dos exemplos.

Rotações e ordem

Numa rotação à direita, a raiz local z tem filho esquerdo y. Chamamos A à subárvore esquerda de y, B à direita de y e C à direita de z. Na animação, as três subárvores são não vazias e cada triângulo representa todos os seus nós.

As chaves de B são maiores que y, porque B está à sua direita. Também são menores que z, porque B pertence à subárvore esquerda de z. Por isso, podes passar B de y.right para z.left sem perder a ordem de pesquisa. Depois, y torna-se a raiz local e z fica como seu filho direito. A continua à esquerda de y e C à direita de z.

Antes e depois, a sequência em-ordem visita os nós de A, depois y, os nós de B, z e os nós de C. A rotação também funciona se alguma destas subárvores for vazia. A rotação à esquerda é simétrica.

Uma rotação mexe num número constante de ligações, logo custa $O(1)$. Se guardas alturas ou tamanhos nos nós, atualiza primeiro a antiga raiz e depois a nova, porque o segundo cálculo depende do primeiro. Também tens de ligar a nova raiz ao pai ou à raiz da árvore.

Invariante AVL

Usamos altura de vazio -1 e fator de equilíbrio $b=h_{esq}-h_{dir}$. Cada nó AVL satisfaz $b\in\{-1,0,1\}$. Não é necessário que as duas subárvores tenham o mesmo número de nós.

Depois de inserires uma folha como numa BST, sobe pelo caminho de inserção, atualiza alturas e trata o primeiro desequilíbrio:

Ao inserires 30, 10 e 20, a raiz 30 fica com fator 2 e o filho 10 com fator -1. Uma rotação à esquerda em 10 cria a cadeia com 20 acima de 10; uma rotação à direita em 30 coloca 20 na raiz, com filhos 10 e 30. A em-ordem continua 10, 20, 30.

A primeira rotação transforma o ramo interior em exterior; a segunda repõe o equilíbrio. Compara a em-ordem dos três desenhos, que é sempre 10,20,30.

#include <algorithm>
#include <iostream>
class AVL {
    struct No { int x, h = 0; No* e = nullptr; No* d = nullptr; };
    No* raiz = nullptr;
    static int altura(No* p) { return p ? p->h : -1; }
    static void atualizar(No* p) { p->h = 1 + std::max(altura(p->e), altura(p->d)); }
    static No* direita(No* p) {
        No* q = p->e; p->e = q->d; q->d = p;
        atualizar(p); atualizar(q); return q;
    }
    static No* esquerda(No* p) {
        No* q = p->d; p->d = q->e; q->e = p;
        atualizar(p); atualizar(q); return q;
    }
    static No* inserir(No* p, int x) {
        if (!p) return new No{x};
        if (x < p->x) p->e = inserir(p->e, x);
        else if (p->x < x) p->d = inserir(p->d, x);
        else return p;
        atualizar(p);
        const int b = altura(p->e) - altura(p->d);
        if (b > 1) {
            if (x > p->e->x) p->e = esquerda(p->e);
            return direita(p);
        }
        if (b < -1) {
            if (x < p->d->x) p->d = direita(p->d);
            return esquerda(p);
        }
        return p;
    }
    static void destruir(No* p) { if (p) { destruir(p->e); destruir(p->d); delete p; } }
    static void mostrar(No* p, bool& primeiro) {
        if (!p) return;
        mostrar(p->e, primeiro);
        std::cout << (primeiro ? "" : " ") << p->x; primeiro = false;
        mostrar(p->d, primeiro);
    }
public:
    AVL() = default;
    AVL(const AVL&) = delete;
    AVL& operator=(const AVL&) = delete;
    ~AVL() { destruir(raiz); }
    void inserir(int x) { raiz = inserir(raiz, x); }
    void mostrar() const { bool primeiro = true; mostrar(raiz, primeiro); std::cout << '\n'; }
    int altura() const { return altura(raiz); }
};
int main() {
    AVL a;
    for (int x : {30, 10, 20, 40, 50, 20}) a.inserir(x);
    a.mostrar();
    std::cout << "altura: " << a.altura() << '\n';
    AVL vazia; std::cout << "vazia: " << vazia.altura() << '\n';
}

O programa ignora duplicados e mantém alturas durante a inserção. Não implementa remoção. Depois de rodar no primeiro nó desequilibrado, a subárvore recupera a altura anterior à inserção; continua a atualizar os antepassados, mas não precisa de outra reparação.

Na remoção, começa por retirar como numa BST e verifica todos os antepassados. O pressuposto muda: uma reparação pode deixar a subárvore mais baixa e propagar o desequilíbrio para cima, por isso um único arranjo pode não chegar. A decisão usa o fator do filho, porque a chave apagada já não identifica o ramo pesado. Com b=2 e filho de fator zero ou positivo, usa uma rotação simples à direita; com filho de fator negativo, usa uma dupla. O caso b=-2 é simétrico. O efeito com filho de fator zero merece atenção: a rotação simples repõe o equilíbrio, mas a altura da subárvore não diminui, por isso continua a verificar os antepassados acima.

Porque a altura AVL é logarítmica

Pesquisa, inserção e remoção custam $O(\log(n+1))$; as rotações não acrescentam um fator logarítmico por nível.

Invariantes vermelho-pretos

Uma árvore vermelho-preta é uma BST com uma cor por nó e folhas vazias NIL consideradas pretas. A raiz é preta; um nó vermelho não pode ter filho vermelho; todos os caminhos de um nó até folhas NIL têm o mesmo número de nós pretos, segundo uma convenção fixa de contagem.

Chama altura preta ao número de nós pretos num caminho descendente, excluindo o nó inicial e incluindo a folha NIL. Uma subárvore com altura preta b tem pelo menos $2^b-1$ nós internos. Como não há dois vermelhos consecutivos, a altura é no máximo duas vezes a altura preta, dando $h\le2\log_2(n+1)$. O equilíbrio é menos restrito que na AVL, mas continua a garantir operações logarítmicas.

Inserção e reparação vermelho-preta

Insere o nó como numa BST e pinta-o de vermelho. Assim não alteras a altura preta dos caminhos. Se o pai for preto, não há conflito. Se o pai for vermelho, o avô existe porque a raiz é preta:

• Com tio vermelho, pinta pai e tio de preto e avô de vermelho. O número de pretos nos caminhos mantém-se; o conflito pode subir para o avô.
• Com tio preto exterior, roda no avô e troca as cores do pai e do avô: o novo topo fica preto e os filhos vermelhos deixam de ser consecutivos.
• Com tio preto, uma configuração interior precisa primeiro de uma rotação no pai para ficar exterior. Depois roda no avô e troca as cores do pai e do avô. O novo topo local fica preto e os filhos vermelhos deixam de ser consecutivos.

No fim, pinta a raiz de preto. As configurações têm casos simétricos para o pai ser filho esquerdo ou direito. Não decidas uma rotação apenas por três valores: as cores e o lado do tio também importam.

A remoção vermelho-preta fica aqui como enquadramento: a fonte de 2025/26 indica que não detalha esse procedimento, por isso não a uses como receita de exame. Na remoção, retirar um nó vermelho não reduz a altura preta. Retirar um nó preto pode deixar um ramo com um preto a menos. A reparação compara o irmão e os seus filhos: um irmão vermelho converte-se por rotação e recoloração para um caso com irmão preto; com filhos do irmão pretos, recolore e propaga a falta; com um filho vermelho adequado, rotações e recolorações restauram a altura preta. Estes passos devem respeitar as folhas NIL, que não são valores do conjunto.

AVL conserva altura mais apertada e pode favorecer pesquisa. Vermelho-preta admite mais variação e pode requerer menos reparações em alterações. A escolha prática depende do padrão de operações e da implementação; a notação assintótica não prevê qual será mais rápida numa medição concreta.

No modelo de armazenamento dos slides, uma cor precisa de um bit e os três fatores AVL precisam de dois bits. Guardar a altura completa num inteiro, como no programa desta página, é outra escolha. Os bytes reais por nó dependem dos campos, do alinhamento e da implementação; a comparação de bits de informação não determina esse tamanho em memória.