Algorytmy i struktury danych - 05. Drzewa binarne.pdf - Grafika komputerowa - pmtg

Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne

Lekcja 5: Drzewa binarne

Wst ħ p

W tym rozdziale zajmiemy si ħ drzewami binarnymi, które s Ģ dynamicznymi strukturami rekurencyjnymi. Zamiast opisywa ę ich

sił ħ i mo Ň liwo Ļ ci - prezentujemy interesuj Ģ cy przykład zastosowania. To dla zach ħ ty, by Ļ cie polubili tworzenie struktur

drzewiastych.

Drzewo binarne

W Waszych programach niejednokrotnie zajdzie potrzeba zastosowania bardziej wyrafinowanych struktur danych ni Ň prosta lista.

Listy s Ģ znacznie bardziej elastyczne ni Ň tablice (poprzez dynamiczny sposób ich tworzenia), niestety s Ģ one tylko strukturami

liniowymi i przedstawienie zło Ň onych relacji mi ħ dzy obiektami przy u Ň yciu list jest mało wygodne. Struktur Ģ , któr Ģ zajmiemy si ħ

w tym rozdziale, b ħ dzie drzewo (ang. tree ). Tak jak lista jednokierunkowa jest najprostsz Ģ dynamiczn Ģ struktur Ģ liniow Ģ

(jednowymiarow Ģ ), tak drzewo jest dynamiczn Ģ struktur Ģ wielowymiarow Ģ . Drzewo jest regularn Ģ struktur Ģ danych składaj Ģ c Ģ si ħ

z w ħ złów (odpowiednik elementów na li Ļ cie) posiadaj Ģ cych co najmniej dwa wska Ņ niki do takich samych w ħ złów. Tak, jak

prawdziwe drzewo w przyrodzie posiada liczne rozgał ħ zienia, tak samo i drzewo w informatyce posiada w ħ zły (wierzchołki) –

miejsca rozgał ħ zie ı . Ka Ň dy w ħ zeł mo Ň e wskazywa ę na kilka innych w ħ złów w drzewie. Jedynym w ħ złem, na którego nie

wskazuje Ň aden inny w ħ zeł drzewa, jest korze ı . Natomiast w ħ zły, których wska Ņ niki s Ģ puste (czyli nie wskazuj Ģ na Ň aden inny

w ħ zeł), nazywamy najcz ħĻ ciej li Ļ cmi . Na ogół drzewa s Ģ przedstawiane w sposób graficzny z korzeniem na górze rysunku oraz z

li Ļę mi na dole. W ħ zły wskazywane przez dany w ħ zeł nazywamy jego synami (potomkami), natomiast on jest w stosunku dla nich

ojcem . Najprostszym i zarazem najcz ħĻ ciej u Ň ywanym rodzajem drzewa jest drzewo binarne . Jest to struktura dwuwymiarowa.

W praktyce przejawia si ħ to tym, Ň e ka Ň dy element (w ħ zeł) ma dokładnie dwie odnogi - lew Ģ i praw Ģ (oczywi Ļ cie nie ka Ň da z nich

musi by ę wypełniona). Rysunek poni Ň ej pokazuje, jak takie drzewo mo Ň e wygl Ģ da ę .

2008-04-18 15:21

Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne

Kolorem niebieskim oznaczyli Ļ my wska Ņ niki do innych w ħ złów drzewa. ņ eby uci Ģę w Ģ tpliwo Ļ ci – wska Ņ niki równe NULL/nil nie

s Ģ narysowane w postaci strzałek. Typowa definicja pojedynczego w ħ zła b ħ d Ģ cego składnikiem drzewa binarnego jest

nast ħ puj Ģ ca:

struct Twezel {

int Dane;

Twezel *Lewy;

Twezel *Prawy;

};

Ka Ň dy w ħ zeł zawiera pole do przechowywania informacji oraz dwa wska Ņ niki. Jak widzimy, wska Ņ niki w w ħŅ le zostały nazwane

mianem lewego oraz prawego – na ogół stosuje si ħ wła Ļ nie takie nazewnictwo, w którym w ħ zeł mo Ň e mie ę lewego oraz prawego

syna. Pami ħ tajmy, Ň e ka Ň dy w ħ zeł w drzewie binarnym nie musi mie ę obu synów – mo Ň e nie mie ę Ň adnego, mo Ň e mie ę równie Ň

jednego z synów (lewego lub prawego).

W tym miejscu nale Ň y wyja Ļ ni ę jedn Ģ niezmiernie istotn Ģ rzecz. Otó Ň , jak wiecie, lista dwukierunkowa składa si ħ z elementów

zawieraj Ģ cych dwa wska Ņ niki. Ró Ň nica mi ħ dzy tak Ģ list Ģ a drzewem kryje si ħ w sposobie poł Ģ czenia elementów. Elementy listy

dwukierunkowej pokazuj Ģ na siebie wzajemnie, tzn. je Ļ li drugi element listy wskazuje na trzeci, to trzeci wskazuje na drugi. Z

tego faktu wynika jeszcze jedno – ka Ň dy element listy z wyj Ģ tkiem pierwszego i ostatniego musi mie ę dwóch s Ģ siadów – czyli oba

wska Ņ niki w nim umieszczone s Ģ ró Ň ne od NULL/nil.

Natomiast przy drzewie binarnym zale Ň no Ļę ta nie jest spełniona. Po pierwsze: w ħ zeł mo Ň e mie ę jednego, dwu, lub nie mie ę

wcale synów. Po drugie: je Ļ li A wskazuje na B, to B nie mo Ň e wskazywa ę na A.

Drzewa binarnego wyszukiwania

Drzewa binarne mog Ģ by ę tworzone według ró Ň nych reguł. Jedn Ģ z grup drzew binarnych, na której s Ģ okre Ļ lone reguły

zachowywania si ħ elementów w drzewie s Ģ drzewa binarnego przeszukiwania (ang. Binary Search Tree - BST ). Struktura BST

jest stosowana przede wszystkim w celu szybkiego wyszukiwania danych (a tak Ň e dodawania i usuwania informacji); cz ħ sto przy

u Ň yciu takich drzew realizowane s Ģ struktury słownikowe oraz kolejki priorytetowe, które dopiero poznacie. Główna zasada

istniej Ģ ca w drzewie BST jest taka, Ň e warto Ļ ci w w ħ złach znajduj Ģ cych si ħ „na lewo” od danego w ħ zła s Ģ mniejsze ni Ň warto Ļę

zapisana w tym w ħŅ le, natomiast wszystkie warto Ļ ci w w ħ złach znajduj Ģ cych si ħ „na prawo” od danego w ħ zła s Ģ wi ħ ksze ni Ň

warto Ļę w nim zapisana. Mówi Ģ c Ļ cisłej, warto Ļę w w ħŅ le jest wi ħ ksza ni Ň warto Ļ ci w w ħ złach znajduj Ģ cych si ħ w lewym

poddrzewie (czyli drzewie o korzeniu b ħ d Ģ cym jego lewym synem), natomiast warto Ļę w konkretnym w ħŅ le jest mniejsza ni Ň

warto Ļ ci w w ħ złach znajduj Ģ cych si ħ w prawym poddrzewie. Zatem:

wszystkie warto Ļ ci lewego poddrzewa < warto Ļę w w ħŅ le < wszystkie warto Ļ ci prawego poddrzewa

Ta zale Ň no Ļę obowi Ģ zuje na ka Ň dym poziomie drzewa BST, a wi ħ c zarówno dla jego korzenia, jak i dla wszystkich poddrzew

dowolnego w ħ zła. Mo Ň ecie to sprawdzi ę na poni Ň szej animacji i na wszystkich nast ħ pnych rysunkach w tej lekcji.

2008-04-18 15:21

Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne

Struktura BST wymaga, by ka Ň dy w ħ zeł posiadał unikatow Ģ warto Ļę danej - to bardzo wa Ň ne: elementy drzewa BST nie mog Ģ si ħ

powtarza ę !.

Przyjrzyjcie si ħ , jak działa proces tworzenia drzewa BST:

Skoro pokazali Ļ my w sposób graficzny, jak dodawane s Ģ nowe elementy do drzewa BST, to równie Ň warto przedstawi ę Ļ cisły kod

budowania takiego drzewa. Kod realizuj Ģ cy dodawanie nowego w ħ zła mo Ň na przedstawi ę w postaci procedury rekurencyjnej (z

przekazywaniem referencji do wska Ņ nika), wraz z przykładowym jej wywołaniem w programie:

void DodajWezel (Twezel *&wezel, int wartosc) {

if (wezel == NULL) { // tworzymy i doł Ģ czamy element

wezel = new Twezel;

wezel -> Dane = wartosc;

wezel -> Lewy = NULL;

wezel -> Prawy = NULL;

}

else

if (wartosc < wezel -> Dane) DodajWezel (wezel -> lewy, wartosc ); // rekurencyjne wywo

else

if (wartosc > wezel -> Dane) DodajWezel (wezel -> prawy, wartosc ); // rekurencyjne wywola

// uwaga: liczby powtarzaj Ģ ce si ħ nie s Ģ dodawane do drzewa

}

int main( ) {

int n, liczba;

Twezel korzen;

korzen=NULL;

cin >> n; // załó Ň my, Ň e n liczb ma by ę wczytanych

for ( int i=0; i<n; i++) {

cin >> liczba;

DodajWezel (korzen, liczba);

// teraz korzen nie jest ju Ň NULL

...

}

Algorytm dodawania w ħ zła w sposób rekurencyjny wykonuje si ħ si ħ od korzenia w stron ħ li Ļ ci, poruszaj Ģ c si ħ w lewo b Ģ d Ņ w

prawo w zale Ň no Ļ ci od wyniku porównania z napotkanymi w ħ złami. W momencie dotarcia do jednego z li Ļ ci nast ħ puje ostatnie

porównanie warto Ļ ci, po czym nowy w ħ zeł staje si ħ lewym lub prawym synem w ħ zła, który do tego czasu był li Ļ ciem. Zło Ň ono Ļę

czasowa algorytmu DodajWezel jest rz ħ du O(h) , gdzie h jest wysoko Ļ ci Ģ drzewa. Dopiero teraz wprowadzamy poj ħ cie wysoko Ļ ci

– oznacza ona odległo Ļę korzenia (w sensie liczby kraw ħ dzi) od najbardziej oddalonego li Ļ cia drzewa.

Warto w tym miejscu pokaza ę na rysunkach, w jaki sposób dodawany w ħ zeł w ħ druje w od korzenia w stron ħ li Ļ ci w poszukiwaniu

odpowiedniego miejsca dla siebie.

2008-04-18 15:21

Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne

Przykładowo, chcemy wczyta ę ci Ģ g liczb 5, 3, 8, 2, 6, 4, 9, 1, 7, które s Ģ warto Ļ ciami zapisywanymi w w ħ złach. Po utworzeniu

drzewa BST z liczb 5, 3, 8, 2, 6, 4, 9 prezentujemy poni Ň ej dodanie w ħ zła o warto Ļ ci 1:

Z kolei w nast ħ pnym (ostatnim) kroku dodawany jest w ħ zeł o warto Ļ ci 7:

Skoro wiemy ju Ň , w jaki sposób tworzy si ħ drzewo BST, warto by było pozna ę korzy Ļ ci płyn Ģ ce z u Ň ywania takiej struktury

danych. Jedna z nich zawarta jest w procedurach wy Ļ wietlania drzewa BST. Otó Ň omawiane drzewo mo Ň na wy Ļ wietli ę na 3

główne sposoby:

w kolejno Ļ ci inorder : najpierw lewe poddrzewo, potem w ħ zeł, a nast ħ pnie prawe poddrzewo

w kolejno Ļ ci preorder : najpierw w ħ zeł, potem lewe poddrzewo, a nast ħ pnie prawe poddrzewo

w kolejno Ļ ci postorder : najpierw lewe poddrzewo, potem prawe poddrzewo, a na samy ko ı cu w ħ zeł

Powy Ň sze sposoby tak naprawd ħ dotycz Ģ metod przechodzenia przez drzewo i kolejno Ļ ci odwiedzania jego wierzchołków – przy

okazji „odwiedzin” mo Ň emy wy Ļ wietli ę zawarto Ļę tego w ħ zła.

Co ciekawe, jeden z tych sposobów zwiedzania wierzchołków daje w rezultacie wy Ļ wietlanie zawarto Ļ ci w ħ złów w kolejno Ļ ci

posortowanej (rosn Ģ cej). Chodzi konkretnie o metod ħ inorder .

void WyswietlDrzewo (Twezel *wezel) {

// porz Ģ dek inorder

if (wezel != NULL) {

WyswietlDrzewo (wezel->Lewy); // lewe poddrzewo

cout << wezel->Dane << " " ; // w ħ zeł

WyswietlDrzewo (wezel->Prawy); // prawe poddrzewo

}

Odnosz Ģ c si ħ do naszego przykładowego drzewa, liczby zapisane w w ħ złach zostan Ģ wy Ļ wietlone w kolejno Ļ ci: 1, 2, 3, 4, 5, 6, 7,

8, 9.

2008-04-18 15:21

Algorytmy i Struktury danych, wer. C/C++, Lekcja 5: Drzewa binarne

Odczytanie danych w kolejno Ļ ci inorder wymaga rekurencyjnego si ħ gania w pierwszej kolejno Ļ ci do skrajnie lewych w ħ złów

drzewa, nast ħ pnie w razie konieczno Ļ ci cofamy si ħ o jeden poziom, odczytujemy warto Ļę w ħ zła, przechodzimy do jego prawego

syna i ponownie próbujemy pod ĢŇ a ę skrajnie na lewo. Algorytm wykonuje si ħ do momentu odwiedzenia wszystkich w ħ złów

drzewa. Zauwa Ň cie, Ň e warto Ļę w ħ zła jest odczytywana dopiero przy jego drugich "odwiedzinach", jak ju Ň nie mo Ň emy i Ļę dalej

w lewo. Ta kolejno Ļę odczytywania elementów wynika z kolejno Ļ ci rekurencyjnych wywoła ı w procedurze powy Ň ej i mo Ň ecie

prze Ļ ledzi ę j Ģ na poni Ň szym rysunku, gdzie czerwon Ģ lini Ģ zaznaczona została droga poruszania si ħ wzdłu Ň drzewa w trakcie tych

wywoła ı . Zielone kółeczka oznaczaj Ģ miejsca odczytu w ħ złów, czerwone numerki przy nich to numer kolejny odczytywanego

w ħ zła.

Mamy wi ħ c prosty sposób sortowania danych:

wpisa ę je do drzewa BST, a nast ħ pnie odczyta ę w kolejno Ļ ci inorder.

Mo Ň ecie to teraz dokładnie prze Ļ ledzi ę na ró Ň nych przykładach drzew, korzystaj Ģ c ze specjalnie napisanego w tym celu apletu -

wejdziecie do niego klikaj Ģ c w poni Ň szy obrazek. Autor tego ciekawego apletu przygotował go dla Was w postaci tradycyjnego

drzewa, rosn Ģ cego od dołu do góry - ale zauwa Ň cie, Ň e spełnia ono nadal wszystkie warunki drzewa BST, warto Ļ ci w lewym

poddrzewie s Ģ mniejsze ni Ň w prawym itd. Tradycyjne drzewo binarne (rosn Ģ ce do dołu) mo Ň na z niego otrzyma ę przez odbicie

lustrzane wzgl ħ dem poziomej linii u podnó Ň a drzewa, nie za Ļ przez obrót.

Dla porównania przedstawimy równie Ň kod programu oraz schemat rysunkowy dla metod preorder oraz postorder.

2008-04-18 15:21

Algorytmy i struktury danych - 05. Drzewa binarne.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: