Drzewa Czerwono-Czarne


Tematy pokrewne   Podrozdziały
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew

Zbiory w drzewach binarnych

  Wiadomości podstawowe
Wstawianie węzła
Usuwanie węzła

Wiadomości podstawowe

Drzewa czerwono-czarne (ang. red-black trees) są odmianą samoorganizujących się binarnych drzew poszukiwań, którą wynalazł niemiecki informatyk Rudolf Bayer w roku 1972 i którą następnie opisali w 1978 Leonidas J. Guibas i Robert Sedgewick. W liściach drzew czerwono-czarnych nie przechowuje się danych. Liście te nawet nie muszą znajdować się bezpośrednio w pamięci komputera. Puste wskazanie w polu syna węzła może być interpretowane jako liść. Jednakże używanie rzeczywistych liści upraszcza niektóre algorytmy na drzewach czerwono-czarnych. W celu zaoszczędzenia pamięci często wybiera się pojedynczy węzeł-strażnika (ang. sentinel node), który pełni rolę wszystkich liści w drzewie. W takim przypadku węzły wewnętrzne w drzewie czerwono-czarnym w polach synów-liści przechowują wskazania do tego węzła strażnika. Puste drzewo zawiera jedynie węzeł strażnika.

Drzewa czerwono-czarne gwarantują, iż ich wysokość nie przekroczy dwukrotnej wartości wysokości minimalnej. Dokonywane jest to przez kolorowanie węzłów na czerwono lub czarno i stosowanie po każdej operacji wstawiania lub usuwania odpowiedniej procedury równoważącej drzewo tak, aby były spełnione następujące warunki:

  1. Każdy węzeł drzewa jest albo czerwony, albo czarny.
  2. Każdy liść drzewa (węzeł pusty nil) jest zawsze czarny.
  3. Korzeń drzewa jest zawsze czarny.
  4. Jeśli węzeł jest czerwony, to obaj jego synowie są czarni – innymi słowy, w drzewie nie mogą występować dwa kolejne czerwone węzły, ojciec i syn.
  5. Każda prosta ścieżka od danego węzła do dowolnego z jego liści potomnych zawiera tę samą liczbę węzłów czarnych.

obrazek

Drzewo czerwono-czarne
Węzeł strażnik jest oznaczony jako czarne koło

 

Węzły drzew czerwono-czarnych będziemy reprezentować następującą strukturą danych:

 

Lazarus Code::Blocks Free Basic
type
  PRBTNode = ^RBTNode;
  RBTNode  = record
    up    : PBSTNode;
    left  : PBSTNode;
    right : PBSTNode;
    key   : integer;
    color : char;
    data  : typ_danych;
  end;
struct RBTNode
{
  RBTNode * up;
  RBTNode * left;
  RBTNode * right;
  int key;
  char color;
  typ_danych data;
};
Type RBTNode
  up    As RBTNode Ptr
  left  As RBTNode Ptr
  right As RBTNode Ptr
  key   As Integer
  color As String * 1
  data  As typ_danych
End Type

 

Pole color zawiera informację o kolorze węzła:

 

color = "B"  węzeł czarny, BLACK
color = "R"  węzeł czerwony, RED

Liście będą reprezentowane przez węzeł strażnika o kolorze czarnym. Węzeł strażnika będzie posiadał wszystkie pola wyzerowane.

 

Wstawianie węzła do drzewa czerwono-czarnego

Operacja wstawiania węzła do drzewa czerwono-czarnego składa się z następujących etapów:
 

Tworzymy nowy węzeł, inicjujemy go danymi, po czym wstawiamy do drzewa czerwono-czarnego za pomocą zwykłej procedury wstawiania węzła do drzewa binarnego (ponieważ drzewo czerwono-czarne wciąż jest drzewem binarnym). Gdy węzeł znajdzie się w drzewie, kolorujemy go na czerwono i sprawdzamy czy nie zostały zaburzone warunki drzewa czerwono-czarnego.

 

obrazek

 

Jeśli nowy węzeł jest korzeniem, to zmieniamy jego kolor na czarny (ponieważ korzeń drzewa musi być czarny). Wstawianie jest zakończone.

Jeśli ojciec nowego węzła jest czarny, to również kończymy, ponieważ warunki drzewa czerwono-czarnego w takim przypadku nie zostały zaburzone:

 

obrazek

 

W przeciwnym razie mamy dwa kolejne węzły czerwone i musimy przywrócić warunki drzewa czerwono-czarnego (zauważ, że czerwony ojciec nowego węzła nie może być korzeniem z uwagi na warunek nr 3: korzeń drzewa musi być czarny). W tym celu rozważamy 3 przypadki, które występują w dwóch lustrzanych postaciach (z zamienionymi stronami: lewa z prawą):

 

Przypadek 1:

Wujek C (brat ojca B, czyli drugi syn węzła A) wstawionego węzła X jest czerwony.

 

obrazek

 

Ojca B i wujka C kolorujemy na czarno. Dziadka A kolorujemy na czerwono.

 

obrazek

 

Jeśli węzeł A jest korzeniem drzewa, to zmieniamy jego kolor na czarny (ponieważ korzeń drzewa musi być czarny) i kończymy. W przeciwnym razie za nowe X przyjmujemy A i sprawdzamy od początku kolejne przypadki na wyższym poziomie drzewa.

 

Przypadek 2:

Wujek C jest czarny, a węzeł X jest prawym dzieckiem węzła B (przypadek lustrzany: wujek B jest czarny, a X jest lewym dzieckiem węzła C).

 

obrazek

 

Wykonujemy rotację w lewo względem węzła B (w przypadku lustrzanym wykonujemy rotację w prawo względem C).

 

obrazek

 

Za X przyjmujemy węzeł B i przechodzimy do przypadku 3.

 

Przypadek 3:

Wujek C jest czarny, a węzeł X jest lewym dzieckiem węzła B (przypadek lustrzany: wujek B jest czarny, a X jest prawym dzieckiem węzła C):

 

obrazek

 

Wykonujemy rotację w prawo względem węzła A (w przypadku lustrzanym wykonujemy rotację w lewo względem A):

 

obrazek

 

Zmieniamy kolory węzłów A i B na przeciwne:

 

obrazek

 

Operacja wstawiania zostaje zakończona, ponieważ węzeł B ma taki sam kolor jak poprzednio węzeł A. Zatem operacja rotacji przywróciła strukturę drzewa czerwono-czarnego.

 

Algorytm wstawiania węzła do drzewa czerwono-czarnego

Wejście
root  –  referencja do zmiennej, która przechowuje wskazanie korzenia drzewa czerwono-czarnego
k  –  klucz nowego węzła (mogą również występować dodatkowe dane, które chcemy przechowywać w węźle)
S  –  wskazanie węzła strażnika
Wyjście:
Drzewo czerwono-czarne z wstawionym nowym węzłem.
Elementy pomocnicze:
X  –  wskazanie nowego węzła
Y  –  wskazanie węzła
rot_L(root,x)  –  rotacja w lewo względem x
rot_R(root,x)  –  rotacja w prawo względem x
Lista kroków:
K01: Utwórz nowy węzeł ; tworzymy nowy węzeł
K02: X ← adres nowego węzła  
K03: (Xleft) ← S ; liśćmi staje się węzeł strażnik
K04: (Xright) ← S  
K05: (Xup) ← root  
K06: (Xkey) ← k  
K07: Jeśli (Xup) ≠ S, to idź do K10 ; sprawdzamy, czy drzewo jest puste
K08: rootX ; jeśli tak, to nowy węzeł staje się jego korzeniem
K09: Idź do K17 ; przechodzimy do sprawdzania warunków drzewa czerwono-czarnego
K10: Jeśli k < (Xupkey), to idź do K14 ; porównujemy klucze
K11: Jeśli (Xupright) = S, to:
    (Xupright) ← X
    Idź do K17
; jeśli prawy syn nie istnieje (jest nim strażnik), to
; nowy węzeł staje się prawym synem
; i przechodzimy do sprawdzania warunków drzewa czerwono-czarnego
K12: (Xup) ← (Xupright) ; inaczej przechodzimy do prawego syna
K13: Idź do K10 ; i kontynuujemy pętlę
K14 Jeśli (Xupleft) = S, to:
    (Xupleft) ← X
    Idź do K17
; to samo dla lewego syna
K15: (Xup) ← (Xupleft)  
K16: Idź do K10  
K17: (Xcolor) ← RED ; węzeł kolorujemy na czerwono
K18: Dopóki (Xroot) obrazek (Xupcolor) = RED) wykonuj  K19..K47. ; w pętli sprawdzamy kolejne przypadki
K19:     Jeśli (Xup) ≠ (Xupup→left), to idź do K34 ; skok do przypadków lustrzanych
K20:     Y ← (Xupupright) ; Y wskazuje wujka węzła X
K21:     Jeśli (Ycolor) = BLACK, to idź do K27 ; sprawdzamy przypadek nr 1 -> wujek jest czerwony
K22:     (Xupcolor) ← BLACK ; ojca kolorujemy na czarno
K23:     (Ycolor) ← BLACK ; wujka kolorujemy na czarno
K24:     (Xupupcolor) ← RED ; dziadka kolorujemy na czerwono
K25:     X ← (Xupup) ; za nowe X przyjmujemy dziadka
K26:     Następny obieg pętli K18 ; i kontynuujemy pętlę
K27:     Jeśli X ≠ (Xup→right), to idź do K30 ; sprawdzamy przypadek 2 -> wujek czarny, X prawy syn
K28:     X ← (Xup) ; X staje się swoim ojcem
K29:     rot_L(root,X) ; wykonujemy rotację w lewo, X przechodzi do lewego syna
K30:     (Xupcolor) ← BLACK ; przypadek 3 -> wujek czarny, X lewy syn
K31:     (Xupupcolor) ← RED ; zmieniamy kolory ojca i dziadka
K32     rot_R(root,(Xupup)) ; wykonujemy rotację w prawo względem dziadka
K33:     Idź do K48 ; i wychodzimy z pętli
K34:     Y ← (Xupupleft) ; przypadki lustrzane
K35:     Jeśli (Ycolor) = BLACK, to idź do K41  
K36:     (Xupcolor) ← BLACK  
K37:     (Ycolor) ← BLACK  
K38:     (Xupupcolor) ← RED  
K39:     X ← (Xupup)  
K40:     Następny obieg pętli K18  
K41:     Jeśli X ≠ (Xup→left), to idź do K44  
K42:     X ← (Xup)  
K43:     rot_R(root,X)  
K44:     (Xupcolor) ← BLACK  
K45:     (Xupupcolor) ← RED  
K46     rot_L(root,(Xupup))  
K47:     Idź do K48 ; wychodzimy z pętli
K48  (rootcolor) ← BLACK ; kolorujemy korzeń na czarno
K49: Zakończ  

 

Usuwanie węzła

Usuwanie węzła z drzewa czerwono-czarnego jest nieco trudniejsze od wstawiania, ponieważ należy rozpatrzyć więcej różnych przypadków. Operację wykonujemy dwuetapowo. Najpierw usuwamy z drzewa wybrany węzeł tak, jak dla drzew BST. Mamy tutaj cztery możliwe przypadki:

 
Przypadek 1. Usuwany węzeł X nie posiada lewego syna (jest nim węzeł strażnik)

Usuwamy z drzewa węzeł X, a na jego miejsce wstawiamy prawego syna Y. Jeśli usunięty węzeł był czarny, to operacja ta może naruszać warunek 4, jeśli Y oraz jego nowy ojciec są węzłami czerwonymi. W takim przypadku przywracamy warunek zmieniając kolor węzła Y na czarny.

obrazek
Przypadek 2. Usuwany węzeł X nie posiada prawego syna.

Jest to przypadek symetryczny do przypadku 1. Usuwamy węzeł X, zastępując go lewym synem. Jeśli X był czarny, kolorujemy Y na czarno.

Zwróć uwagę, że przypadki 1 i 2 również obejmują brak synów w węźle X. W takim przypadku X zostaje zastąpiony przez węzeł strażnika, który jest czarny.

 

obrazek
Przypadek 3. Węzeł X posiada dwóch synów, z których prawy Z jest następnikiem.

Węzeł X zastępujemy następnikiem Z. Lewym synem Z staje się węzeł Y. Następnik zawsze ma lewego syna pustego (w przeciwnym razie nie byłby najmniejszym elementem w prawej gałęzi drzewa). Następnik otrzymuje kolor węzła X. Jeśli następnik był czarny, to jego prawy syn ZR otrzymuje umownie dodatkowy kolor czarny – jeśli ZR był czarny, to jest teraz podwójnie czarny, a jeśli był czerwony, to jest czerwono-czarny. Zostanie to rozwiązane w dalszej części algorytmu.

obrazek
Przypadek 4. Węzeł X posiada dwóch synów, jednak następnik nie jest jego prawym synem.

Następnik A zostaje zastąpiony w drzewie swoim prawym synem B (kolor A zachowujemy dla B). Do węzła X kopiujemy zawartość następnika A bez pola koloru (kolor X zostaje zachowany dla A). Jeśli następnik A był czarny, to jego prawy syn B otrzymuje umownie dodatkowy kolor czarny – jeśli B był czarny, to jest teraz podwójnie czarny, a jeśli był czerwony, to jest czerwono-czarny. Zostanie to rozwiązane w dalszej części algorytmu.

 

obrazek

 

Przypadki 3 i 4 wymagają korekty drzewa, jeśli następnik był czarny (w przeciwnym razie drzewo wciąż jest drzewem czerwono-czarnym i operację usuwania węzła możemy zakończyć). W takim przypadku prawy syn następnika posiada dodatkowy kolor czarny. Kolor ten dodajemy umownie po to, aby był wciąż spełniony warunek nr 5. Ponieważ ze ścieżek, które wcześniej zawierały usunięty węzeł, zniknął jeden węzeł czarny, to musimy ten kolor dodać do węzła znajdującego się na tych ścieżkach, czyli do prawego syna następnika. Powstaje ciąg czterech symetrycznych przypadków, które są lustrzanymi odbiciami. Umówmy się, że węzeł posiadający dodatkowy kolor czarny będziemy oznaczali gwiazdką. Kolor szary oznacza, że węzeł może być czerwony lub czarny.

 

Przypadek 1. Brat węzła A* (węzeł C) jest czerwony.

Wykonujemy rotację w lewo względem B (ojciec węzła A*). Zamieniamy kolory ojca (węzeł B) i dziadka (węzeł C). W ten sposób brat A* (teraz węzeł D) staje się węzłem czarnym. Otrzymujemy jeden z przypadków 2, 3 lub 4, które rozróżniamy po kolorach synów brata A*.

obrazek
Przypadek 2. Brat węzła A* (węzeł C) jest czarny i posiada czarnych synów (węzły D i E).

Zabieramy jeden kolor czarny z węzłów A i C, przenosząc go w górę do węzła B. W efekcie węzeł A nie ma już nadmiarowego koloru czarnego, staje się normalnym węzłem czerwonym lub czarnym. Z kolei zabranie koloru czarnego z węzła C skutkuje zmianą koloru na czerwony. Ponieważ obaj synowie D i E są czarni, zmiana ta nie powoduje naruszenia warunku drzewa czerwono-czarnego.

Ponieważ problem dodatkowego koloru czarnego przeniósł się w górę drzewa do węzła B (ojca A), to wracamy do rozpatrywania przypadków z nowym węzłem A*, który teraz jest ojcem poprzedniego węzła A, czyli węzłem B*.

obrazek
Przypadek 3. Brat węzła A* (węzeł C) jest czarny, lewy syn węzła C jest czerwony, prawy syn węzła C jest czarny.

Wykonujemy rotację w prawo względem węzła C, po czym zamieniamy kolory pomiędzy węzłami C i D. Otrzymujemy w ten sposób przypadek 4.

obrazek
Przypadek 4. Brat węzła A* (węzeł C) jest czarny, a jego prawy syn jest czerwony.

Wykonujemy rotację względem węzła B (ojciec A*). Przenosimy kolor z węzła B do C. W takim przypadku B traci kolor i możemy w tym węźle umieścić dodatkowy kolor czarny z węzła A. Dzięki temu pozbywamy się dodatkowej czerni. Na koniec węzeł E kolorujemy na czarno.

Ta transformacja przywraca strukturę drzewa czerwono-czarnego, zatem kończy operację usuwania węzła.

 

obrazek

 

Algorytm usuwania węzła z drzewa czerwono-czarnego

Wejście
root  –  referencja do zmiennej przechowującej adres korzenia
X  –  wskazanie usuwanego węzła
S  –  wskazanie węzła strażnika
Wyjście:
Drzewo czerwono-czarne z usuniętym węzłem X
Elementy pomocnicze:
 
W,Y,Z  –  wskazania węzłów
succRBT(p)  –  zwraca wskazanie następnika p w drzewie czerwono-czarnym
rot_L(root,p)  –  wykonuje rotację w lewo względem węzła p
rot_R(root,p)  –  wykonuje rotację w prawo względem węzła p
Lista kroków:
K01: Jeśli ((Xleft) = S) obrazek ((Xright) = S), to Y X
Inaczej                                                  Y ← succRBT(X)
; Y jest usuwanym węzłem, jest to albo X,
; albo jego następnik
K02: Jeśli (Yleft) ≠ S, to Z ← (Yleft)
Inaczej                     Z ← (Yright)
; Z jest lewym lub prawym synem usuwanego elementu
K03: (Zup) ← (Yup) ; Ojcem Z będzie ojciec Y
K04: Jeśli (Yup) ≠ S, to idź do K07 ; Sprawdzamy, czy usuwany węzeł jest korzeniem
K05: rootZ ; Jeśli tak, to nowym korzeniem będzie jego syn
K06: Idź do K08 ; Przechodzimy do poprawiania struktury drzewa
K07: Jeśli Y = (Yupleft), to (Yupleft) ← Z
Inaczej                            (Yupright) ← Z
; Z zastępuje Y w strukturze drzewa
K08: Jeśli YX, to (Xkey) ← (Ykey) ; Jeśli X nie jest usuwanym węzłem, to przenosimy klucze z Y do X
K09: Jeśli (Ycolor) = RED, to idź do K52 ; Jeśli usuwany węzeł jest czerwony, to kończymy
K10: Dopóki (Zroot) obrazek ((Zcolor) = BLACK), wykonuj kroki K11...K51 ; Dokonujemy poprawy struktury drzewa czerwono-czarnego
K11:     Jeśli Z = (Zupright), to idź do K33 ; Skok do przypadków lustrzanych
K12:     W ← (Zupright) ; W wskazuje brata Z
K13:     Jeśli (Wcolor) = BLACK, to idź do K18  
K14:     (Wcolor) ← BLACK ; Przypadek 1
K15:     (Zupcolor) ← RED  
K16:     rot_L(root,(Zup))  
K17:     W ← (Zupright)  
K18:     Jeśli ((Wleftcolor) = RED) obrazek ((Wrightcolor) = RED), to idź do K22  
K19:     (Wcolor) ← RED ; Przypadek 2
K20:     Z ← (Zup)  
K21:     Następny obieg pętli K10  
K22:     Jeśli (Wrightcolor) = RED, to idź do K27  
K23:     (Wleftcolor) ← BLACK ; Przypadek 3
K24:     (Wcolor) ← RED  
K25:     rot_R(root,W)  
K26:     W ← (Zupright)  
K27:     (Wcolor) ← (Zupcolor) ; Przypadek 4
K28:     (Zupcolor) ← BLACK  
K29:     (Wrightcolor) ← BLACK  
K30:     rot_L(root,(Zup))  
K31     Zroot i następny obieg pętli K10 ; Z = root spowoduje przerwanie pętli
K32:     W ← (Zupleft) ; Przypadki lustrzane
K33:     Jeśli (Wcolor) = BLACK, to idź do K38  
K34:     (Wcolor) ← BLACK ; Przypadek 1
K35:     (Zupcolor) ← RED  
K36:     rot_R(root,(Zup))  
K37:     W ← (Zupleft)  
K38:     Jeśli ((Wleftcolor) = RED) obrazek ((Wrightcolor) = RED), to idź do K42  
K39:     (Wcolor) ← RED ; Przypadek 2
K40:     Z ← (Zup)  
K41:     Następny obieg pętli K10  
K42:     Jeśli (Wleftcolor) = RED, to idź do K47  
K43:     (Wrightcolor) ← BLACK ; Przypadek 3
K44:     (Wcolor) ← RED  
K45:     rot_L(root,W)  
K46:     W ← (Zupleft)  
K47:     (Wcolor) ← (Zupcolor) ; Przypadek 4
K48:     (Zupcolor) ← BLACK  
K49:     (Wleftcolor) ← BLACK  
K50:     rot_R(root,(Zup))  
K51     Z Z root i następny obieg pętli K10 ; Z = root spowoduje przerwanie pętli
K52: (Zcolor) ← BLACK ; węzeł Z kolorujemy na czarno
K53 Usuń Y  
K54: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tworzy drzewo czerwono-czarne z 30 kluczy o wartościach od 1 do 30. Węzły z tymi kluczami będą wstawiane losowo. Po utworzeniu drzewa zostaje ono wyświetlona. Następnie program wylosuje połowę kluczy i usunie węzły z tymi kluczami z drzewa. Drzewo końcowe również zostanie wyświetlone.

 

Lazarus
// Drzewo czerwono-czarne
// Data: 11.06.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program RedBlackTree;

const MAXN = 30;           // Liczba węzłów

// Typ węzłów drzewa RBT

type
  PRBTNode = ^RBTNode;
  RBTNode  = record
    up,left,right : PRBTNode;
    key   : integer;
    color : char;
  end;

// Definicja typu obiektowego TRBTree
TRBTree = object
  private
    S    : RBTNode;        // Węzeł strażnika
    root : PRBTNode;       // Korzeń drzewa czerwono-czarnego
    cr,cl,cp : string;     // Łańcuchy do znaków ramek

    procedure printRBT(sp,sn : string; p : PRBTNode); // Wypisuje drzewo

  public
    constructor init;
    destructor  destroy;
    procedure DFSRelease(p : PRBTNode);          // Usuwa rekurencyjnie drzewo
    procedure print();                           // Wypisuje drzewo
    function  findRBT(k : integer)  : PRBTNode;  // Wyszukuje węzeł o kluczu k
    function  minRBT(p : PRBTNode)  : PRBTNode;  // Wyszukuje najmniejszy węzeł w p
    function  succRBT(p : PRBTNode) : PRBTNode;  // Wyszukuje następnik p
    procedure rot_L(A : PRBTNode);               // Rotacja w lewo względem A
    procedure rot_R(A : PRBTNode);               // Rotacja w prawo względem A
    procedure insertRBT(k : integer);            // Wstawia węzeł o kluczu k
    procedure removeRBT(X : PRBTNode);           // Usuwa węzeł X
end;

// Konstruktor drzewa
//-------------------
constructor TRBTree.init;
begin
  cr := #218#196;          // Inicjujemy łańcuchy do ramek
  cl := #192#196;
  cp := #179#32;
  S.color := 'B';          // Inicjujemy strażnika
  S.up    := @S;
  S.left  := @S;
  S.right := @S;
  root    := @S;           // Korzeń wskazuje strażnika
end;

// Destruktor drzewa
//------------------
destructor TRBTree.destroy;
begin
  DFSRelease(root);        // Rekurencyjnie usuwamy węzły
end;

// Usuwa rekurencyjnie drzewo czerwono-czarne
//-------------------------------------------
procedure TRBTree.DFSRelease(p : PRBTNode);
begin
  if p <> @S then
  begin
    DFSRelease(p^.left);   // usuwamy lewe poddrzewo
    DFSRelease(p^.right);  // usuwamy prawe poddrzewo
    dispose(p);            // usuwamy sam węzeł
  end;
end;

// Wypisuje zawartość drzewa
//--------------------------
procedure TRBTree.printRBT(sp,sn : string; p : PRBTNode);
var
  t : string;
begin
  if p <> @S then
  begin
    t := sp;
    if sn = cr then t[length(t) - 1] := ' ';
    printRBT(t+cp,cr,p^.right);

    t := Copy(sp,1,length(sp)-2);
    writeln(t,sn,p^.color,':',p^.key);

    t := sp;
    if sn = cl then t[length(t) - 1] := ' ';
    printRBT(t+cp,cl,p^.left);
  end;
end;

// Wypisuje zawartość drzewa
//--------------------------
procedure TRBTree.print();
begin
  printRBT('','',root);
end;

// Wyszukuje węzeł o kluczu k
// Jeśli węzeł nie zostanie znaleziony, to zwraca
// wskazanie puste nil
//-----------------------------------------------
function TRBTree.findRBT(k : integer)  : PRBTNode;
var
  p : PRBTNode;
begin
  p := root;
  while (p <> @S) and (p^.key <> k) do
      if k < p^.key then p := p^.left
      else               p := p^.right;
  if p = @S then findRBT := nil
  else           findRBT := p;
end;

// Wyszukuje najmniejszy węzeł w poddrzewie
// o korzeniu p
//-----------------------------------------
function  TRBTree.minRBT(p : PRBTNode)  : PRBTNode;
begin
  if p <> @S then
    while p^.left <> @S do
      p := p^.left;
  minRBT := p;
end;

// Zwraca następnik p
//-------------------
function TRBTree.succRBT(p : PRBTNode) : PRBTNode;
var
  r : PRBTNode;
begin
  succRBT := @S;
  if p <> @S then
  begin
    if p^.right <> @S then succRBT := minRBT(p^.right)
    else
    begin
      r := p^.up;
      while (r <> @S) and (p = r^.right) do
      begin
        p := r;
        r := r^.up;
      end;
      succRBT := r;
    end;
  end;
end;

// Wykonuje rotację w lewo względem A
//-----------------------------------
procedure TRBTree.rot_L(A : PRBTNode);
var
  B,p : PRBTNode;
begin
  B := A^.right;
  if B <> @S then
  begin
    p := A^.up;
    A^.right := B^.left;
    if A^.right <> @S then A^.right^.up := A;

    B^.left := A;
    B^.up := p;
    A^.up := B;

    if p <> @S then
    begin
      if p^.left = A then p^.left := B else p^.right := B;
    end
    else root := B;
  end;
end;

// Wykonuje rotację w prawo względem A
//------------------------------------
procedure TRBTree.rot_R(A : PRBTNode);
var
  B,p : PRBTNode;
begin
  B := A^.left;
  if B <> @S then
  begin
    p := A^.up;
    A^.left := B^.right;
    if A^.left <> @S then A^.left^.up := A;

    B^.right := A;
    B^.up := p;
    A^.up := B;

    if p <> @S then
    begin
      if p^.left = A then p^.left := B else p^.right := B;
    end
    else root := B;
  end;
end;

// Wstawia do drzewa węzeł o kluczu k
//-----------------------------------
procedure TRBTree.insertRBT(k : integer);
var
  X,Y : PRBTNode;
begin
  new(X);                  // Tworzymy nowy węzeł
  X^.left  := @S;          // Inicjujemy pola
  X^.right := @S;
  X^.up    := root;
  X^.key   := k;
  if X^.up = @S then root := X // X staje się korzeniem
  else
  while true do            // Szukamy liścia do zastąpienia przez X
  begin
    if k < X^.up^.key then
    begin
      if X^.up^.left = @S then
      begin
        X^.up^.left := X;  // X zastępuje lewy liść
        break;
      end;
      X^.up := X^.up^.left;
    end
    else
    begin
      if X^.up^.right = @S then
      begin
        X^.up^.right := X; // X zastępuje prawy liść
        break;
      end;
      X^.up := X^.up^.right;
    end;
  end;
  X^.color := 'R';         // Węzeł kolorujemy na czerwono
  while (X <> root) and (X^.up^.color = 'R') do
  begin
    if X^.up = X^.up^.up^.left then
    begin
      Y := X^.up^.up^.right; // Y -> wujek X

      if Y^.color = 'R' then // Przypadek 1
      begin
        X^.up^.color := 'B';
        Y^.color := 'B';
        X^.up^.up^.color := 'R';
        X := X^.up^.up;
        continue;
      end;

      if X = X^.up^.right then // Przypadek 2
      begin
        X := X^.up;
        rot_L(X);
      end;

      X^.up^.color := 'B'; // Przypadek 3
      X^.up^.up^.color := 'R';
      rot_R(X^.up^.up);
      break;
    end
    else
    begin                  // Przypadki lustrzane
      Y := X^.up^.up^.left;

      if Y^.color = 'R' then // Przypadek 1
      begin
        X^.up^.color := 'B';
        Y^.color := 'B';
        X^.up^.up^.color := 'R';
        X := X^.up^.up;
        continue;
      end;

      if X = X^.up^.left then // Przypadek 2
      begin
        X := X^.up;
        rot_R(X);
      end;

      X^.up^.color := 'B'; // Przypadek 3
      X^.up^.up^.color := 'R';
      rot_L(X^.up^.up);
      break;
    end;
  end;
  root^.color := 'B';
end;

// Usuwa z drzewa węzeł X
//-----------------------
procedure TRBTree.removeRBT(X : PRBTNode);
var
  W,Y,Z : PRBTNode;
begin
  if (X^.left = @S) or (X^.right = @S) then Y := X
  else                                      Y := succRBT(X);

  if Y^.left <> @S then Z := Y^.left
  else                  Z := Y^.right;

  Z^.up := Y^.up;

  if Y^.up = @S then root := Z
  else if Y = Y^.up^.left then Y^.up^.left  := Z
  else                         Y^.up^.right := Z;

  if Y <> X then X^.key := Y^.key;

  if Y^.color = 'B' then   // Naprawa struktury drzewa czerwono-czarnego
    while (Z <> root) and (Z^.color = 'B') do
      if Z = Z^.up^.left then
      begin

        W := Z^.up^.right;

        if W^.color = 'R' then
        begin              // Przypadek 1
          W^.color := 'B';
          Z^.up^.color := 'R';
          rot_L(Z^.up);
          W := Z^.up^.right;
        end;

        if (W^.left^.color = 'B') and (W^.right^.color = 'B') then
        begin              // Przypadek 2
          W^.color := 'R';
          Z := Z^.up;
          continue;
        end;

        if W^.right^.color = 'B' then
        begin              // Przypadek 3
          W^.left^.color := 'B';
          W^.color := 'R';
          rot_R(W);
          W := Z^.up^.right;
        end;

        W^.color := Z^.up^.color; // Przypadek 4
        Z^.up^.color := 'B';
        W^.right^.color := 'B';
        rot_L(Z^.up);
        Z := root;         // To spowoduje zakończenie pętli
      end
      else
      begin                // Przypadki lustrzane
        W := Z^.up^.left;

        if W^.color = 'R' then
        begin              // Przypadek 1
          W^.color := 'B';
          Z^.up^.color := 'R';
          rot_R(Z^.up);
          W := Z^.up^.left;
        end;

        if (W^.left^.color = 'B') and (W^.right^.color = 'B') then
        begin              // Przypadek 2
          W^.color := 'R';
          Z := Z^.up;
          continue;
        end;

        if W^.left^.color = 'B' then
        begin              // Przypadek 3
          W^.right^.color := 'B';
          W^.color := 'R';
          rot_L(W);
          W := Z^.up^.left;
        end;

        W^.color := Z^.up^.color;  // Przypadek 4
        Z^.up^.color := 'B';
        W^.left^.color := 'B';
        rot_R(Z^.up);
        Z := root;         // To spowoduje zakończenie pętli
      end;

  Z^.color := 'B';

  dispose(Y);

end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

var
  Tk   : array[0..MAXN-1] of integer; // Tablica kluczy węzłów
  i,x,i1,i2  : integer;
  RBT : TRBTree;                      // Obiekt drzewa czerwono-czarnego

begin
  randomize;               // Inicjujemy generator pseudolosowy

  RBT.init;                // Tworzymy puste drzewo

  for i := 0 to MAXN-1 do  // Tablicę wypełniamy wartościami kluczy
    Tk[i] := i + 1;

  for i := 1 to 300 do     // Mieszamy tablicę
  begin
    i1 := random(MAXN);    // Losujemy 2 indeksy
    i2 := random(MAXN);

    x := Tk[i1];           // Wymieniamy Tk[i1] <-->. Tk[i2]
    Tk[i1] := Tk[i2];
    Tk[i2] := x;
  end;

  for i := 0 to MAXN-1 do  // Na podstawie tablicy tworzymy drzewo czerwono-czarne
  begin
    write(Tk[i],' ');
    RBT.insertRBT(Tk[i]);
  end;

  writeln; writeln;

  RBT.print();             // Wyświetlamy zawartość drzewa

  writeln; writeln;

  for i := 1 to 300 do     // Ponownie mieszamy tablicę
  begin
    i1 := random(MAXN); i2 := random(MAXN);
    x := Tk[i1]; Tk[i1] := Tk[i2]; Tk[i2] := x;
  end;

  for i := 0 to MAXN div 2 do // Usuwamy połowę węzłów
  begin
    write(Tk[i],' ');
    RBT.removeRBT(RBT.findRBT(Tk[i]));
  end;

  writeln; writeln;

  RBT.print();             // Wyświetlamy zawartość drzewa

  RBT.destroy;             // Usuwamy drzewo z pamięci

end.
Code::Blocks
// Drzewo czerwono-czarne
// Data: 11.06.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXN = 30;           // Liczba węzłów

// Typ węzłów drzewa RBT

struct RBTNode
{
  RBTNode * up;
  RBTNode * left;
  RBTNode * right;
  int key;
  char color;
};

// Definicja typu obiektowego TRBTree
class TRBTree
{
  private:
    RBTNode S;             // Węzeł strażnika
    RBTNode * root;        // Korzeń drzewa czerwono-czarnego
    string cr,cl,cp;       // Łańcuchy do znaków ramek

    void printRBT(string sp, string sn, RBTNode * p); // Wypisuje drzewo

  public:
    TRBTree();             // Konstruktor klasy
    ~TRBTree();            // Destruktor klasy
    void DFSRelease(RBTNode * p); // Usuwa rekurencyjnie drzewo
    void print();          // Wypisuje drzewo
    RBTNode * findRBT(int k); // Wyszukuje węzeł o kluczu k
    RBTNode * minRBT(RBTNode * p); // Wyszukuje najmniejszy węzeł w p
    RBTNode * succRBT(RBTNode * p);// Wyszukuje następnik p
    void rot_L(RBTNode * A); // Rotacja w lewo względem A
    void rot_R(RBTNode * A); // Rotacja w prawo względem A
    void insertRBT(int k);   // Wstawia węzeł o kluczu k
    void removeRBT(RBTNode * X); // Usuwa węzeł X
};

// Konstruktor drzewa
//-------------------
TRBTree::TRBTree()
{
  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;
  S.color = 'B';          // Inicjujemy strażnika
  S.up    = &S;
  S.left  = &S;
  S.right = &S;
  root    = &S;           // Korzeń wskazuje strażnika
}

// Destruktor drzewa
//------------------
TRBTree::~TRBTree()
{
  DFSRelease(root);       // Rekurencyjnie usuwamy węzły
}

// Usuwa rekurencyjnie drzewo czerwono-czarne
//-------------------------------------------
void TRBTree::DFSRelease(RBTNode * p)
{
  if(p != &S)
  {
    DFSRelease(p->left);   // usuwamy lewe poddrzewo
    DFSRelease(p->right);  // usuwamy prawe poddrzewo
    delete p;              // usuwamy sam węzeł
  }
}

// Wypisuje zawartość drzewa
//--------------------------
void TRBTree::printRBT(string sp, string sn, RBTNode * p)
{
  string t;

  if(p != &S)
  {
    t = sp;
    if(sn == cr) t[t.length() - 2] = ' ';
    printRBT(t+cp,cr,p->right);

    t = t.substr(0,sp.length()-2);
    cout << t << sn << p->color << ":" << p->key << endl;

    t = sp;
    if(sn == cl) t[t.length() - 2] = ' ';
    printRBT(t+cp,cl,p->left);
  }
}

// Wypisuje zawartość drzewa
//--------------------------
void TRBTree::print()
{
  printRBT("","",root);
}

// Wyszukuje węzeł o kluczu k
// Jeśli węzeł nie zostanie znaleziony, to zwraca
// wskazanie puste NULL
//-----------------------------------------------
RBTNode * TRBTree::findRBT(int k)
{
  RBTNode * p;

  p = root;
  while((p != &S) && (p->key != k))
    if(k < p->key) p = p->left;
    else           p = p->right;
  if(p == &S) return NULL;
  return p;
}

// Wyszukuje najmniejszy węzeł w poddrzewie
// o korzeniu p
//-----------------------------------------
RBTNode * TRBTree::minRBT(RBTNode * p)
{
  if(p != &S)
    while(p->left != &S) p = p->left;
  return p;
}

// Zwraca następnik p
//-------------------
RBTNode * TRBTree::succRBT(RBTNode * p)
{
  RBTNode * r;

  if(p != &S)
  {
    if(p->right != &S) return minRBT(p->right);
    else
    {
      r = p->up;
      while((r != &S) && (p == r->right))
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return &S;
}

// Wykonuje rotację w lewo względem A
//-----------------------------------
void TRBTree::rot_L(RBTNode * A)
{
  RBTNode * B, * p;

  B = A->right;
  if(B != &S)
  {
    p = A->up;
    A->right = B->left;
    if(A->right != &S) A->right->up = A;

    B->left = A;
    B->up = p;
    A->up = B;

    if(p != &S)
    {
      if(p->left == A) p->left = B; else p->right = B;
    }
    else root = B;
  }
}

// Wykonuje rotację w prawo względem A
//------------------------------------
void TRBTree::rot_R(RBTNode * A)
{
  RBTNode * B, * p;

  B = A->left;
  if(B != &S)
  {
    p = A->up;
    A->left = B->right;
    if(A->left != &S) A->left->up = A;

    B->right = A;
    B->up = p;
    A->up = B;

    if(p != &S)
    {
      if(p->left == A) p->left = B; else p->right = B;
    }
    else root = B;
  }
}

// Wstawia do drzewa węzeł o kluczu k
//-----------------------------------
void TRBTree::insertRBT(int k)
{
  RBTNode * X, * Y;

  X = new RBTNode;        // Tworzymy nowy węzeł
  X->left  = &S;          // Inicjujemy pola
  X->right = &S;
  X->up    = root;
  X->key   = k;
  if(X->up == &S) root = X; // X staje się korzeniem
  else
  while(true)             // Szukamy liścia do zastąpienia przez X
  {
    if(k < X->up->key)
    {
      if(X->up->left == &S)
      {
        X->up->left = X;  // X zastępuje lewy liść
        break;
      }
      X->up = X->up->left;
    }
    else
    {
      if(X->up->right == &S)
      {
        X->up->right = X; // X zastępuje prawy liść
        break;
      }
      X->up = X->up->right;
    }
  }
  X->color = 'R';         // Węzeł kolorujemy na czerwono
  while((X != root) && (X->up->color == 'R'))
  {
    if(X->up == X->up->up->left)
    {
      Y = X->up->up->right; // Y -> wujek X

      if(Y->color == 'R')  // Przypadek 1
      {
        X->up->color = 'B';
        Y->color = 'B';
        X->up->up->color = 'R';
        X = X->up->up;
        continue;
      }

      if(X == X->up->right) // Przypadek 2
      {
        X = X->up;
        rot_L(X);
      }

      X->up->color = 'B'; // Przypadek 3
      X->up->up->color = 'R';
      rot_R(X->up->up);
      break;
    }
    else
    {                  // Przypadki lustrzane
      Y = X->up->up->left;

      if(Y->color == 'R') // Przypadek 1
      {
        X->up->color = 'B';
        Y->color = 'B';
        X->up->up->color = 'R';
        X = X->up->up;
        continue;
      }

      if(X == X->up->left) // Przypadek 2
      {
        X = X->up;
        rot_R(X);
      }

      X->up->color = 'B'; // Przypadek 3
      X->up->up->color = 'R';
      rot_L(X->up->up);
      break;
    }
  }
  root->color = 'B';
}

// Usuwa z drzewa węzeł X
//-----------------------
void TRBTree::removeRBT(RBTNode * X)
{
  RBTNode * W, * Y, * Z;

  if((X->left == &S) || (X->right == &S)) Y = X;
  else                                    Y = succRBT(X);

  if(Y->left != &S) Z = Y->left;
  else              Z = Y->right;

  Z->up = Y->up;

  if(Y->up == &S) root = Z;
  else if(Y == Y->up->left) Y->up->left  = Z;
  else                      Y->up->right = Z;

  if(Y != X) X->key = Y->key;

  if(Y->color == 'B')   // Naprawa struktury drzewa czerwono-czarnego
    while((Z != root) && (Z->color == 'B'))
      if(Z == Z->up->left)
      {
        W = Z->up->right;

        if(W->color == 'R')
        {              // Przypadek 1
          W->color = 'B';
          Z->up->color = 'R';
          rot_L(Z->up);
          W = Z->up->right;
        }

        if((W->left->color == 'B') && (W->right->color == 'B'))
        {              // Przypadek 2
          W->color = 'R';
          Z = Z->up;
          continue;
        }

        if(W->right->color == 'B')
        {              // Przypadek 3
          W->left->color = 'B';
          W->color = 'R';
          rot_R(W);
          W = Z->up->right;
        }

        W->color = Z->up->color; // Przypadek 4
        Z->up->color = 'B';
        W->right->color = 'B';
        rot_L(Z->up);
        Z = root;         // To spowoduje zakończenie pętli
      }
      else
      {                // Przypadki lustrzane
        W = Z->up->left;

        if(W->color == 'R')
        {              // Przypadek 1
          W->color = 'B';
          Z->up->color = 'R';
          rot_R(Z->up);
          W = Z->up->left;
        }

        if((W->left->color == 'B') && (W->right->color == 'B'))
        {              // Przypadek 2
          W->color = 'R';
          Z = Z->up;
          continue;
        }

        if(W->left->color == 'B')
        {              // Przypadek 3
          W->right->color = 'B';
          W->color = 'R';
          rot_L(W);
          W = Z->up->left;
        }

        W->color = Z->up->color;  // Przypadek 4
        Z->up->color = 'B';
        W->left->color = 'B';
        rot_R(Z->up);
        Z = root;         // To spowoduje zakończenie pętli
      }

  Z->color = 'B';

  delete Y;
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

int main()
{
  int Tk[MAXN];          // Tablica kluczy węzłów
  int i,x,i1,i2;
  TRBTree * RBT;         // Obiekt drzewa czerwono-czarnego

  srand(time(NULL));     // Inicjujemy generator pseudolosowy

  RBT = new TRBTree;     // Tworzymy puste drzewo

  for(i = 0; i < MAXN; i++) // Tablicę wypełniamy wartościami kluczy
    Tk[i] = i + 1;

  for(i = 0; i < 300; i++)  // Mieszamy tablicę
  {
    i1 = rand() % MAXN;     // Losujemy 2 indeksy
    i2 = rand() % MAXN;

    x = Tk[i1];             // Wymieniamy Tk[i1] <-->. Tk[i2]
    Tk[i1] = Tk[i2];
    Tk[i2] = x;
  }

  for(i = 0; i < MAXN; i++) // Na podstawie tablicy tworzymy drzewo czerwono-czarne
  {
    cout << Tk[i] << " ";
    RBT->insertRBT(Tk[i]);
  }

  cout << endl << endl;

  RBT->print();             // Wyświetlamy zawartość drzewa

  cout << endl << endl;

  for(i = 0; i < 300; i++)  // Ponownie mieszamy tablicę
  {
    i1 = rand() % MAXN; i2 = rand() % MAXN;
    x = Tk[i1]; Tk[i1] = Tk[i2]; Tk[i2] = x;
  }

  for(i = 0; i < MAXN >> 1; i++) // Usuwamy połowę węzłów
  {
    cout << Tk[i] << " ";
    RBT->removeRBT(RBT->findRBT(Tk[i]));
  }

  cout << endl << endl;

  RBT->print();            // Wyświetlamy zawartość drzewa

  delete RBT;              // Usuwamy drzewo z pamięci

  return 0;
}
Free Basic
' Drzewo czerwono-czarne
' Data: 11.06.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

const MAXN = 30           ' Liczba węzłów

' Typ węzłów drzewa RBT

Type RBTNode
  up    As RBTNode Ptr
  left  As RBTNode Ptr
  right As RBTNode Ptr
  key   As Integer
  color As String * 1
End Type

' Definicja typu obiektowego TRBTree
Type TRBTree
  Private:
    S As RBTNode          ' Węzeł strażnika
    root As RBTNode Ptr   ' Korzeń drzewa czerwono-czarnego
    cr As String * 2      ' Łańcuchy do znaków ramek
    cl As String * 2
    cp As String * 2       

    Declare Sub printRBT(sp As String, sn As String, p As RBTNode Ptr) ' Wypisuje drzewo

  Public:
    Declare Constructor()                   ' Konstruktor klasy
    Declare Destructor()                    ' Destruktor klasy
    Declare Sub DFSRelease(p As RBTNode Ptr)' Usuwa rekurencyjnie drzewo
    Declare Sub printT()                    ' Wypisuje drzewo
    Declare Function findRBT(k As Integer) As RBTNode Ptr ' Wyszukuje węzeł o kluczu k
    Declare Function minRBT(p As RBTNode Ptr) As RBTNode Ptr ' Wyszukuje najmniejszy węzeł w p
    Declare Function succRBT(p As RBTNode Ptr) As RBTNode Ptr' Wyszukuje następnik p
    Declare Sub rot_L(A As RBTNode Ptr)     ' Rotacja w lewo względem A
    Declare Sub rot_R(A As RBTNode Ptr)     ' Rotacja w prawo względem A
    Declare Sub insertRBT(k As Integer)     ' Wstawia węzeł o kluczu k
    Declare Sub removeRBT(X As RBTNode Ptr) ' Usuwa węzeł X
End Type

' Konstruktor drzewa
'-------------------
Constructor TRBTree()
  cr = Chr(218) + Chr(196)
  cl = Chr(192) + Chr(196)
  cp = Chr(179) + " "
  S.color = "B"          ' Inicjujemy strażnika
  S.up    = @S
  S.left  = @S
  S.right = @S
  root    = @S           ' Korzeń wskazuje strażnika
End Constructor

' Destruktor drzewa
'------------------
Destructor TRBTree()
  DFSRelease(root)       ' Rekurencyjnie usuwamy węzły
End Destructor

' Usuwa rekurencyjnie drzewo czerwono-czarne
'-------------------------------------------
Sub TRBTree.DFSRelease(p As RBTNode Ptr)
  If p <> @S Then
    DFSRelease(p->left)   ' usuwamy lewe poddrzewo
    DFSRelease(p->right)  ' usuwamy prawe poddrzewo
    Delete p              ' usuwamy sam węzeł
  End If
End Sub

' Wypisuje zawartość drzewa
'--------------------------
Sub TRBTree.printRBT(sp As String, sn As String, p As RBTNode Ptr)
  Dim As String t

  If p <> @S Then
    t = sp
    If sn = cr Then Mid(t,Len(t) - 1,1) = " "
    printRBT(t+cp,cr,p->right)

    t = Mid(t,1,Len(sp)-2)
    Print Using "&&&:&";t;sn;p->Color;p->key

    t = sp
    If sn = cl Then Mid(t,Len(t) - 1,1) = " "
    printRBT(t+cp,cl,p->left)
  End If
End Sub

' Wypisuje zawartość drzewa
'--------------------------
Sub TRBTree.printT()
  printRBT("","",root)
End Sub

' Wyszukuje węzeł o kluczu k
' Jeśli węzeł nie zostanie znaleziony, to zwraca
' wskazanie puste NULL
'-----------------------------------------------
Function TRBTree.findRBT(k As Integer) As RBTNode Ptr

  Dim As RBTNode Ptr p

  p = root
  While (p <> @S) AndAlso (p->key <> k)
    If k < p->key Then
    	p = p->Left
    Else
      p = p->Right
    End If
  Wend
  If p = @S Then return 0
  Return p
End Function

' Wyszukuje najmniejszy węzeł w poddrzewie
' o korzeniu p
'-----------------------------------------
Function TRBTree.minRBT(p As RBTNode Ptr) As RBTNode Ptr
  If p <> @S Then While p->left <> @S: p = p->Left: Wend
  Return p
End Function

' Zwraca następnik p
'-------------------
Function TRBTree.succRBT(p As RBTNode Ptr) As RBTNode Ptr

  Dim As RBTNode Ptr r

  If p <> @S Then
    If p->right <> @S Then
      Return minRBT(p->right)
    Else
      r = p->up
      While (r <> @S) AndAlso (p = r->right)
        p = r
        r = r->up
      Wend
      Return r
    End If
  End If
  Return @S
End Function

' Wykonuje rotację w lewo względem A
'-----------------------------------
Sub TRBTree.rot_L(A As RBTNode Ptr)

  Dim As RBTNode Ptr B, p

  B = A->Right
  If B <> @S Then
    p = A->up
    A->right = B->Left
    If A->right <> @S then A->right->up = A

    B->left = A
    B->up = p
    A->up = B

    If p <> @S Then
      If p->left = A then p->left = B: Else p->right = B
    Else
      root = B
    End If
    
  End If
End Sub

' Wykonuje rotację w prawo względem A
'------------------------------------
Sub TRBTree.rot_R(A As RBTNode Ptr)

  Dim As RBTNode Ptr B, p

  B = A->Left
  if B <> @S Then
    p = A->up
    A->left = B->Right
    if A->left <> @S Then A->left->up = A

    B->right = A
    B->up = p
    A->up = B

    If p <> @S Then
      If p->left = A then p->left = B: Else p->right = B
    Else
      root = B
    End If
  End If
End Sub

' Wstawia do drzewa węzeł o kluczu k
'-----------------------------------
Sub TRBTree.insertRBT(k As Integer)

  Dim As RBTNode Ptr X, Y

  X = new RBTNode        ' Tworzymy nowy węzeł
  X->left  = @S          ' Inicjujemy pola
  X->right = @S
  X->up    = root
  X->key   = k
  If X->up = @S Then
  	  root = X ' X staje się korzeniem
  Else
    Do             ' Szukamy liścia do zastąpienia przez X
  
      If k < X->up->key Then
        If X->up->left = @S Then
          X->up->left = X  ' X zastępuje lewy liść
          Exit Do
        End If
        X->up = X->up->Left
      Else
        If X->up->right = @S Then
          X->up->right = X ' X zastępuje prawy liść
          Exit Do
        End If
        X->up = X->up->Right
      End If
      
    Loop
  End If
  
  X->color = "R"         ' Węzeł kolorujemy na czerwono
  
  While (X <> root) AndAlso (X->up->color = "R")
    If X->up = X->up->up->Left Then

      Y = X->up->up->Right ' Y -> wujek X

      If Y->color = "R" Then  ' Przypadek 1
        X->up->color = "B"
        Y->color = "B"
        X->up->up->color = "R"
        X = X->up->up
        Continue While
      End If

      If X = X->up->Right Then ' Przypadek 2
        X = X->up
        rot_L(X)
      End If

      X->up->color = "B" ' Przypadek 3
      X->up->up->color = "R"
      rot_R(X->up->up)
      Exit While
    
    Else              ' Przypadki lustrzane
     
      Y = X->up->up->Left

      if Y->color = "R" Then ' Przypadek 1
        X->up->color = "B"
        Y->color = "B"
        X->up->up->color = "R"
        X = X->up->up
        Continue While
      End If

      if X = X->up->Left Then ' Przypadek 2
        X = X->up
        rot_R(X)
      End If

      X->up->color = "B" ' Przypadek 3
      X->up->up->color = "R"
      rot_L(X->up->up)
      Exit While
    End If
  Wend
  root->color = "B"
End Sub

' Usuwa z drzewa węzeł X
'-----------------------
Sub TRBTree.removeRBT(X As RBTNode Ptr )

  Dim As RBTNode Ptr W, Y, Z

  If (X->left = @S) OrElse (X->right = @S) Then
  	 Y = X
  Else
    Y = succRBT(X)
  End If 

  if Y->left <> @S Then
    Z = Y->Left
  Else
    Z = Y->Right
  End If
  
  Z->up = Y->up

  If Y->up = @S Then
  	 root = Z
  ElseIf Y = Y->up->Left Then
    Y->up->Left = Z
  Else
    Y->up->right = Z
  End If
  
  If Y <> X Then X->key = Y->key

  If Y->color = "B" Then   ' Naprawa struktury drzewa czerwono-czarnego
    While (Z <> root) AndAlso (Z->color = "B")
      If Z = Z->up->Left Then
      	
        W = Z->up->Right

        If W->color = "R" Then ' Przypadek 1
          W->color = "B"
          Z->up->color = "R"
          rot_L(Z->up)
          W = Z->up->Right
        End If

        If (W->left->color = "B") AndAlso (W->right->color = "B") Then ' Przypadek 2
          W->color = "R"
          Z = Z->up
          Continue While
        End If

        if W->right->color = "B" Then ' Przypadek 3
          W->left->color = "B"
          W->color = "R"
          rot_R(W)
          W = Z->up->Right
        End If

        W->color = Z->up->Color ' Przypadek 4
        Z->up->color = "B"
        W->right->color = "B"
        rot_L(Z->up)
        Z = root         ' To spowoduje zakończenie pętli
      Else               ' Przypadki lustrzane
        
        W = Z->up->Left

        If W->color = "R" Then ' Przypadek 1
          W->color = "B"
          Z->up->color = "R"
          rot_R(Z->up)
          W = Z->up->Left
        End If

        If (W->left->color = "B") AndAlso (W->right->color = "B") Then ' Przypadek 2
          W->color = "R"
          Z = Z->up
          Continue While
        End If

        if W->left->color = "B" Then ' Przypadek 3
          W->right->color = "B"
          W->color = "R"
          rot_L(W)
          W = Z->up->Left
        End If

        W->color = Z->up->Color  ' Przypadek 4
        Z->up->color = "B"
        W->left->color = "B"
        rot_R(Z->up)
        Z = root         ' To spowoduje zakończenie pętli
      End If
    Wend
  End If
  Z->color = "B"

  Delete Y
  
End Sub

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

Dim As Integer Tk(MAXN - 1) ' Tablica kluczy węzłów
Dim As Integer i,x,i1,i2
Dim As TRBTree Ptr RBT      ' Obiekt drzewa czerwono-czarnego

Randomize                   ' Inicjujemy generator pseudolosowy

RBT = new TRBTree         ' Tworzymy puste drzewo

For i = 0 To MAXN - 1     ' Tablicę wypełniamy wartościami kluczy
  Tk(i) = i + 1
Next

For i = 0 To 300          ' Mieszamy tablicę
  i1 = Int(rnd() * MAXN)  ' Losujemy 2 indeksy
  i2 = Int(rnd() * MAXN)

  x = Tk(i1)              ' Wymieniamy Tk[i1] <-->. Tk[i2]
  Tk(i1) = Tk(i2)
  Tk(i2) = x
Next

For i = 0 To MAXN - 1     ' Na podstawie tablicy tworzymy drzewo czerwono-czarne
  Print Tk(i);
  RBT->insertRBT(Tk(i))
Next

Print: Print

RBT->printT()             ' Wyświetlamy zawartość drzewa

Print: Print

For i = 0 To 300          ' Ponownie mieszamy tablicę
  i1 = Int(rnd() * MAXN): i2 = Int(rnd() * MAXN)
  x = Tk(i1): Tk(i1) = Tk(i2): Tk(i2) = x
Next

For i = 0 To MAXN \ 2     ' Usuwamy połowę węzłów
  Print Tk(i);
  RBT->removeRBT(RBT->findRBT(Tk(i)))
Next

Print: Print

RBT->printT()            ' Wyświetlamy zawartość drzewa

Delete RBT              ' Usuwamy drzewo z pamięci

End
Wynik
3 25 14 29 10 17 23 2 11 1 15 16 21 6 8 20 27 24 4 5 22 7 13 9 26 28 12 30 18 19


        ┌─R:30
      ┌─B:29
      │ └─R:28
    ┌─R:27
    │ └─B:26
  ┌─B:25
  │ │ ┌─R:24
  │ └─B:23
  │   └─R:22
┌─R:21
│ │   ┌─R:20
│ │ ┌─B:19
│ │ │ └─R:18
│ └─B:17
│   │ ┌─R:16
│   └─B:15
B:14
│     ┌─R:13
│   ┌─B:12
│   │ └─R:11
│ ┌─R:10
│ │ │ ┌─R:9
│ │ └─B:8
│ │   └─R:7
└─B:6
  │   ┌─R:5
  │ ┌─B:4
  └─R:3
    └─B:2
      └─R:1


18 10 2 13 3 5 29 9 30 6 19 28 26 25 21 7

    ┌─B:27
  ┌─B:24
  │ └─B:23
┌─R:22
│ │ ┌─B:20
│ └─B:17
│   │ ┌─R:16
│   └─B:15
B:14
│   ┌─R:12
│ ┌─B:11
└─B:8
  └─B:4
    └─R:1

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe