// i kolorujemy go na czerwono
Przypadki 2 i 3 nie wykluczają się wzajemnie, a wręcz przeciwnie. Przypadek 2 możemy bowiem rozwiązać, sprowadzając go do przypadku 3: ustawiamy na ojca dotychczasowego i wykonujemy jego rotację w lewo:
z = z.parent; // przesuwamy się na ojca left-rotate(z); // wykonujemy rotacje w lewo
Rozwiązanie przypadku 3 polega na przekolorowaniu ojca na czarno, jego ojca na czerwono i wykonaniu na tymże ojcu ojca rotacji w prawo:
z.parent.color = black; // ojciec na czarno z.parent.parent.color = red; // jego ojciec na czerwono right-rotate(z.parent.parent); // rotacja w prawo ojca ojca.
Wskaźnika już nie przesuwamy. Zauważmy, że po rozwiązaniu przypadku 3 element jest czerwony, zaś jego ojciec czarny, co oznacza jednocześnie zakończenie przywracania własności czerwono-czarnych.
Przypadki dla sytuacji, gdy ojciec jest prawym synem swego ojca wyglądają analogicznie. Należy jedynie odwrócić kolejność wszystkich operacji (lewo → prawo, prawo → lewo).
Usuwanie
Do usuwania węzła wykorzystujemy standardowy algorytm usuwania elementu z drzewa poszukiwań binarnych z wprowadzoną jedną modyfikacją.