Introdução às Árvores Vermelha e Preta

A árvore vermelha e preta é uma variação de árvore binária de busca auto-balanceável que garante desempenho eficiente em operações de inserção, remoção e busca — todas com complexidade temporal O(log n). Em comparação com a árvore AVL, ela adota um equilíbrio mais flexível, permitindo alturas ligeiramente assimétricas entre subárvores. Essa relaxação reduz o número de rotações necessárias durante modificações, tornando-a mais vantajosa em cenários com muitas atualizações.

Essa estrutura é amplamente utilizada em bibliotecas padrão, como no C++ STL (em std::map, std::set) e no Java (TreeMap, TreeSet), graças ao seu bom desempenho médio e estabilidade.

Propriedades Fundamentais

Uma árvore vermelha e preta atende às seguintes regras:

1. Cada nó é colorido como vermelho ou preto.
2. O nó raiz é sempre preto.
3. Todos os nós folhas (nulos) são considerados pretos.
4. Nenhum nó vermelho pode ter um filho vermelho (ou seja, não há dois vermelhos consecutivos).
5. Em qualquer caminho da raiz até uma folha, o número de nós pretos é constante (chamado de altura negra).

A última propriedade garante o balanceamento aproximado: a altura máxima da árvore nunca excede o dobro da altura mínima.

Rotações: Operações Básicas de Rebalanceamento

As rotações são transformações locais que preservam a ordem da busca binária enquanto ajustam a estrutura da árvore. Existem dois tipos principais: rotação à esquerda e rotação à direita.

Rotação à Esquerda

Aplicada quando um nó precisa ser promovido à posição de pai, movendo-se para a esquerda na hierarquia. A operação assume que o nó tem um filho direito válido.

rotacaoEsquerda(arvore, x) {
    y = direita[x]
    direita[x] = esquerda[y]
    se esquerda[y] != nulo
        pai[esquerda[y]] = x
    pai[y] = pai[x]
    se pai[x] == nulo
        raiz[arvore] = y
    senao se x == esquerda[pai[x]]
        esquerda[pai[x]] = y
    senao
        direita[pai[x]] = y
    esquerda[y] = x
    pai[x] = y
}

Rotação à Direita

Inversa da rotação à esquerda, usada para subir um nó pela esquerda.

rotacaoDireita(arvore, y) {
    x = esquerda[y]
    esquerda[y] = direita[x]
    se direita[x] != nulo
        pai[direita[x]] = y
    pai[x] = pai[y]
    se pai[y] == nulo
        raiz[arvore] = x
    senao se y == direita[pai[y]]
        direita[pai[y]] = x
    senao
        esquerda[pai[y]] = x
    direita[x] = y
    pai[y] = x
}

Inserção em Árvore Vermelha e Preta

A inserção ocorre em três etapas:

1. Inserção inicial: Insere-se o novo nó como em uma árvore binária comum, mantendo a ordenação.
2. Coloração: O novo nó é pintado de vermelho. Isso evita alterar a contagem de nós pretos nos caminhos (preservando a propriedade 5).
3. Reparo: Se a inserção violar alguma propriedade (como dois vermelhos consecutivos), aplica-se uma série de recolorações e rotações para restaurar as condições.

O algoritmo de reparo trata três casos principais com base na cor do tio do nó inserido e sua posição relativa:

• Caso 1: Tio vermelho – Recolora-se pai, tio e avô. O problema sobe para o nível do avô.
• Caso 2: Tio preto, nó à direita – Aplica-se rotação à esquerda no pai para transformar na configuração do Caso 3.
• Caso 3: Tio preto, nó à esquerda – Recolora-se pai e avô, e realiza-se rotação à direita no avô.

Após essas correções, a raiz é forçada a ser preta para garantir a propriedade 2.

Remoção em Árvore Vermelha e Preta

A remoção também segue duas fases principais:

1. Eliminação padrão: Remove-se o nó como em uma BST comum. Se o nó removido era preto, isso pode quebrar a propriedade 5 (desequilíbrio na contagem negra).
2. Rebalanceamento: Usa-se uma função de reparo para corrigir a inconsistência causada pela perda de um nó preto.

Durante o reparo, o nó substituto (x) é tratado temporariamente como tendo uma "cor extra" (preto duplo). O objetivo é empurrar essa cor extra para cima até que possa ser eliminada via recoloração ou rotação. Os quatro casos principais envolvem o irmão do nó problemático e os filhos dele:

• Caso 1: Irmão vermelho – Transforma a situação em um dos outros casos via rotação.
• Caso 2: Irmão preto com ambos filhos pretos – Recolora o irmão e move o problema para o pai.
• Caso 3: Irmão preto com filho esquerdo vermelho e direito preto – Prepara para o Caso 4 com uma rotação.
• Caso 4: Irmão preto com filho direito vermelho – Realiza rotação final, redistribui cores e elimina a cor extra.

Após resolver o Caso 4, o nó problemático é movido para a raiz e colorido como simplesmente preto, encerrando o processo.