Árvores Rubro-negras: Remoção

Oliveiros Neto
Aug 9, 2017 · 2 min read

Esse texto foi escrito levando em consideração que as pessoas que o vão ler já estão familiarizadas com os conceitos de árvore rubro-negra (ou preta e vermelha), então se você não manja desse assunto indico fortemente que pare um pouco, leia sobre as características fundamentais da mesma, tambem sobre inserção, e depois volte aqui.

Sem muita enrolação começarei o texto deixando claro o seguinte, isso é muito fácil e simples… Até partirmos para a implementação.

Meu objetivo aqui é te levar pro mundo da imaginação onde tudo é lindo e não existe “out of bounds exception”, qualquer coisa além disso virá do seu sangue, suor e linhas de código.


Então vamos lá, começar essa bagaça.

Precisamos nomear alguns nós específicos para melhorar a compreensão a partir daqui. Primeiramente o nó a ser removido será Z. Se Z possui um filhos ou nenhum filho então Y é Z, caso possua dois filhos, então Y é o nó com valor sucessor a Z. X é o filho de Y antes da remoção de Z, ou null caso Y não possua filhos. E pra finalizar W é o tio de X antes da remoção de Z.

Leia o parágrafo acima pelo menos umas 3 vezes, é realmente confuso, eu sei…

E já que entendemos os conceitos de cor do nó e que a busca já está implementada na nossa estrutura, então assumimos que podemos dar de cara com as seguintes quatro situações:

Situação 1: W é vermelho.

Situação 2: W é preto, tem dois filhos e ambos também são pretos.

Situação 3: W é preto, tem dois filhos, o da esquerda é vermelho e o da direita preto.

Situação 4: W é preto e seu filho da direita vermelho.


Situação 1

Como o W é vermelho, inverter as cores dele e do seu pai e aplica a remoção na árvore.

Não se iluda pequeno gafanhoto, o demônio é esperto, ele te dá uma mão mas te pedirá em troca tua alma.


Situação 2

Remove um preto de X, pinta W de vermelho, adiciona o preto ao pai, faz pai o novo X e remove o valor desejado da árvore.

As coisas começaram a ficar mais complicadas aqui…


Situação 3

Nesse caso precisamos inverter as cores de W com a de seu filho da esquerda, realizar uma rotação para a direita e por fim aplicar a remoção.

Uma luz no fim do túnel talvez…


Situação 4

Primeiramente atribuímos a cor do pai de W ao próprio W, pinta o pai de preto, faz o filho da direita de W preto, faz uma rotação pra esquerda e aplica a remoção na árvore.

Essa é a última, graças a Deus!

    Oliveiros Neto
    Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
    Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
    Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade