Dziś powiemy sobie o strukturach drzewiastych. Drzewiastą strukturą danych (drzewem) nazywamy strukturę danych S = (D, R, e), w której relacja porządkująca N opisuje hierarhiczne powiązania pomiędzy węzłami drzewa tworzącymi kolejne poddrzewa. Warto zwrócić uwagę, że drzewo ze stwojej natury jest strukturą hierarhiczną, czyli rekurencyjną. Niezwykle istotne jest więc tutaj odpowiednie przypisanie danych elementarnych ze zbioru D do kolejnych poziomów drzewa i zdefiniowanie relacji N określającej porządek w drzewie. Teraz powiedzmy sobie jeszcze o kilku ważnych pojęciach. Te pojęcia to:

1. Korzeń drzewa - Jest to element drzewa wskazywany przez element wejściowy e. Zawsze istnieje tylko jeden korzeń drzewa.

2. Liść drzewa - Jest to element drzewa, który nie posiada następnika w sensie relacji N.

3. Stopień drzewa - To maksymalna liczba możliwych następników dla dowolnego elementu drzewa. Najczęściej przyjmuje się, że stopień drzewa jest potęga liczby 2 (drzewa dwójkowe, czwórkowe, ósemkowe, szesnastkowe).

4. Droga w drzewie to ciąg kolejnych łuków pomiędzy dwoma elementami drzewa, które trzeba pokonać, aby dojść od jednego elementu drzewa do innego.

5. Poziom drzewa to elementy ułożone w tej samej odległości (długości drogi) od korzenia drzewa.

6. Drzewo zupełne to takie drzewo, którego wszystkie elementy prócz liści mają taką liczbę nastepników, ile wynosi stopień drzewa.

7. Wysokośc drzewa - Różnica pomiędzy najwyższym i najniższym poziomem drzewa (przy założeniu, że korzeń znajduje się na poziomie najniższym).

I teraz zacznijmy od najprostszej struktury drzewiastej - drzewa binarnego (dwójkowego). Zauważmy na poniższym rysunku, że jest to drzewo o 2 stopniu (każdy węzeł ma co najwyżej dwa następniki), oraz ze na ostatnim, czyli najniższym poziomie drzewa są liście (elementy, które nie mają następników):

Korzeniem będzie tu jak widać e, a liśćmi - 20, 25, 29, 31. Relacją wejściową będzie z kolei połączenie e z 2. I mamy tu między innymi połączenia e - 2, 2- 13, 2 - 12, 10 - 25 …

Popatrzmy teraz jak się okresla w dowolnym drzewie jego rekurencję, czyli na jakie inne drzewa się takie przykładowe drzewo dzieli:

A oto, jak wygląda jeszcze inne drzewo binarne będące strukturą drzewiastą:

Przejdźmy teraz do omawiania drzewa, jakim jest drzewo poszukiwań binarnych BST będace odmianą drzewa binarnego. Jak wiadomo w zupełnym drzewie binarnym każdy węzeł z wyjątkiem liści ma dokładnie dwa następniki. W przypadku drzewa BST, dla każdego węzła nie będącego liściem wszystkie wartości przechowywane w lewym poddrzewie są mniejsze od jego wartości, natomiast wszystkie wartości przechowywane w prawym poddrzewie sa większe od wartości w tym węźle. Popatrzmy na różnicę. Poniżej zwykłe drzewo binarne (po lewej), oraz drzewo BST będące jego odmianą:

Co gdybyśmy chcieli znaleźć w obydwu drzewach wartość 31. Na pewno mniej czasu nam to zajmie w przypadku drzewa BST, bo od razu nastapi przejście z korzenia do liczby 25, a potem do 31. Jednak drzewo BST ma kilka wad. Jedną z nich jest fakt, że mając dane dwa dowolne drzewa z tym samym zbiorem wartości mogą one osiągać różną wysokość. Zobaczymy to na rysunku poniżej:

Dla pierwszego drzewa z korzeniem 10 mamy wysokość równą trzy, ale przy zamianie korzenia z 10 na 8 już mamy wysokośc równą cztery. Zatem jeśli najmiejszą z wartości przeniesiemy do korzenia (w tym wypadku 2) powstanie nam zwykła lista - i to jest cały minus tej metody. Istnieje tez wiele ograniczeń w drzewie poszukiwań binarnych BST. Podstawowe operacje realizują się szybko (O (log n)) dzięki symetrycznemu porządkowi.

Jeśli jednak do drzewa będizemy wstawiać elementy, drzewo rozrośnie się w jedną ze stron (może być w skrajnym przypadku zdegenerowane do winorośli, czyli listy powiązanej). Zlożonośc poszukiwania takiego zdegenerowanego drzewa (a tymsamym wszystkich innych operacji) jest liniowa O(n). Aby równoważyć drzewa BST wymyślono ich różne odmiany, jak drzewa AVL, czy drzewa czerwono czarne. Dzięki zrównoważeniu nie tracimy podstawowej zalety struktury drzewiastej: mniejszej niż liniowa złożoności obliczeniowej.

Teraz nieco o podstawowych operacjach na drzewach binarnych. Są to: szukanie elementu w drzewie przechodzenie po drzewie, dołączanie elementu do drzewa i usuwanie elementu z drzewa. Istnieje pewna uwaga, że wszystkie te operacje często są realizowane rekurencyjnie.

Spójrzmy teraz na schemat i zobaczmy, co zawiera pojedynczy element drzewa. Są to dwa składniki - dane elementarne, oraz realizację relacji następstwa (wskaźniki na następniki):

Mówiliśmy więc o zasadzie drzewa binarnego i zasadzie drzewa BST. Istnieją jeszcze dwa istotne drzewa: drzewo AVL i kopiec. O drzewie BST będącego drzewem AVL mówimy, gdy dla każdego wierzchołka wysokości jego dwóch poddrzew (lewego i prawego) różnią się co najwyżej o 1 poziom. Z kolei kopiec zwany inaczej stertą (stogiem) charakteryzuje się tym, że wartości przechowywane w nastepnikach kazdego węzła są mniejsze od wartości w danym węźle (kopiec maksymalny), ale też charakteryzuje się także tym, że wartości przechowywane w nastepnikach kazdego węzła mogą być większe od wartości w danym węźle. Wtedy mówimy o kopcu minimalnym. W kopcu jest tak, że drzewo jest szczelnie wypełniane (zrównoważone) od lewego poddrzewa. No i porównajmy drzewo BST z kopcem:

Wróćmy jednak do drzew poszukiwań BST i podstawowych operacjach, które można na takich drzewach wykonać. Na początek deklaracja elementu drzewa binarnego, która prezentuje się nastepująco:

Do tego dochodzi pomocniczy typ wskaźnikowy do struktury Node o nastepującej postaci:

Typedef struct Node *NodePtr;

Zmienna tego typu, jak powyżej będzie wskazywać korzeń. I teraz jakie mamy operacje. Pierwszą operacją, jaką można wykonać na drzewie jest wyszukanie elementu w takim drzewie BST. Algorytm przedstawia się tak, że główny cel to uzyskanie dowiązania do węzła, które można interpretować jako identyfikację węzła. Za dane posłuży dowiązanie do korzenia drzewa Root. No i istnieje kilka uwag. Kolejnośc przeszukiwania drzewa jest dowolna. W skrajnym przypadku należy jednak przejrzeć wszystkie węzły w drzewie - złożoność (O(n)). W przypadku wyszukiwania stosuje się dwie metody: pętli oraz rekurencji. No i konkretny algorytm:

1. Ustaw aktualne dowiązanie na korzeń drzewa.

2. Dopóki aktualne rozwiązanie jest różne od NULL, to:

1. Jeśli wartość szukana jest mniejsza od danej aktualnego węzła, to szukaj w

jego lewym poddrzewie.

2. Jeśli wartość szukana jest większa od danej aktualnego węzła, to szukaj w

jego prawym poddrzewie.

3. Jeśli wartość szukana jest równa danej aktualnego węzła, to koniec - zwróć

dowiązanie do węzła.

Spójrzmy na wersję procedury iteracyjnej:

No i popatrzmy na wersję procedury rekurencyjnej:

Teraz zajmiemy się kolejnym algorytmem - przechodzenia po drzewie binarnym. Celem takiego algorytmu będzie jednokrotne odwiedzenie każdego elementu drzewa. Za dane wejściowe posłuży nam dowiązanie do korzenia drzewa Root. Warto dodać jednak dwie uwagi, że kolejność przejścia jest tu dowolna (liczba możliwych ścieżek w drzewie o n węzłach wynosi n!), oraz że najczęstszymi sposobami przeglądania sa sposoby wszerz i wgłąb o których powiemy. Załóżmy, ze mamy drzewko:

Przechodzenie wszerz polega na odwiedzaniu kolejno każdego węzła od najwyższego (najniższego) poziomu i przechodzeniu kolejno po tych poziomach od góry w dół (od dołu do góry) i od lewej do prawej (od prawej do lewej). Z kolei metoda wgłąb polega na przejściu jak najdalej w lewo (prawo), nastepnie powrocie do pierwszego rozwidlenia, przejściu jeden krok w prawo (lewo) i tak dalej. Skupmy się na maetodzie w głąb, a oknkretnie na algorytmie przechodzenia po drzewie binarnym w taki oto sposób. Wyróżnia się trzy wersje przejścia - inorder (LVR), preorder (VLR) i postorder (LRV). Ta pierwsza polega na przejściu dolewego poddrzewa (L), odwiedzeniu węzła (V) i przejściu do prawego poddrzewa (R). Metoda preorder polega na odwiedzeniu węzła (V), przejściu do prawego poddrzewa (R), oraz na przejściu dolewego poddrzewa (L). I ostatnia metoda - postorder. Ta poega na przejściu dolewego poddrzewa (L), przejściu do prawego poddrzewa (R) i odwiedzeniu węzła (V). Popatrzmy, jak implementujemy wszystkie te trzy procedury w kolejności: INORDER, PREORDER, POSTORDER:

Kolejnym ciekawym algorytmem jest algorymtm dołączania elementu do drzewa BST. Głównym celem jest dodanie nowego elementu do drzewa, zaś danymi wejściowymi będzie dowiązanie do korzenia drzewa Root, oraz nowe dane elementarne. Algorytm ten składa się z trzech kroków:

1. Utwórz element i ustaw dane elementarne.

2. Znajdź miejsce wstawienia elementu w drzewie.

3. Wstaw element do drzewa (wstaw element jako pierwszy w drzewie, lub wstaw element we wskazane miejsce w drzewie).

No i czas na implementację funkcji:

No i na sam koniec zostawiamy algorytm usuwania elementu z drzewa binatnego. Celem jest usunięcie węzła z drzewa. Za dane wejściowe posłuży dowiązanie do korzenia drzewa Root, oraz opis elementu usuwanego (na przykład wartość danej elementarnej). Rozpatrzymy algorytm dla trzech przypadków: gdy węzeł jest liściem, gdy węzeł ma jednego potomka, oraz gdy węzeł ma dwóch potomków. Najpierw rozpatrzmy pierwszy z przypadków:

W tym przypadku węzeł jest liściem. Należy więc znaleźć element w drzewie i usunąć węzeł z drzewa tak, jak na rysunku niżej:

W drugim przypadku gdy węzel ma jednego potomka należy znaleźć element w drzewie, usunąć węzeł z drzewa i zastąpić węzeł usunięty jego potomkiem (zmiana wskaźnika w poprzedniku węzła usuwanego).

I ostatni przypadek, gdy węzeł ma dwóch potomków. Tutaj należy znaleźć element w drzewie, usunąć węzeł z drzewa i zastapić węzeł usunięty najmniejszym z prawego poddrzewa lub największym z lewego poddrzewa.

Popatrzmy niżej na przypadek w wersji z usunięciem najmniejszego elementu z prawego poddrzewa (skrajnie lewy wierzcho.łek tego poddrzewa):

Oraz popatrzmy na inna wersję z usunięciem największego elementu z lewego poddrzewa (skrajnie prawy wierzchołek):

Podsumowując wykład ze struktur drzewiastych usunięcie węzła z drzewa BST prowadzi do jednego z trzech poniższych przypadków:

Teraz natomiast zakończymy ten wykład i przejdziemy do kolejnego tematu, jakim jest temat związany z drzewami zrównoważonymi. Drzewo binarne jest zrónoważone, jeżeli dla każdego węzła wysokości dwóch jego poddrzew (lewego i prawego) różnią się co najwyżej o 1 (własności drzew AVL). Dla drzewa zrównoważonego o liczbie węzłów równej n, każda droga od korzenia do któregokolwiek z węzłów w tym liści nie jest dłuższa niż logarytm przy podstawie 2 z n. Na następnej stronie przykład zrównowazonego drzewa binarnego:

Zacznijmy od drzew częściowo uporządkowanych. Są to drzewa binarne mające nastepującą własność. Element przechowywany w węźle musi mieć co najmniej (co najwyżej) tak dużą wartość, jak wartości nastepników tego węzła. Własnośc ta oznacza, że element w korzeniu dowolnego poddrzewa jest zawsze największym (najmniejszym) elementem tego poddrzewa. Oto, jak wygląda takie drzewo częściowo uporządkowane:

Drzewo częściowo uporządkowane jest zrównoważone, jeżeli jest drzewem zrównoważonym:

Przykładem drzewa częściowo uporządkowanego może być kopiec. Drzewo binarne jest kopcem, jeśli wartości przechowywane w następnikach każdego węzła są mniejsze od wartości w danym węźle (kopiec maksymalny) lub wartości przechowywane w nastepnikach każdego węzła sa większe od wartości w danym węźle (kopiec minimalny). Tutaj drzewo jest zrównoważone, a wszystkie liście najniższego poziomu znajdują się na jego skrajnych lewych pozycjach. Przykłady kopców znajdują się na stronie 4. Po lewej stronie znajduje się kopiec maksymalny, a po lewej - minimalny. Kopiec można zaimplementować bazując na tablicy jednowymiarowej (wektorze) o długości n. Elementy są umieszczone w drzewie w kolejnych węzłach od góry do dołu i od lewej strony do prawej. Istotny jest fakt, że każdy kopiec jest tablicą, ale nie każda tablica kopcem. Oto cztery podstawowe cechy charakterystyczne tablicy A implementującej kopiec:

1. Korzeń znajduje się w A[0].

2. Po korzeniu zapisujemy w tablicy kolejne poziomy.

3. Zatem lewy następnik korzenia znajduje się w A[1], a prawy następnik korzenia w A[2].

4. Ogólnie: lewy następnik węzła zapisanego w A[i] znajduje się w A[2i+1], prawy nastepnik w A[2i+2] (jeżeli nastepniki istnieją).

Oto reprezentacja tablicowa kopców:

Dla kopca:

Zachodzą dwie nierównoci:
i
.

Przejdźmy teraz do przekształcenia tablicy w kopiec. Robi się to metodą wstepującą Floyda, dla której warunek implementujemy tak:

Prototyp funkcji MoveDown wygląda następująco:

void MoveDown(T data[] int frist, int last);

Zobaczmy na ilustracji idee działania tej funkcji:

I tutaj element 9 przeskakuje na mniejsce 25, nastepnie na miejsce 18 i 15. I tak drzewo staje się kopcem. A oto pełna implementacja tej metody:

I na zakończenie wykładu popatrzmy na 7 kroków przekształcenia tablicy

A = [2 8 6 1 10 15 3 12 11] metodą Floyda:

Następniki katego węzła na bocznym rysunku drzewa mają indeksy równe 2k + 1 (lewy nastepnik) i 2k + 2 (prawy nastepnik). Węzeł nadrzędny ma tu indeks równy k/2

---