W poprzednim poście, omówiliśmy wprowadzenie do Drzew Czerwono-Czarnych. W tym poście omówione zostanie wstawianie. W AVL wstawianie drzew, użyliśmy rotacji jako narzędzia do zrobienia równoważenia po wstawieniu. W drzewie Red-Black, używamy dwóch narzędzi do wykonania równoważenia.
- Recoloring
- Rotacja
Recoloring jest zmianą koloru węzła tzn. jeśli jest on czerwony to zmień go na czarny i odwrotnie. Należy zwrócić uwagę, że kolor węzła NULL jest zawsze czarny. Ponadto, zawsze najpierw próbujemy zmienić kolor węzła, a jeśli to nie zadziała, to przechodzimy do rotacji. Poniżej znajduje się szczegółowy algorytm. Algorytmy te mają głównie dwa przypadki w zależności od koloru wujka. Jeśli wujek jest czerwony, to wykonujemy przekolorowanie. Jeśli wujek jest czarny, wykonujemy rotacje i/lub recolouring.
Reprezentacja, z którą będziemy pracować to:
Oparciem tej reprezentacji jest X
Logika:
Najpierw trzeba wstawić węzeł podobnie jak w drzewie binarnym i przypisać mu czerwony kolor. Teraz, jeśli węzeł jest węzłem głównym, to zmień jego kolor na czarny, ale jeśli nie jest, to sprawdź kolor węzła nadrzędnego. Jeśli jego kolor jest czarny, to nie zmieniaj koloru, ale jeśli nie jest, tzn. jest czerwony, to sprawdź kolor wujka węzła. Jeśli wujek węzła ma kolor czerwony to zmień kolor rodzica i wujka węzła na czarny, a dziadka na czerwony i powtórz ten sam proces dla niego (tj. dziadka).
Ale jeśli wujek węzła ma czarny kolor to są 4 możliwe przypadki:
- Lewy lewy przypadek (obrót LL):
- Lewy prawy przypadek (obrót LR):
- Right Right Case (obrót RR):
- Right Left Case (obrót RL):
Teraz, po tych obrotach, jeśli kolory węzłów nie są dopasowane, pokoloruj je ponownie.
Algorytm:
Pozwól x być nowo wstawionym węzłem.
- Wykonaj standardowe wstawianie BST i zmień kolor nowo wstawionych węzłów na CZERWONY.
- Jeśli x jest korzeniem, zmień kolor x na CZARNY (wysokość kompletnego drzewa wzrasta o 1).
- Wykonaj następujące czynności, jeśli kolor rodzica x nie jest CZARNY i x nie jest korzeniem.
a) Jeśli wujek x jest CZERWONY (dziadek musiał być czarny z właściwości 4)
(i) Zmień kolor rodzica i wujka na CZARNY.
(ii) Zmień kolor dziadka na CZERWONY.
(iii) Zmień x = dziadek x, powtórz kroki 2 i 3 dla nowego x.b) Jeśli wujek x jest CZARNY, to mogą istnieć cztery konfiguracje dla x, rodzica x (p) i dziadka x (g) (jest to podobne do drzewa AVL)
(i) Left Left Case (p jest lewym dzieckiem g i x jest lewym dzieckiem p)
(ii) Left Right Case (p jest lewym dzieckiem g i x jest prawym dzieckiem p)
(iii) Right Right Case (lustrzane odbicie przypadku i)
(iv) Right Left Case (lustrzane odbicie przypadku ii)
Przykład: Tworzenie czerwono-czarnego drzewa z elementami 3, 21, 32 i 17 w pustym drzewie.
Rozwiązanie:
Przy wstawianiu pierwszego elementu jest on wstawiany jako węzeł korzeniowy i jako węzeł korzeniowy ma kolor czarny więc nabywa kolor czarny.
Nowy element jest wstawiany zawsze z kolorem czerwonym i jako 21 > 3 więc staje się częścią prawego poddrzewa węzła korzeniowego.
Teraz, gdy wstawiamy 32 widzimy, że jest tam czerwona para ojciec-dziecko, która narusza regułę czerwono-czarnego drzewa, więc musimy ją obrócić. Ponadto widzimy warunki rotacji RR (uznanie węzła zerowego węzła głównego jako czarnego) więc po rotacji jako węzeł główny nie może być Czerwony więc musimy wykonać recolouring w drzewie dając w efekcie drzewo pokazane powyżej.
Teraz, gdy wstawimy nowy element węzeł rodzica i węzeł dziecka z czerwonym kolorem pojawiają się ponownie i tutaj musimy je przekolorować. Widzimy, że zarówno węzeł rodzica jak i węzeł wujka mają czerwony kolor, więc po prostu zmieniamy ich kolor na czarny i zmieniamy kolor dziadka na czerwony. Teraz, ponieważ dziadek jest węzłem głównym, więc ponownie zmieniamy jego kolor na czarny, w wyniku czego otrzymujemy drzewo pokazane powyżej.
Finalna struktura drzewa:
Końcowe drzewo będzie wyglądać tak
Proszę odnieść się do C Program for Red Black Tree Insertion dla kompletnej implementacji powyższego algorytmu.
Red-Black Tree | Set 3 (Delete)