Podstawowymi operacjami służącymi do reorganizacji drzewa są operacje rotacji w lewo oraz rotacji w prawo przedstawione na rysunku obok. Rotacja w lewo powoduje spłynięcie danego węzła na lewo w dół i wysunięcie do góry jego prawego syna. Rotacja w prawo zachodzi w drugą stronę - węzeł spływa w prawo, zaś w górę wyciągany jest jego lewy syn. Ze schematu widać, że podczas rotacji nie trzeba przepinać poddrzew oraz , natomiast poddrzewo przenoszone jest między węzłami, zależnie od kierunku rotacji. Można przyjąć, że każda rotacja wykonuje się w czasie O(1).
Rotacja w prawo węzła jest wykonalna, jeżeli jego lewy syn istnieje. Odpowiednio, możemy wykonać rotację w lewo, jeżeli posiada prawego syna. Obie rotacje są operacjami odwracalnymi. Na poziomie rotacji nie uwzględniamy kolorowania węzłów, jest ono poprawiane później niezależnie.
Wstawianie Wstawianie elementu do drzewa składa się z trzech kroków: Umieszczenie elementu za pomocą standardowego algorytmu dla drzew poszukiwań binarnych. Pokolorowanie nowego węzła na czerwono. Przywrócenie własności czerwono-czarnych.