Przywracanie własności rozpoczynamy ze wskaźnikiem , który początkowo wskazuje na czerwony węzeł, który właśnie dodaliśmy. Kończymy je, gdy rodzic węzła będzie czarny, zatem podczas każdej iteracji wiemy także, że rodzic jest czerwony. W algorytmie musimy rozważyć sześć przypadków, przy czym wystarczy rozpatrywać tylko trzy. Druga trójka jest ich symetrycznym odbiciem, a my wybieramy odpowiedni przypadek zależnie od tego, czy jest lewym, czy prawym synem swojego rodzica. Poniżej rozpatrzymy jedynie przypadki, gdy ojciec jest lewym synem swojego ojca. Możliwe są wtedy następujące sytuacje:
Brat ojca (stryj) węzła jest czerwony. Stryj węzła jest czarny i jest prawym synem. Stryj węzła jest czarny i jest lewym synem.
Aby rozwiązać pierwszy przypadek, kolorujemy zarówno ojca, jak i jego brata na czarno, a następnie przesuwamy na ich ojca, którego kolorujemy na czerwono:
z.parent.color = black; // kolorujemy ojca na czarno z.parent.parent.right.color = black; // kolorujemy prawego brata ojca na czarno z = z.parent.parent; // przenosimy się dwa poziomy do góry do ojca ojca. z.color = red;