Árvores Rubro-negras: Remoção
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!