Remover nós de uma árvore vermelha e preta não é uma tarefa fácil, então faz sentido dividi-la em várias partes e considerar cada caso separadamente.
cartoonbank.ru
No último artigo, examinamos as regras para formar uma árvore de pesquisa vermelho e preto e consideramos os casos de balanceamento ao adicionar elementos.
Agora vamos falar sobre a exclusão de itens.
Veja, por exemplo, esta árvore vermelho-preto:
Lembre-se de que a propriedade principal de uma árvore vermelho-preto é a mesma altura preta à esquerda e à direita de cada nó. Portanto, nas figuras, ao lado de cada nó, iremos indicar o valor da altura do preto, para que a cada estágio possamos verificar sua estabilidade.
Dividir para reinar
Remover um elemento de uma árvore vermelho-preta não é uma tarefa tão fácil como pode parecer à primeira vista, então proponho dividi-lo em várias partes e considerar cada uma separadamente.
Primeiro, vamos dividir a tarefa em duas categorias:
- cor do nó removido: K ou H
- número de nós filhos: 2, 1 ou 0
Como resultado, obtemos uma matriz de 6 opções: K2, Ch2, K1, Ch1, K0, Ch0.
Para cada opção, o nó correspondente de nossa árvore é indicado.
Vamos considerar o processo de remoção de cada opção.
K2 - nó vermelho com dois filhos
A tarefa de deletar um nó com dois filhos é reduzida à tarefa de deletar um nó com um ou zero filhos.
Para fazer isso, você precisa encontrar o elemento mais próximo que seja menor ou maior que o excluído e trocá-los.
Observe que ao trocar os elementos, você precisa alterar apenas os valores nos nós, e deixar a cor da mesma, para não quebrar a estrutura da árvore e não alterar a altura do preto.
Após a troca, você precisa remover o item de seu novo local. Será o elemento mais à direita no ramo esquerdo (máximo à esquerda), ou o mais à esquerda à direita (mínimo à direita), em qualquer caso não terá um filho à esquerda ou direita. Assim, a tarefa de remover um nó com 2 filhos é reduzida à tarefa de remover um elemento com 1 ou 0 filhos:
- K2 => K1 ou K0
Ch2 - nó preto com dois filhos
Da mesma forma que no caso anterior, daremos um exemplo de exclusão do nó preto 16.
Como você pode ver, após a troca, a tarefa se reduz a excluir um elemento com um filho:
- Ch2 => Ch1 ou Ch0
K1 - nó vermelho com uma criança
Se o nó vermelho não tem um filho, então ele tem um elemento NIL preto e a altura preta do nó vermelho é 1. Portanto, por outro lado, a altura preta também deve ser 1. Mas como o nó vermelho não pode ter um filho vermelho cores, então seu outro filho deve ser preto. Como a altura do preto deve ser 1, ele só pode ser um elemento NIL preto, já que no caso de um elemento preto normal, a altura será maior.
Assim, o caso K1 não ocorre.
Ch1 - nó preto com uma criança
Se o elemento preto não tiver um filho, então haverá um elemento NIL preto com uma altura preta 1. Portanto, do outro lado deve haver um nó vermelho sem filhos. Para remover tal elemento, basta transferir o valor do elemento vermelho para o nó preto, enquanto a altura do preto será preservada.
K0 - nó vermelho sem filhos
O caso mais simples. Simplesmente removemos o elemento, substituindo-o por uma referência NIL:
Remover o elemento vermelho não altera a altura do preto.
CH0 - nó preto sem filhos
Remover um nó preto sem filhos também é muito simples: nós o substituímos por uma referência a NIL.
Você acha que isso é quase tudo? Haha, seis vezes.
Depois de remover o elemento preto, a altura preta da subárvore muda e você precisa equilibrá-la para seu pai.
O elemento excluído nas figuras é denotado por x, sua altura - h. Quando apenas começamos o equilíbrio, h = 1, mas com chamadas recursivas pode aumentar.
Para definição, vamos estabelecer que o elemento excluído era o filho certo. Após a remoção, sua altura diminuiu e tornou-se h. Isso significa que a altura do filho esquerdo permanece h + 1. Precisamos alinhar as alturas das subárvores esquerda e direita e torná-las iguais a h + 1.
Sugiro dividir a tarefa em várias partes novamente. Que opções nós temos?
O pai pode ser vermelho ou preto. O filho esquerdo também pode ser preto ou vermelho. E o filho certo é sempre preto - foi a partir daí que chegamos ao equilíbrio após a remoção.
Existem 6 casos diferentes a serem considerados:
- KCH1 e KCH2 - o pai é vermelho, o filho esquerdo é preto.
- CHK3 e CHK4 - o pai é negro, o filho esquerdo é vermelho.
- HH5 e HH6 - o pai é negro, o filho esquerdo é negro.
Vamos estocar paciência e pipoca, o mais interessante e misterioso que virá.
1 - pai vermelho, filho esquerdo preto com netos pretos
Enquanto tivermos os nós vermelhos, podemos movê-los e / ou recolori-los para restaurar o equilíbrio da altura preta. Nesse caso, podemos diminuir a cor vermelha do pai para o filho esquerdo, alinhando assim a altura preta do pai:
certifique-se de verificar novamente a partir da figura se as alturas pretas dos nós a e b são preservadas e a altura de toda a subárvore se tornou a mesma e igual a h + 1.
KCH2 - o pai é vermelho, o filho esquerdo é preto com o neto vermelho esquerdo.
Nesse caso, apenas repintar não é suficiente. Precisamos fazer uma pequena curva para a direita entre os nós 3-7. Como resultado, seremos capazes de aumentar a altura da subárvore direita até h + 1: Um
nó verde significa que pode ser preto ou vermelho.
Nota. Se o nó “1” for preto e “c” for vermelho, o problema pode ser reduzido para a variante HH5.
CHK3 - o pai é negro, o filho esquerdo é vermelho, o neto direito tem bisnetos pretos
Ter bisnetos pretos permite repintar o neto de vermelho e enviá-lo para a subárvore direita fazendo uma pequena curva à direita 3-7, e não pergunte por quê, apenas confie e verifique se a altura do preto se estabilizou:
Observe que o nó 5 vermelho não aumenta o preto altura.
CHK4 - o pai é negro, o filho esquerdo é vermelho, o neto direito tem o bisneto esquerdo é vermelho
Mais para dentro da floresta vermelha, há mais lenha preta, e há cada vez menos vermelha, ou seja, recolorindo os nós de vermelho, é possível estabilizar a altura preta.
Nesse caso, você precisa fazer uma grande curva à esquerda, que consiste em duas pequenas curvas 5-3 e 5-7. O nó b mudou sua cor de vermelho para preto e, portanto, aumentou sua altura em 1. Certifique-se de que a altura do preto estabilizou.
HCH5 - o pai é preto, o filho esquerdo é preto com o neto vermelho direito.
Cada vez menos elementos vermelhos em nossa subárvore, pinte de preto o último neto vermelho e faça uma grande curva à esquerda, como no caso anterior.
Verifique se a altura preta da subárvore se estabilizou.
HCH6 - o pai é negro, o filho esquerdo é negro, os netos também são negros
E então chegou o momento em que a madeira vermelha acabou. Não há nada a fazer, você deve pintar o nó preto de vermelho e, assim, equalizar a altura preta do nó 7, mas não aumentando a altura preta da subárvore direita, mas diminuindo a altura preta da subárvore esquerda. Como resultado, a altura preta de toda a nossa estrutura diminuirá em 1 e devemos chamar recursivamente o equilíbrio aos antepassados.
Exemplo de exclusão com balanceamento e recursão
Vimos todos os 6 casos de equilíbrio de altura preto após remover um elemento de uma árvore vermelho-preto. Para ter uma ideia melhor de como tudo isso funciona, vamos continuar removendo o nó 30 da árvore original.
A primeira etapa é simplesmente excluir o nó 30. A
segunda etapa é iniciar o balanceamento em seu pai - nó 25.
Há um caso de HH6:
A altura do nó 25 foi estabilizada com dor pela metade.
A terceira etapa é o equilíbrio no nível do avô - para o nó 20.
Para torná-lo mais divertido e claro , vamos desenhar a árvore inteira antes e depois do balanceamento. Este é o caso do HK4:
Observe como a árvore vermelho-preta mudou após o equilíbrio, alguns dos elementos da subárvore esquerda foram movidos para a direita, a altura estabilizou, o elemento foi removido, todos estão felizes!
Remover itens de uma árvore vermelho e preto é uma das operações mais difíceis ao trabalhar com árvores binárias de pesquisa. No curso " Algoritmos e Estruturas de Dados " consideramos não apenas as árvores binárias de busca, mas também muitos outros algoritmos interessantes, para mais detalhes consulte o programa do curso.
