Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
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:
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:
Pascaltype 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; }; |
BasicType 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.
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.
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:
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.
Ojca B i wujka C kolorujemy na czarno. Dziadka A kolorujemy na czerwono.
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).
Wykonujemy rotację w lewo względem węzła B (w przypadku lustrzanym wykonujemy rotację w prawo względem C).
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):
Wykonujemy rotację w prawo względem węzła A (w przypadku lustrzanym wykonujemy rotację w lewo względem A):
Zmieniamy kolory węzłów A i B na przeciwne:
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.
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 |
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 |
K01: | Utwórz nowy węzeł | tworzymy nowy węzeł |
K02: | X ← adres nowego węzła | |
K03: | (X→left) ← S | liśćmi staje się węzeł strażnik |
K04: | (X→right) ← S | |
K05: | (X→up) ← root | |
K06: | (X→key) ← k | |
K07: | Jeśli (X→up) ≠
S, to idź do kroku K10 |
sprawdzamy, czy drzewo jest puste |
K08: | root ← X | 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 < (X→up→key), to idź do kroku K14 |
porównujemy klucze |
K11: | Jeśli (X→up→right) = S, to: (X→up→right) ← X i idź do kroku 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: | (X→up) ← (X→up→right) | inaczej przechodzimy do prawego syna |
K13: | Idź do kroku K10 | i kontynuujemy pętlę |
K14 | Jeśli (X→up→left) = S, to: (X→up→left) ← X i idź do kroku K17 |
to samo dla lewego syna |
K15: | (X→up) ← (X→up→left) | |
K16: | Idź do kroku K10 | |
K17: | (X→color) ← RED | węzeł kolorujemy na czerwono |
K18: | Dopóki (X ≠ root)
(X→up→color) = RED), wykonuj kroki K19..K47. |
w pętli sprawdzamy kolejne przypadki |
K19: | Jeśli (X→up) ≠ (X→up→up→left), to idź do kroku K34 |
skok do przypadków lustrzanych |
K20: | Y ← ( X→up→up→right) | Y wskazuje wujka węzła X |
K21: | Jeśli (Y→color) = BLACK, to idź do kroku K27 |
sprawdzamy przypadek nr 1 -> wujek jest czerwony |
K22: | (X→up→color) ← BLACK | ojca kolorujemy na czarno |
K23: | (Y→color) ← BLACK | wujka kolorujemy na czarno |
K24: | (X→up→up→color) ← RED | dziadka kolorujemy na czerwono |
K25: | X ← ( X→up→up) | za nowe X przyjmujemy dziadka |
K26: | Następny obieg pętli K18 | i kontynuujemy pętlę |
K27: | Jeśli X
≠ (X→up→right), to idź do kroku K30 |
sprawdzamy przypadek 2 -> wujek czarny, X prawy syn |
K28: | X ← ( X→up) | X staje się swoim ojcem |
K29: | rot_L (root, X) | wykonujemy rotację w lewo, X przechodzi do lewego syna |
K30: | (X→up→color) ← BLACK | przypadek 3 -> wujek czarny, X lewy syn |
K31: | (X→up→up→color) ← RED | zmieniamy kolory ojca i dziadka |
K32 | rot_R (root, (X→up→up)) | wykonujemy rotację w prawo względem dziadka |
K33: | Idź do kroku K48 | i wychodzimy z pętli |
K34: | Y ← ( X→up→up→left) | przypadki lustrzane |
K35: | Jeśli (Y→color) = BLACK, to idź do kroku K41 |
|
K36: | (X→up→color) ← BLACK | |
K37: | (Y→color) ← BLACK | |
K38: | (X→up→up→color) ← RED | |
K39: | X ← ( X→up→up) | |
K40: | Następny obieg pętli K18 | |
K41: | Jeśli X
≠ (X→up→left), to idź do kroku K44 |
|
K42: | X ← ( X→up) | |
K43: | rot_R (root, X) | |
K44: | (X→up→color) ← BLACK | |
K45: | (X→up→up→color) ← RED | |
K46 | rot_L (root, (X→up→up)) | |
K47: | Idź do kroku K48 | wychodzimy z pętli |
K48 | (root→color) ← BLACK | kolorujemy korzeń na czarno |
K49: | Zakończ |
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. |
|
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.
|
|
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. |
|
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.
|
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*. |
|
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*. |
|
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. |
|
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. |
root | – | referencja do zmiennej przechowującej adres korzenia |
X | – | wskazanie usuwanego węzła |
S | – | wskazanie węzła strażnika |
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 |
K01: | Jeśli ((X→left) = S)
((X→right) = 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 (Y→left) ≠ S, to Z ← (Y→left) Inaczej Z ← (Y→right) |
Z jest lewym lub prawym synem usuwanego elementu |
K03: | (Z→up) ← (Y→up) | Ojcem Z będzie ojciec Y |
K04: | Jeśli (Y→up) ≠ S, to idź do kroku K07 |
Sprawdzamy, czy usuwany węzeł jest korzeniem |
K05: | root ← Z | Jeśli tak, to nowym korzeniem będzie jego syn |
K06: | Idź do kroku K08 | Przechodzimy do poprawiania struktury drzewa |
K07: | Jeśli Y = (Y→up→left), to (Y→up→left) ← Z inaczej (Y→up→right) ← Z |
Z zastępuje Y w strukturze drzewa |
K08: | Jeśli Y ≠ X, to (X→key) ← (Y→key) |
Jeśli X nie jest usuwanym węzłem, to przenosimy klucze z Y do X |
K09: | Jeśli (Y→color) = RED, to idź do kroku K52 |
Jeśli usuwany węzeł jest czerwony, to kończymy |
K10: | Dopóki (Z ≠ root)
((Z→color) = BLACK): wykonuj kroki K11…K51 |
Dokonujemy poprawy struktury drzewa czerwono-czarnego |
K11: | Jeśli Z
= (Z→up→right), to idź do kroku K33 |
Skok do przypadków lustrzanych |
K12: | W ← ( Z→up→right) | W wskazuje brata Z |
K13: | Jeśli (W→color) = BLACK, to idź do kroku K18 |
|
K14: | (W→color) ← BLACK | Przypadek 1 |
K15: | (Z→up→color) ← RED | |
K16: | rot_L (root, (Z→up)) | |
K17: | W ← ( Z→up→right) | |
K18: | Jeśli ((W→left→color) = RED)
((W→right→color) = RED), to idź do kroku K22 |
|
K19: | (W→color) ← RED | Przypadek 2 |
K20: | Z ← ( Z→up) | |
K21: | Następny obieg pętli K10 | |
K22: | Jeśli (W→right→color) = RED, to idź do kroku K27 |
|
K23: | (W→left→color) ← BLACK | Przypadek 3 |
K24: | (W→color) ← RED | |
K25: | rot_R (root, W) | |
K26: | W ← ( Z→up→right) | |
K27: | (W→color) ← ( Z→up→color) | Przypadek 4 |
K28: | (Z→up→color) ← BLACK | |
K29: | (W→right→color) ← BLACK | |
K30: | rot_L (root, (Z→up)) | |
K31 | Z ← root i następny obieg pętli K10 | Z = root spowoduje przerwanie pętli |
K32: | W ← ( Z→up→left) | Przypadki lustrzane |
K33: | Jeśli (W→color) = BLACK, to idź do kroku K38 |
|
K34: | (W→color) ← BLACK | Przypadek 1 |
K35: | (Z→up→color) ← RED | |
K36: | rot_R (root, (Z→up)) | |
K37: | W ← ( Z→up→left) | |
K38: | Jeśli ((W→left→color) = RED)
((W→right→color) = RED), to idź do kroku K42 |
|
K39: | (W→color) ← RED | Przypadek 2 |
K40: | Z ← ( Z→up) | |
K41: | Następny obieg pętli K10 | |
K42: | Jeśli (W→left→color) = RED, to idź do kroku K47 |
|
K43: | (W→right→color) ← BLACK | Przypadek 3 |
K44: | (W→color) ← RED | |
K45: | rot_L (root, W) | |
K46: | W ← ( Z→up→left) | |
K47: | (W→color) ← ( Z→up→color) | Przypadek 4 |
K48: | (Z→up→color) ← BLACK | |
K49: | (W→left→color) ← BLACK | |
K50: | rot_R (root, (Z→up)) | |
K51 | Z Z ← root i następny obieg pętli K10 | Z = root spowoduje przerwanie pętli |
K52: | (Z→color) ← BLACK | węzeł Z kolorujemy na czarno |
K53 | Usuń Y | |
K54: | Zakończ |
Uwaga:
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. |
Pascal// 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. |
// 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;} |
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 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.