1 ALGORYTMY I STRUKTURY DANYCHWYKŁAD 08 Drzewa binarnych poszukiwań Grażyna Mirkowska PJWSTK, semestr zimowy 2002/2003

2 G. Mirkowska, ASD_08 Drzewa, drzewa BSTPlan wykładu Drzewa Podstawowe definicje Implementacja Odwiedzanie wierzchołków drzewa i grafu Porządki Drzewa BST Wyszukiwanie Koszt wyszukiwania Operacja minimum listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

3 G. Mirkowska, ASD_08 Drzewa, drzewa BSTGrafy System relacyjny postaci < V, E>, gdzie V jest dowolnym niepustym zbiorem , a E relacją binarną w V, nazywamy grafem zorientowanym. Zbiór wierzchołków Zbiór krawędzi Definicje Drogą w grafie G = nazywamy ciąg wierzchołków v1, v2,...vk , taki, że (vi, v i+1) E dla i pojęcia: relacja incydencji (sąsiedztwa) wierzcholki incydentne krawędzie incydentne droga zamknięta droga prosta długość drogi cykl graf acykliczny graf spójny Graf niezorientowany Graf spójny Graf acykliczny listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

4 G. Mirkowska, ASD_08 Drzewa, drzewa BSTDrzewo= graf niezorientowany + spójny + acykliczny Niech G= bedzie niezorientowanym grafem. Wtedy nastepujące zdania są równoważne: (1) G jest drzewem, (2) Między dowolnymi dwoma wierzchołkami istnieje dokładnie jedna prosta droga, (3) G jest spójny, ale po usunięciu dowolnej krawędzi otrzymujemy graf niespójny, (4) G jest spójny i ma card(V)-1 krawędzi, (5) G jest acykliczny i ma card(V) -1 krawędzi, (6) G jest acykliczny ale dodanie dowolnej krawędzi prowadzi do grafu z cyklem. Twierdzenie drzewo z korzeniem ojciec-syn przodek,poprzednik-następnik rząd wierzchołka liść twierdzenie o charakteryzacji drzew Drzewo etykietowane drzewa binarne lewe poddrzewo, prawe poddrzewo listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

5 Reprezentacja/implementacja drzewet(v) lewy prawy v Public class node { public etykieta e; public node lewy, prawy ; public node(etykieta e) { this.e = e; lewy = null; prawy = null; } Referencja do lewego poddrzewa Referencja do prawego poddrzewa W zastosowaniu: node root= null; root = New node (a); listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

6 G. Mirkowska, ASD_08 Drzewa, drzewa BSTImplementacja c.d. Public class node { public etykieta e; public node s[ ] ; public node(etykieta e, int k) { this.e = e; s = New node[k]; for (i=0; i } E = et(v) v s1 ... sk Tablica referencji do synów tego wierzchołka listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

7 Chodzenie po drzewie BFSRozważmy następujący program Niech a będzie korzeniem pewnego drzewa binarnego { // q = kolejka q := in(a,q); while not empty(q) do v := first(q); q := out(q); if (not empty(v.lewy)){ q :=in(v.lewy);} if (not empty(e.prawy)){ q := in(v.prawy);} //wypisz v.wartość od} a wartość lewy prawy wszerz 1 2 3 4 5 6 7 8 9 Kolejka 1 2 3 3 4 5 Jedną z najczęściej wykonywanych operacji na drzewie jest przeglądanie wierzchołków drzewa. Można to wrobić na różne sposoby. Przedstawimy 2 metody : odwiedzanie drzewa "w głąb" i odwiedzanie drzewa "wszerz". Te dwie metody stosuje się do dowolnych grafów i w szczególności do dowolnych drzew(tzn do drzew dowolnego rządu. W przypadku drzew binarnych stosuje się 3 metody rekurencyjnego przegladania drzewa : postfix, infix, prefix, zależnie od tego czy korzeń jest odwiedzany przed synami czy po odwiedzeniu synów czy pomiędzy. 4 5 6 7 5 6 7 6 7 7 8 9 Wynik : 8 9 9 listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

8 Chodzenie po drzewie DFSa {// q = stos q := in(a,q); while not empty(q) do v := top(q); q := pop(q); if (not empty(v.lewy)){ q :=push(v.lewy);} if (not empty(v.prawy)){ q := push(v.prawy);} //wypisz v.wartość od} 1 2 3 4 5 6 7 8 9 { q := in(a,q); while not empty(q) do e := first(q); q := out(q); if (not empty(e.lewy){ q :=in(e.lewy);} if (not empty(e.prawy){ q := in(e.prawy);} //wypisz e.wartość od} W głąb Stos: 2 6 7 2 8 9 2 3 2 6 2 8 4 5 1 2 4 Wyniki : 1 3 7 6 9 8 2 5 4 listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

9 G. Mirkowska, ASD_08 Drzewa, drzewa BST1 2 3 4 5 6 7 8 9 Porządki korzeń LD PD Inorder 1. Odwiedź lewe poddrzewo 2. Odwiedź korzeń 3. Odwiedź prawe poddrzewo Preorder 1. Odwiedź korzeń 2. Odwiedź lewe poddrzewo 3. Odwiedź prawe poddrzewo ((4)2(5))1(((8) 6( 9))3(7)) Postorder 1. Odwiedź lewe poddrzewo 2. Odwiedź prawe poddrzewo 3. Odwiedź korzeń listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

10 Drzewo binarnych poszukiwań BSTNiech będzie niepustym, liniowo uporządkowanym zbiorem. Drzewem binarnych poszukiwań nazywamy etykietowane drzewo binarne z wyróżnionym korzeniem D= takie, że et jest funkcją różnowartościową oraz dla każdego wierzchołka v V, (1) jeśli x  LD(v), to et(x) et(v) (2) jeśli x  PD(v), tp et(v)  et(x). Definicja 6 10 8 4 2 5 1 3 7 9 11 7 9 8 5 6 3 Przykład To nie jest BST listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

11 Operacja wyszukiwania w BSTSpecyfikacja Zadanie Zbadać, czy dany element e należy do zbioru etykiet w danym drzewie D. Member(D,e) wttw (xD.V) et(x) = e Rozpoczynając od korzenia, porównujemy etykietę wierzchołka x z wyszukiwanym elementem e. e< x.et x.et< e x.et= e Metoda Znaleziono Szukaj e w lewym poddrzewie x Szukaj e w prawym poddrzewie wierzchołka x listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

12 Algorytm Wyszukiwania{ bool := false; while (not empty(x) and not bool) do if x.e = e then bool := true else if x.e < e then x:= x.prawy else x:= x.lewy fi fi od; return bool; } member : BST ET Bo Lemat Member Jeżeli wartością zmiennej x jest korzeń drzewa D, to algorytm member zatrzymuje się po skończonej liczbie kroków oraz końcowa wartość bool jest równa true wttw, gdy e jest jedną z etykiet drzewa D. listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

13 G. Mirkowska, ASD_08 Drzewa, drzewa BSTPrzykład Szukam 3 Szukam 8.5 6 10 8 4 2 5 1 3 7 9 11 pokaz listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

14 Koszt operacji member Operacja dominująca = porównywanie elementów.W(n) = O(n) Niech n = card(D.V). Ponumerujmy etykiety drzewa liczbami naturalnymi 1,2...n i załóżmy, że prawdopodobieństwo tego, że w korzeniu jest i-ta etykieta (lub po prostu liczba i) wynosi 1/n. Prawdopodobieństwo tego, że korzeniem drzewa jest i A(n) średnia liczba porównań dla znalezienia elementu e. A(n) = Sni=1 1/n (średnia długość ścieżki od korzenia do e o ile etykietą korzenia jest i) listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

15 Cd. Koszt średni wyszukiwaniaŚrednia długość ścieżki do e = i LD PD Prawdopodobieństwo tego, że e jest w lewym poddrzewie Prawdopodobieństwo tego, że e jest w prawym poddrzewie i-1 elem. n-i elem. Można pokazać przez indukcję, że listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST

16 G. Mirkowska, ASD_08 Drzewa, drzewa BSTOperacja minimum w BST Zadanie Znaleźć etykietę o najmniejszej wartości, w zbiorze etykiet danego drzewa D. Zejdź po ścieżce od korzenia do liścia, wybierając zawsze drogę w lewo, o ile to możliwe. min: BST ET Metoda Koszt : public min (node x) { while (not x.lewy= null) { x := x.lewy} return x.e; } W(n) = O(n) A(n) = O(lg n) listopad 2002 G. Mirkowska, ASD_08 Drzewa, drzewa BST