Metody Programowania - Lista 7

Zadanie 1

Węzły drzewa dwuwymiarowego reprezentują kwadraty. Dany węzeł może być węzłem końcowym (liściem), albo dany kwadrat jest podzielony na cztery równe części i wtedy ten węzeł ma do czterech potomków. Początkowy kwadrat to kwadrat jednostkowy -- o wierzchołkach (0,0), (1,0), (0,1), (1,1). Mamy daną listę punktów. Chcemy żeby w kwadratch odpowiadających węzłom końcowym znajdował się co najwyżej jeden z zadanych punktów. Napisać funkcję (a właściwie trzy oddzielne funkcje) która:

mając dany punkt kwadratu początkowego i drzewo znajdzie węzeł końcowy taki że ten punkt należy do kwadratu związanego z tym węzłem
"wstawi" punkt do drzewa, tzn. znajdzie odpowiadający punktowi węzeł końcowy i jeśli trzeba podzieli ten węzeł
mając dany kwadrat początkowy i listę punktów zbuduje z niego drzewo

Naiwne rozwiązanie w każdym węźle przechowywałoby wierzchołki związanego z nim kwadratu -- jest to niepotrzebne Uwaga: jeśli węzeł leży na brzegu kwadratu to nieważne do którego z sąsiednich kwadratów go zaliczymy (np. można węzeł zaliczać do prawego/górnego kwadratu).

Przypominam że 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). W pozostałych zadaniach używać tego typu węzła.

Zadanie 2

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 3

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ę korzenia 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 4

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 5

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 6

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 7

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