Metody Programowania - Lista 7

Drzewo czewono-czarne to drzewo binarne, takie że: - każdy węzeł drzewa jest pomalowany albo na czarno albo na czerwono - korzeń drzewa jest pomalowany na czarno - potomek czerwonego węzła jest czarny - każda scieżka od korzenia aż do lisci zawiera tyle samo czarnych węzłów -- liczbę czarnych węzłów w scieżce będę dalej nazywał czarną wysokością drzewa. Czarny węzeł może mieć 0, 1 lub 2 czewone potomki -- czarny węzeł razem z jego czerwonymi potomkami można traktować jako węzeł drzewa wielokrotnie rozgałęzionego zaierający 1, 2 lub 3 klucze i mający (odpowiednio) 2, 3 lub 4 potomków. Czarną wysokość jest równa zwykłej wysokości drzewa wielokrotnie rozgałęzionego odpowiadającego danemu drzewu czewono-czarnemu. Węzły drzewa czewono-czarnego można reprezentować obiektami Pop11 w następujący sposób:

uses objectclass;

define :class Węzeł;
   slot klucz;
   slot lewy = [];
   slot prawy = [];
   slot kolor;
enddefine;

Uwaga: ta deklaracja zakłada że drzewo puste jest reprezentowane nie jako obiekt typu Węzeł, ale jako lista pusta. Po tej deklaracji możemy alokować nowe obiekty przy pomocy procedur consWęzeł (wymaga podania wartości początkowych dla wszystkich slotów) i newWęzeł (nadaje slotom wartości domyślne). We wszystkich zadaniach używać tego typu węzła.

Zadanie 1

Napisać procedurę która sprawdzi czy dane drzewo jest drzewem czerwono czarnym (tzn. czy spełnia podane wyżej warunki).

Uwaga: sprawdzenie można wykonać pojedyńczym przejściem po drzewie.

Zadanie 2

Napisać procedurę która wygeneruje wszystkie struktury drzewa czewono-czarnego z zadaną czarną wysokością i z ilością węzłów nie przekraczającą danego ograniczenia.

Uwaga1: struktura drzewa czarnej wysokości n jest jednoznacznie wyznaczone przez strukturę korzenia odpowiedniego drzewa wielokrotnie rozgałęziaonego oraz przez struktury drzew czarnej wysokości n-1 bedących potomkami kożenia. W szczególności, mając listę (lub) wektor wszystkich drzew czarnej wysokości n-1 i struktórę kożenia możemy wypodukować drzewa wysokości n w zagniżdżonej pętli. A więc progam powinien najpierw obliczyć drzewa czarnej wysokości n-1, a następnie do każdej z 4 możliwych struktur korzenia uruchomić odpowiednią pętlę.

Uwaga2: mówiąc o strukturze drzewa ignorujemy wartości kluczy -- można je pozostawić niezdefiniowane.

Zadanie 3

Napisać procedurę która wygeneruje losową strukturę drzewa czewono-czarne o zadanej czarnej wysokości n.

Uwaga1: Wybrać losowo (przy pomocy procedury random) jedną z czterech struktur korzenia, a następnie rekursywnie wygenerować poddrzewa czarnej wysokości n-1.

Zadanie 4

Napisać procedurę która kluczom drzewa nada kolejne wartości startując z danej liczby początkowej i powiększając ją o zadany krok.

Zadanie 5

Zaadoptować procedurę szukania w drzewie binarnym, tak by szukała w drzewie złożonym n naszych obecnych węzłów. Przetestować ją na losowych drzewach i wszystkich "małych" drzewach.

Zadanie 6

Napisać procedurę wstawiania do drzewie czewono-czarnego według następującego schematu:

Rekursywnie wyszukać miejsce do wstawiania.
Potraktować węzeły jak węzły drzewa wielokrotnie rozgałęzionego (jeśli trzeba wracając do czernego węzła, tak by mieć dostęp do niego i czerwonych potomków).
Jeśli węzeł drzewa wielokrotnie rozgałęzionego zawiera 3 węzły drzewa binarnego (czyli odpowieni czarny węzeł ma 2 czerone potomki) to ten wezeł trzeba podzielić na dwa -- jeden złożony z pojedynczego wezla, drugi z podwójnego. Dodatkowo musimy jeden węzeł wstawić wyżej (i uaktualnić odwołania do potomków w węzłach wyżej).
Jeśli węzeł drzewa wielokrotnie rozgałęzionego zawiera co najwyżej dwa węzły to trzeci węzeł można dodać odpowiednio reorganizując ten węzeł (bez potrzeby wstawiania wyżej).
procedura wsawiająca ma zwracać korzeń drzewa po wstawieniu elementu. Jedna metoda poinformowania procedury nadrzędnej że potrzebne jest wstawienie węzła to pomalowanie wezła do wstawiania na czerwono i zwrócenie go tak jakby był korzeniem normalego podrzewa. W procedurze nadrzędnej widząc że wywałanie rekursywne dało nam węzeł czarny wiemy że wstawianie się zakończyło, zaś widząc węzeł czerwony wiemy że trzeba kontynuować wstawianie.

Przetestować otrzynaną procedurę na "małych" drzewach i drzewach losowych