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.