Struktury danych/Drzewa

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

xkcd

Drzewa

Przykład drzewa genealogicznego

Do tej pory zajmowaliśmy się tylko strukturami, które w swej naturze były liniowe, jednak nie wszystko da się w ten sposób przedstawić. Weźmy na przykład drzewo genealogiczne, gdzie relacje pomiędzy elementami tego drzewa pokazują stopień pokrewieństwa pomiędzy członkami rodziny. Niemniej każdy element – dziecko – ma dwoje rodziców, tak samo jak jego rodzice, od tej reguły nie ma odstępstw.

Terminologia

drzewo 1

Drzewa w informatyce, to bardzo szczególne struktury. Jak zobaczymy później są to pewne szczególne grafy i jako takie mają bardzo ścisłą definicję matematyczną, którą podamy przy okazji ich omawiania. Na razie wystarczy nam wiedzieć, że w drzewie istnieje pewien wyróżniony element nazywany korzeniem (na rysunku obok oznaczony przez F), od którego odchodzą poszczególne elementy drzewa – wierzchołki, które połączone są krawędziami. Ciąg krawędzi łączących poszczególne wierzchołki nazywamy ścieżką.

Wszystkie wierzchołki połączone z danym wierzchołkiem, a leżące na następnym poziomie są nazywane dziećmi tego węzła (np. dziećmi wierzchołka F są B i G, natomiast wierzchołka B: A i D). Wierzchołek może mieć dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest liściem. Liśćmi w przykładowym drzewie są A, C, E, H.

Idąc dalej tym tokiem myślowym wierzchołek jest rodzicem dla każdego swojego dziecka.

Drzewa binarne

Jednym z najczęściej wykorzystywanych typów drzew jest drzewo binarne, różni się ono od zwykłego drzewa dodatkowym warunkiem - każdy rodzic może mieć maksymalnie dwoje dzieci. Zwyczajowo mówi się wtedy o lewym i prawym dziecku. To ograniczenie, jak mogłoby się zdawać, jest jednak bardzo użyteczne, o czym można się przekonać czytając następny rozdział o drzewach BST.

Sposoby przeglądania struktur nieliniowych

W przypadku listy czy tablicy jedyną różnicą jaką możemy uczynić podczas przeglądania tej struktury jest to czy zaczniemy wypisywanie elementów od początku czy od końca. Wynika to z ich liniowego charakteru. Jednakże w przypadku drzew sprawa przestaje być już aż tak oczywista. Aby wypisać wszystkie elementy drzewa można zastosować dwa podejścia - przeglądanie w głąb kolejnych poddrzew (ang.Depth First Search - DFS) lub przeglądanie poziomami drzewa - przeglądnie wszerz (ang. Breadth First Search - BFS). Poniżej zaczniemy od omówienia pierwszego podejścia. Ponadto już teraz warto wspomnieć, że te terminy okażą się bardzo ważne przy omawianiu grafów.

Przegląd DFS

Za przykład posłuży nam drzewo binarne, ale opisane tu procedury można z powodzeniem rozszerzyć na inne typy drzew. Istnieją 3 podstawowe porządki w jakich można wypisywać struktury nieliniowe:

• PREORDER
• INORDER
• POSTORDER

W tym momencie bardzo przydatna jest znajomość Odwrotnej Notacji Polskiej (czy tematyki związanej z reprezentacją wyrażeń w systemach komputerowych), ponieważ problemy związane z zapisem wyrażeń matematycznych można w prosty sposób połączyć z drzewami binarnymi. Podstawowe działania matematyczne mają pewną hierarchię wykonywania operacji, i w tym momencie można skorzystać z drzew do reprezentacji tych wyrażeń (wiąże się to również z tym, że niewiele jest operatorów, których liczba argumentów byłaby większa niż 2).

Weźmy na przykład wyrażenie $(2+4)*(15-3)/(7*4)^{(13/34)}$ i spróbujmy stworzyć drzewo, które opisywałoby po kolei jakie operacje matematyczne będziemy wykonywać. Oczywiście w zapisie infiksowym (czyli takim jak tutaj) połapać się w kolejności wykonywania działań pomagają nawiasy. Czytając od lewej do prawej: najpierw dodajemy zawartość pierwszego nawiasu, na tym samym poziomie będziemy rysować odejmowanie z drugiego nawiasu, wyniki następnie pomnożymy, ale żeby móc wykonać dzielenie, które nam się następnie pojawia musimy najpierw wykonać działania po prawej stronie operatora.Tzn. tym razem pomnożymy liczby w pierwszym nawiasie następnie podzielimy to co mamy w wykładniku i dopiero podniesiemy do potęgi. Teraz mamy dopiero wartość, z której możemy skorzystać w dzieleniu. Kiedy narysujemy drzewo tych operacji to dostaniemy coś podobnego do rysunku poniżej.

Dobrze, a teraz zastanówmy się jak wyglądałoby to wyrażenie gdybyśmy przekształcili je do notacji polskiej. W ramach przypomnienia - jest ona dla nas bardzo naturalna, ponieważ stara się naśladować sposób w jaki normalnie (w języku naturalanym w przeciwieństwie do języka symboli matematycznych) opisujemy wyrażenia matematyczne, czyli nasze wyrażenie to jest "iloraz iloczynu sumy 2 i 4 oraz różnicy 15 i 3 oraz wyniku podnoszenia iloczynu 7 i 4 do potęgi wyniku ilorazu 13 i 34", znów używając symboli matematycznych bez nawiasów: / * + 2 4 - 15 3 ^ * 7 4 / 13 34. Z kolei w odwrotnej notacji polskiej sprowadziłoby się to do wyrażenia o postaci: 2 4 + 15 3- * 7 4 * 13 34 / ^ /.

W jaki sposób łączy się to z wypisywaniem drzewa? Nasza normalna notacja wyrażeń nazywana jest infiksową co odpowiada wypisywaniu drzewa, które powyżej przedstawiliśmy, w porządku inorder, z kolei notację polską nazywa się również notacją prefiksową, co odpowiada porządkowi preorder powyższego drzewa. Widać już, że ONP (tj. notacja postfiksowa) analogicznie odpowiada wypisaniu postorder.

Przy opisywaniu sposobu przeglądania drzewa przydatne jest zdefiniowanie pewnych abstrakcyjnych operacji: V (ang. visit) - wypisanie wartości węzła, L (ang. left) - przejście do lewego dziecka (o ile istnieje), R - (ang. right) - przejście do prawego dziecka(o ile istnieje).

Korzystając z tej terminologii działanie poszczególnych procedur można w skrócie zapisać tak:

• INORDER = LVR
• PREORDER = VLR
• POSTORDER = LRV

Pokażemy teraz rekurencyjne funkcje napisane w C++, które będą wykonywały te procedury, zakładając, że istnieje pewna struktura Node odpowiadająca węzłowi drzewa, zawierająca pola left oraz right, które są wskaźnikami na dzieci tego węzła oraz funkcja print_node służąca do wypisywnaia węzła.

Inorder

void inorder(Node n){
if(left != nullptr) inorder(n->left);
print_node(n);
if(right!= nullptr) inorder(n->right);
}

Spójrzmy jeszcze raz na drzewo 1. Korzystając z tej funkcji spróbujmy wypisać znajdujące się tam elementy. Zaczynamy w korzeniu, tj. wierzchołku F. Istnieje lewe dziecko więc wywołujemy funkcję jeszcze raz na tym dziecku - wierzchołku B. Sytuacja w tym wierzchołku się powtarza, wywołujemy na rzecz A. Dopiero ten wierzchołek jest liściem, więc go wypisujemy. Do tej pory wypisaliśmy

A

Wracamy do wywołania na rzecz B, wypisujemy B i wywołujemy na rzecz D.

A B

D nie jest liściem, więc wywołujemy na rzecz C, które jest więc je wypisujemy i wracamy do wywołania na rzecz D. Wypisujemy D i wywołujemy funkcję znów na rzecz E, które jest liściem, więc wypisujemy. Do tej pory mamy więc:

A B C D E

W tym momencie wracamy do pierwszego wywołania i wypisujemy korzeń - F i wywołujemy na rzecz prawego dziecka G.

A B C D E F

G nie ma lewego dziecka, więc wypisujemy i wywołujemy na rzecz I. I nie jest liściem, wywołuje się od razu jego dziecko H, które liściem już jest.

A B C D E F G H

Wracamy do wywołania na rzecz I i wypisujemy. Wszystkie wywołania rekurencyjne się kończą, a na ekranie będziemy mieć :

A B C D E F G H I

Preorder

void preorder(Node n){
print_node(n);
if(left != nullptr) preorder(n->left);
if(right!= nullptr) preorder(n->right);
}

Warto zauważyć, że ten sposób pierwszym wypisywanym elementem będzie korzeń drzewa (ewentualnie poddrzewa), co jest bardzo użyteczną informacją gdybyśmy mieli na przykład utworzyć drzewo mając do dyspozycji dwa wypisania tego drzewa, w preorderze oraz dodatkowo za pomocą inorder(dzięki temu można jednoznacznie je odtworzyć).

W podobny sposób jak w przypadku inorder można "na sucho" przetestować działanie tego algorytmu. Wynikiem powinno być:

F B A D C E G I H

Postorder

void postorder(Node n){
if(left != nullptr) postorder(n->left);
if(right!= nullptr) postorder(n->right);
print_node(n);
}

Skorzystajmy jeszcze raz z drzewa operacji i spróbujmy za pomocą tego algorytmu utworzyć zapis w ONP.

Wywołujemy postorder na korzeniu "/". Nie jest liściem, więc wywołujemy rekurencyjnie na lewym poddrzewie "*". Sytuacja się powtarza, więc wywołujemy na "+". Tutaj znów nie jest to liść, więc wywołujemy na "2" i od razu wypisujemy, potem to samo dzieje się dla "4". Mamy więc :

2 4 Wracamy z wywołaniem do "+" i wypisujemy. I wywołujemy funkcję na rzecz prawego poddrzewa "*". Przy czym na ekranie jest już:

2 4 +

Wierzchołek "-" nie jest liściem. Kolejne dwa wywołania wypisują 15 i 3, a następnie "-".

2 4 + 15 3 -

Dopiero teraz wracamy z wywołaniami do "*" i wypisujemy. Następnie stos wywołań zwija się do tego na rzecz korzenia. Ponownie wywołujemy funkcję na rzecz prawego poddrzewa "^".

2 4 + 15 3 - *

Następne wywołania są analogiczne. Dostajemy w rezultacie:

2 4 + 15 3 - * 7 4 * 13 34 / ^ /

Z tego wynika, że można by za pomocą przechodzenia drzewa napisać program, który mógłby zamieniać wyrażenia z jednej notacji na inną, wystarczyłoby tylko napisać funkcje, które tworzyły by poprawne drzewa z każdego zapisu, a jest to już zadanie problematyczne.

Typy drzew

1. Drzewa wyszukiwań binarnych
2. Drzewa czerwono-czarne
3. Drzewa AVL
4. Drzewa przedziałowe
5. Drzewa czwórkowe

Ćwiczenia

Podstawowe

Ćwiczenie 1: Zaimplementuj podane tutaj procedury przechodzenia drzewa binarnego nie używając funkcji rekurencyjnych.

Ćwiczenie 2: Napisz program, który mając dostępne wyniki działania procedur inorder oraz preorder lub postorder zbuduje wyjściowe drzewo binarne.

Zaawansowane

Ćwiczenie 1: Napisz program, który jako dane wejściowe będzie przyjmował wyniki procedury inorder oraz jednej z procedur preorder, postorder, który w wyniku działa będzie zwracał przejście niepodane dla danego drzewa(tzn. jeśli dostajesz preorder, inorder to masz zwrócić postorder).