Árvores Rubro-Negras (Red-Black Trees)

1. O Padrão da Indústria

Enquanto a AVL é matematicamente elegante, a Árvore Rubro-Negra (Red-Black Tree) é a escolha pragmática da indústria. Ela é a estrutura de dados por trás de: - java.util.TreeMap e TreeSet. - std::map, std::set e std::multiset do C++. - O agendador de processos “Completely Fair Scheduler” do kernel Linux.

Sua vantagem é realizar menos rotações que a AVL, trocando ajustes estruturais caros por simples mudanças de cor (recoloração).

2. As 5 Regras de Ouro

Uma BST é uma Árvore Rubro-Negra se satisfizer simultaneamente as seguintes propriedades:

  1. Cor: Todo nó é Vermelho ou Preto.
  2. Raiz: A raiz é sempre Preta.
  3. Folhas: Todas as folhas (null ou NIL) são consideradas Pretas.
  4. Regra do Vermelho: Se um nó é Vermelho, seus dois filhos devem ser Pretos. (Não existem dois vermelhos consecutivos no caminho).
  5. Altura Negra: Todo caminho de um nó até qualquer uma de suas folhas descendentes contém o mesmo número de nós Pretos.

Consequência

O caminho mais longo (intercalando Vermelho-Preto) não é mais do que \(\boldsymbol{2 \times}\) maior que o caminho mais curto (só Pretos). Isso garante uma altura \(O(\log N)\), levemente maior que a AVL, mas suficiente para operações rápidas.

3. Lógica de Inserção

Todo novo nó inserido começa como Vermelho. Por quê? - Inserir Vermelho não viola a altura negra (Propriedade 5). - Só viola a Propriedade 4 (Vermelho-Vermelho) se o pai for Vermelho. E isso é mais fácil de corrigir localmente.

Algoritmo de Correção

Se inserimos um nó \(Z\) (Vermelho) e o pai \(P\) também é Vermelho, temos um conflito. Olhamos para o Tio \(U\) (irmão do pai).

Caso 1: Tio é Vermelho (Recoloração) - Pinta Pai e Tio de Preto. - Pinta Avô de Vermelho. - O problema sobe para o Avô (verifica recursivamente).

Caso 2: Tio é Preto (Rotação) - Se formamos um “joelho” (Ziguezague), fazemos rotação dupla (primeiro gira filho, depois pai). - Se formamos uma “linha” (Zigue-zague), fazemos rotação simples no Avô e trocamos as cores de Pai e Avô.

4. Usando na Prática (Java TreeMap)

Como a implementação de uma RB-Tree completa é extensa e propensa a erros (centenas de linhas para cobrir todos os Edge Cases de remoção), em problemas de maratona e sistemas reais, usamos as bibliotecas padrão.

TreeMap (Mapa Ordenado)

import java.util.Map;
import java.util.TreeMap;

public class ExemploRB {
    public static void main(String[] args) {
        // Chaves são ordenadas naturalmente (Inteiros crescentes)
        TreeMap<Integer, String> agenda = new TreeMap<>();
        
        agenda.put(10, "Reunião");
        agenda.put(5, "Academia");
        agenda.put(20, "Jantar");
        
        // iteração em Ordem: 5 -> 10 -> 20
        for (var entry : agenda.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        
        // Poderes exclusivos de Árvores (Range Queries)
        System.out.println("Primeiro evento: " + agenda.firstEntry());
        System.out.println("Último evento: " + agenda.lastEntry());
        
        // Ceiling e Floor (Teto e Piso)
        // ceilingKey(k): menor chave >= k
        // floorKey(k): maior chave <= k
        System.out.println(agenda.ceilingKey(7)); // Retorna 10
        System.out.println(agenda.floorKey(7));   // Retorna 5
        
        // SubMap: Faixa [5, 15)
        System.out.println(agenda.subMap(5, 15)); 
    }
}

TreeSet (Conjunto Ordenado)

Ideal para manter uma lista de elementos únicos ordenados dinamicamente e buscar “o próximo maior”.

import java.util.TreeSet;

public class ExemploSet {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(10);
        set.add(5);
        set.add(20);
        
        // Operações O(log N)
        if (set.contains(10)) System.out.println("Tem 10");
        
        set.remove(5); 
        
        System.out.println(set.higher(10)); // O próximo estrito > 10 => 20
        System.out.println(set.lower(10));  // O anterior estrito < 10 => null (pois removemos o 5)
    }
}

5. Comparativo Final (Hash vs Tree)

Quando usar HashMap (\(O(1)\)) e quando usar TreeMap (\(O(\log N)\))?

Critério HashMap / HashSet TreeMap / TreeSet
Velocidade Pura Mais rápido para get/put. Levemente mais lento (fator constante).
Ordenação Aleatória (caótica). Sempre ordenado.
Busca de Faixa Impossível. Não dá para pedir “chaves entre 10 e 20”. Eficiente (subMap, tailMap).
Próximo/Anterior Impossível. higher, lower, ceiling, floor.
Memória Maior overhead se tabela estiver vazia (array alocado). Overhead por nó (ponteiros e cor).

Regra de Ouro: Use HashMap por padrão. Use TreeMap apenas se precisar da ordem ou de operações de faixa.

Back to top