No post anterior, discutimos a introdução a Red-Black Trees. Neste post, a inserção é discutida. Na inserção da árvore AVL, usamos a rotação como uma ferramenta para fazer o balanceamento após a inserção. Na árvore Red-Black, nós utilizamos duas ferramentas para fazer o balanceamento.
- Recoloração
- Rotação
Recoloração é a mudança de cor do nó, ou seja, se ele for vermelho então mude-o para preto e vice versa. Deve-se notar que a cor do nó NULL é sempre preta. Além disso, nós sempre tentamos primeiro a recoloração, se a recoloração não funcionar, então nós vamos para a rotação. Segue-se um algoritmo detalhado. Os algoritmos têm principalmente dois casos, dependendo da cor do tio. Se o tio for vermelho, nós recolhemos. Se o tio for preto, fazemos rotações e/ou recolorações.
A representação com que vamos trabalhar é:
Esta representação é baseada em X
Logic:
Primeiro, tem de inserir o nó de forma semelhante à de uma árvore binária e atribuir-lhe uma cor vermelha. Agora, se o nó for um nó raiz, então mude sua cor para preto, mas se ele não verificar a cor do nó pai. Se sua cor for preta então não mude a cor, mas se não for, ou seja, vermelha então verifique a cor do tio do nó. Se o tio do nó tiver uma cor vermelha então mude a cor do pai e do tio do nó para preto e a do avô para vermelho e repita o mesmo processo para ele (isto é, avô).
>
Mas, se o tio do nó tiver uma cor preta então existem 4 caixas possíveis:
>
- Caixa Esquerda Esquerda (rotação LL):
- Caixa Esquerda Direita (rotação LR):
>
>
- Caixa-direita direita (rotação RR):
>
>
>>
- >
- Caixa-esquerda direita (rotação RL):
>
>
Agora, após estas rotações, se as cores dos nós não coincidirem, então lembre-se delas.
Algoritmo:
Deixe x ser o nó recém inserido.
- Realize a inserção padrão BST e faça a cor dos nós recém inseridos como Vermelho.
- Se x for a raiz, mude a cor de x como PRETO (a altura preta da árvore completa aumenta em 1).
- Faça o seguinte se a cor do pai de x não for PRETO e x não for a raiz.
a) Se o tio de x for VERMELHO (O avô deve ter sido preto da propriedade 4)
(i) Mude a cor do pai e do tio como PRETO.
(ii) Cor de um avô como VERMELHO.
(iii) Alterar x = avô de x, repita os passos 2 e 3 para o novo x.b) Se o tio de x for PRETO, então pode haver quatro configurações para x, x’s parent (p) and x’s grandparent (g) (Isto é semelhante à Árvore AVL)
(i) Left Left Left Case (p é filho esquerdo de g e x é filho esquerdo de p)
(ii) Left Right Case (p é esquerda filho de g e x é o filho direito de p)
(iii) Mala direita (Espelho da caixa i)
(iv) Mala direita esquerda (Espelho da caixa ii)
Exemplo: Criação de uma árvore preta vermelha com elementos 3, 21, 32 e 17 numa árvore vazia.
Solução:
Quando o primeiro elemento é inserido é inserido como um nó-raiz e como nó-raiz tem cor preta, então adquire a cor preta.
O novo elemento é sempre inserido com uma cor vermelha e como 21 > 3 então torna-se a parte da sub-árvore direita do nó-raiz.
Agora, como inserimos 32 vemos que há um par pai-criança vermelho que viola a regra da árvore vermelha-preta, então temos que rodá-la. Além disso, vemos as condições de rotação RR (considerando o nó nulo do nó raiz como preto) então após a rotação como o nó raiz não pode ser Vermelho então temos que realizar a recoloração na árvore resultando na árvore mostrada acima.
Agora quando inserimos o novo elemento o nó pai e o filho com cor vermelha aparecem novamente e aqui temos de os recolorir. Vemos que tanto o nó pai como o nó tio têm cor vermelha, então simplesmente mudamos a cor deles para preto e mudamos a cor do avô para vermelho. Agora, como um avô é o nó raiz, então mudamos novamente a sua cor para preto, resultando na árvore mostrada acima.
Final Tree Structure:
A árvore final ficará assim
Please refer C Program for Red Black Tree Insertion for complete implementation of the above algorithm.
Red-Black Tree | Set 3 (Delete)