Exclusão na Árvore Rubro-negra

Inserção, verifica a cor do nó tio.

Exclusão, verifica a cor do nó irmão.

A propriedade principal que se verifica na inserção por dois vermelhos consecutivos.

Na exclusão, se verifica a alteração da altura preta em subárvores.

A eliminação é um processo complexo. Para entender a exclusão, a noção de preto duplo é usada. Quando um nó preto é excluído e substituído por um filho preto, a criança é marcada como preto duplo. A principal tarefa agora se torna converter este preto duplo em preto único.

A etapa inicial da exclusão basta executar padrão comum de uma árvore de busca binária (BST) para apagar.

Sempre acabamos apagando um nó que é uma folha ou tem apenas um filho. Para um nó interno, trocamos com o menor descendente esquerdo do lado direito.

Portanto, só precisamos lidar com casos em que um nó é folha ou tem um filho.

Caso simples

Se um dos nós  é vermelho, marcamos a criança substituída como preto, não ocorre alteração na altura preta, nem dois vermelhos consecutivos, pois não são permitidos na árvore vermelho-preta.

Nos demais casos podemos supor que o nó excluído é uma folha preta, remover isso reduz a altura preta de um nó externo, portanto reorganiza-se a árvore quando a altura preta de alguma subárvore desce de h para h-1.

Caso 1.1

• Se pai é um nó vermelho (a).
• Então tem uma criança (b) que deve ser preto
• Se b tem uma criança vermelha (c)

Caso 1.2

• Se pai é um nó vermelho (a).
• Então tem uma criança (b) que deve ser preto
• Se b não tiver criança vermelha

Caso 2.1.1

• Se pai é um nó preto (a).
• Se a tem uma criança vermelha (b)
• Considere o filho direito de b (c) que deve ser preto.
• Se (c) tem uma criança vermelha (d).

Caso 2.1.2

• Se pai é um nó preto (a).
• Se a tem uma criança vermelha (b)
• Considere o filho direito de b (c) que deve ser preto.
• Se (c) não tiver uma criança vermelha.

Caso 2.2.1

• Se pai é um nó preto (a).
• Se o filho do nó a (c) é preto.
• Se (c) tem uma criança vermelha (d)

Caso 2.2.2

• Se pai é um nó preto (a).
• Se o filho do nó a (c) é preto.
• Se (c) não tiver uma criança vermelha.

Em todos os casos, exceto 2.2.2, a exclusão pode ser completada por uma simples rotação/mudança de cor.

No caso 2.2.2  apenas trocou a cor dos nós, a altura da subárvore diminui e portanto (preto duplo), precisamos avançar na árvore até eventualmente faríamos uma rotação.

Inserção na Árvore Rubro-negra

Em uma árvore AVL, usamos a rotação como uma ferramenta para fazer o balanceamento após a inserção que causou desequilíbrio. Na árvore Rubro negra, alem o do balanceamento, usa a mudança de cor. Tenta-se mudar as cores em primeiro lugar, caso não funcione, segue para a rotação.

Seja k o nó recém-inserido.

• Como no caso de um BST primeiro procurar por k; Isso nos dá o lugar onde temos de inserir k.
• Criamos um novo nó com chave k e inseri-lo neste local.
• O novo nó está colorido em vermelho.
• Como o nó inserido é colorido em vermelho, a altura preta da árvore permanece inalterada.
• No entanto, se o pai do nó inserido também é vermelho, então temos um problema de vermelho duplo.

Caso 1

• O pai do nó inserido (a) é vermelho.
• Pai de (a) deve ser preto (b)
• A outra criança de (b) é preta (c).

Caso 2

• O pai do nó inserido (a) é vermelho.
• Pai de (a) deve ser preto (b)
• A outra criança de (b) também é vermelha (c).

• O pai de b também poderia ser vermelho. Nesse caso, o problema de vermelho duplo ascende um nível.
• Repetimos esse processo no próximo nível.
• Eventualmente, poderemos colorir a raiz vermelha.
• Nesse caso, recolorimos a raiz negra. Isso aumenta a profundidade preta de cada nó externo em 1.
• Na árvore-B (2-4) isso equivale em dividir o nó raiz.

Precisamos fazer no máximo uma rotação, movendo-se para cima da árvore, mas apenas mudando a cor dos nós.

Á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