Árvore Rubro-Negra

CÓDIGO-FONTE: https://github.com/r-bauer/rbTree/archive/master.zip

Conceito

Uma alternativa para a árvore AVL é utilizar o conceito conhecido como árvore rubro-negra, originalmente concebida por Rudolf Bayer como “Árvore B de simetria binária”, mas teve seu nome alterado em 1978 dentro de um artigo publicado por Sedgewick e Guibas sobre biblioteca de controle bicromáticas para balanceamento de árvores, curiosamente a cor vermelha foi escolhida por prover uma melhor apresentação na impressão final feita pela impressora a laser do escritório em que trabalhavam.

A árvore rubro-negra tem em seu cerne uma árvore de busca binária, entretanto faz uso de  novos conceitos.

1. Cada nó representa uma cor vermelha ou preta.
• Uma vez que foi nomeada rubro negra, obvio (sic)
2. Raiz tem cor fixa preta
• Uma regra imposta por conceito, na prática não influencia a análise
3. Todas as folhas são pretas
• Nós vazios ou nulos, são considerados de cor preta, outro caso em que a não afeta a implementação, novamente inserido por conceito
4. Proibido ter dois nós vermelhos consecutivos
5. Todas as folhas da árvore têm de ter a mesma profundidade negra (número de nós pretos entre a raiz e a folha)
• Aqui tem a grande diferencial, basta fazer um paralelo com uma árvore B de ordem 4 para compreender essas duas últimas regras

Exemplos de árvores rubro negras com profundidade 2

Adicionar legenda

Dois exemplos de regra violada, Duplo vermelho, profundidade negra irregular

Rubro negra para árvore-B(2-4)

• Qualquer árvore vermelha-preta pode ser convertida em uma árvore-b(2-4).
• Pegue um nó preto e seus filhos vermelhos (no máximo 2) e combine-os em um nó de uma árvore-b(2-4).
• Cada nó assim formado tem pelo menos 1 e no máximo 3 chaves.
• Como a altura preta de todos os nós externos é a mesma, na árvore-b(2-4) resultante todas as folhas estão no mesmo nível.

Árvore-B(2-4) para rubro negra

• Qualquer árvore 2-4 pode ser convertida em uma árvore vermelha-preta.
• Substituímos um nó da árvore 2-4 com um nó preto e 0/1/2 nós vermelhos que são filhos do nó preto.
• A altura da árvore 2-4 é a altura preta da árvore vermelha-preta criada.
• Cada nó vermelho tem uma criança negra.

O principal ponto que pode-se concluir, a criação da árvore rubro negra é como tratar toda a abstração de árvore-B (2-4) em forma de árvore binária, obedecendo as regras de que indicar vermelho ou preto é um simples dispositivo de marcação para facilitar a interpretação.

Para mais informações, existem outros 2 artigos detalhando o processo de inclusão e exclusão No github é possível baixar todo o código desta implementação no seguinte endereço:
https://github.com/r-bauer/rbTree