Podręcznik

Operacje wstawiania oraz usuwania węzłów w drzewach czerwono-czarnych mają na celu nie tylko utrzymanie poprawnej struktury binarnego drzewa wyszukiwania, ale również zachowanie jego zrównoważenia zgodnie z regułami kolorowania. W klasycznych typach drzew czerwono-czarnych procedury te bywają dość złożone. Wymagają uwzględnienia wielu przypadków oraz wariantów rotacji oraz kolorowania. Modyfikacja w postaci drzew LLRBT upraszczają ten proces, ponieważ narzucają dodatkowe ograniczenie tzn. wszystkie czerwone krawędzie muszą być „pochylone w lewo”, czyli czerwony węzeł nie może być prawym dzieckiem. Dzięki temu algorytm wstawiania w LLRBT można podzielić na jasne, powtarzalne etapy i obsługiwać go za pomocą prostego, rekurencyjnego podejścia. 

Możemy wyróżnić następujące etapy wstawienia do drzewa LLRBT:

• Dodanie nowego węzła jako czerwonego liścia - nowy węzeł zawsze wstawiany jest jako czerwony oraz dzięki temu nie narusza to czarnej głębokości ścieżek. Jego kolor może zostać łatwo dostosowany w trakcie przywracania struktury.
• Zamiana kolorów tzw. rozdzielenie 4 węzła - jeśli nowy węzeł został dodany jako dziecko węzła, który ma już dwóch czerwonych synów, to znaczy, że lokalnie utworzył się węzeł 4-elementowy (według analogii z drzewami 2-3-4). Aby przywrócić strukturę drzewa 2-3, następuje zamiana kolorów: ojciec staje się czerwony, a obaj jego synowie – czarni.
• Lewa rotacja tzn. eliminacja czerwonego prawego syna - jeśli po dodaniu nowego węzła powstała sytuacja, w której węzeł ma czerwonego prawego syna, należy wykonać rotację w lewo, by zachować zasadę „pochylania w lewo”.
• Prawa rotacja tzn. eliminacja dwóch czerwonych pod rząd - jeśli po lewej stronie występują dwa czerwone węzły z rzędu (ojciec i lewy syn), wykonuje się rotację w prawo. Dzięki temu eliminujemy sytuację, w której czerwony węzeł ma czerwonego lewego potomka, co narusza zasady LLRBT.

Działanie algorytmu możemy opisać w następujący sposób: podczas wstawiania algorytm schodzi w dół drzewa w taki sam sposób jak zwykłe BST. Gdy znajdzie właściwe miejsce, tworzy czerwony liść. W trakcie wędrówki w górę drzewa (w powrotnej fazie rekurencji) dokonuje ewentualnych korekt:

• jeśli obaj synowie są czerwoni – zmienia kolory. 
•  jeśli prawy syn jest czerwony, a lewy nie – rotuje w lewo. 
•  jeśli lewy syn i jego lewy syn są czerwoni – rotuje w prawo.