1 Algorytmy i Struktury Danych Drzewa BTS, AVLWykład 5 Prowadzący: dr Paweł Drozda
2 Drzewa Reprezentują dane w sposób hierarchiczny Szerokie zastosowaniebazy danych grafika komputerowa sztuczna inteligencja przetwarzanie tekstu
3 Drzewa korzeń n1 węzeł przodek potomek Poddrzewo n2 n3 n4 n5 n6 n7liść rodzic (ojciec) n8 n9 n10 n11 dzieci (synowie)
4 Własności drzewa(1) Korzeń: węzeł, który nie ma rodzicaLiść: węzeł, który nie ma dzieci Węzeł wewnętrzny: węzeł nie będący liściem Pojedynczy węzeł jest drzewem, korzeniem i liściem Dzieci danego węzła są zarazem jego poddrzewami Drzewo puste: drzewo bez jakichkolwiek węzłów
5 Własności drzewa(2) Ścieżka od n1 do nk: sekwencja n1,n2,n3,...,nk taka że ni jest rodzicem dla ni+1 Długość ścieżka: liczba tworzących ją węzłów – 1 Jeżeli od węzła a do b istnieje ścieżka, to a jest przodkiem b, a b jest potomkiem a Wysokość węzła: długość najdłuższej ścieżki od tego węzła do jego potomków Wysokość drzewa = wysokość korzenia Głębokość węzła: długość ścieżki łączącej go z korzeniem dr Paweł Drozda
6 Drzewo Książka Rozdział 1 Rozdział 2 Rozdział 3 Podrozdział 1.1Punkt 2.1.1 Punkt 2.1.2
7 Drzewo
8 Jak uporządkować drzewo?Czyli w jakiej kolejności odwiedzić wszystkie węzły dokładnie raz uporządkowanie węzłów odwiedzanie węzłów przechodzenie przez drzewo Najważniejsze metody to: preorder inorder postorder
9 Odwiedzanie węzłów W szczególnym przypadku W ogólnym przypadkudla pustego drzewa wynikiem jest pusta lista węzłów dla drzewa złożonego z jednego węzła otrzymamy jednoelementową listę W ogólnym przypadku przechodzimy przez drzewo rekurencyjnie
10 Odwiedzanie węzłów n T1 T2 Tk ... Preorder(T): Inorder(T):Preorder(Tk) Inorder(T): Inorder(T1) Inorder(T2) Inorder(Tk) Postorder(T): Postorder(T1) Postorder(T2) Postorder(Tk) n T1 T2 Tk ...
11 Przykład 1 2 3 4 7 6 5 10 9 8 Preorder: 1, 2, 3, 5, 8, 9, 6, 10, 4, 7 Inorder: 2, 1, 8, 5, 9, 3, 10, 6, 7, 4 Postorder: 2, 8, 9, 5, 10, 6, 3, 7, 4, 1
12 Wyrażenia arytmetyczne(a+b)*(a-c) Liść przybiera wartość „operand” Węzeł wewnętrzny przybiera wartość „operator” n1 n2 n3 n4 n5 n7 n6 * + - b a c n1=n2*n3=(a+b)*(a-c) n2=a+b n3=a-c Preorder: *+ab-ac (not. prefiksowa) Postorder: ab+ac-* (ONP) Inorder: a+b*a-c (not. infiksowa)
13 Operacje RODZIC(T,n) – w drzewie T zwróć węzeł-rodzica węzła nLEWY_SYN(T,n) – w drzewie T zwróć skrajny lewy węzeł-dziecko węzła n NASTĘPNY_BRAT(T,n) – w drzewie T zwróć węzeł mający tego samego rodzica co n i położony bezpośrednio na prawo od n WARTOŚĆ(T,n) – w drzewie T przyporządkuj węzłowi n pewną wartość KORZEŃ(T) – zwraca węzeł-korzeń drzewa T DODAJ_DZIECKO(T,n) – w drzewie T dodaje węzeł-dziecko do węzła n. Jeżeli n ma wartość NULL to utworzony zostaje korzeń drzewa. Zwraca nowo utworzony węzeł USUŃ_WĘZEŁ(T,n) – jeżeli n jest liściem to zostaje usunięty z drzewa T, w przeciwnym wypadku wynik jest nieokreślony
14 Implementacja drzewa Węzeł wartość LISTA dzieci rodzic wartość
15 Drzewo binarne Każdy rodzic może mieć co najwyżej 2 dziecilewe poddrzewo prawe poddrzewo n1 n2 n3 n4 n5 n7 n6
16 Kodowanie Huffmana Własność przedrostka:Znak prawd. kod a 0.12 000 b 0.4 11 c .15 01 d .08 001 e .25 10 Własność przedrostka: kod danego znaku nie jest początkiem kodu innego znaku np.: = = cad Średnia ilość bitów potrzebna do zakodowania znaku
17 Kodowanie Huffmana a d c e b 1 Znak prawd. kod a 0.12 000 b 0.4 11 c1 Znak prawd. kod a 0.12 000 b 0.4 11 c .15 01 d .08 001 e .25 10
18 Algorytm Huffmana 1) Weź 2 najrzadsze znaki2) Do kodu pierwszego dopisz 0 3) Do kodu drugiego dopisz 1 4) Zastąp je nowym znakniem z prawd. = sumie 2 znaków 5) Powtórz kroki 1-4 dopóki nie pozostanie 1 znak
19 Algorytm Huffmana 1 0,6 0,35 0,2 b (0,4) e (0,25) c (0,15) a (0,12)d (0,08) 0.4* * * * *4 = 2.15
20 Drzewo binarne Drzewo regularne: każdy wierzchołek ma 0 lub 2 synówDrzewo zrównoważone: na wszystkich poziomach poza ostatnim i przedostatnim każdy wierzchołek ma 2 synów Drzewo uporządkowane: węzły w drzewie są ułożone kolejno od lewej strony
21 Drzewa poszukiwań binarnychBST (binary search tree) struktura danych umożliwiająca operacje FIND, MIN, MAX, INSERT, DELETE czas wykonania tych operacji: w pełnym drzewie – Θ(lgn) w drzewie zdegenerowanym – Θ(n)
22 Węzeł drzewa BST Rekord Własność drzewa BST: key left right pdla każdego y = LEWY_POTOMEK(BST,x) KEY(BST,y) ≤ KEY(BST,x) dla każdego y = PRAWY_POTOMEK(BST,x) KEY(BST,x) ≤ KEY(BST,y)
23 2,3,5,6,7,8 6 2 3 7 3 2 5 8 7 6 8 5
24 Wyszukiwanie w BST Odwiedzamy O(h) węzłów SZUKAJ_BST_IT(n,k):while (n.key<>k AND n<>NULL) do begin if (k<=n.key) then n:=n.left; else n:=n.right; end return n; SZUKAJ_BST(n,k): if (n.key=k OR n=NULL) then return n; if (k<=n.key) then SZUKAJ_BST(n.left,k); else SZUKAJ_BST(n.right,k); Odwiedzamy O(h) węzłów
25 Wartości ekstremalne w BSTminimum SZUKAJ_MIN(n): while(n.left<>NULL) do n:=n.left; return n; maksimum SZUKAJ_MAX(n): while(n.right<>NULL) do n:=n.right; return n; Poprawność procedur wynika z własności drzewa BST
26 Wstawianie nowych elementówTREE_INSERT(T,z): x:=ROOT(T); y:=x.p; while (x<>NULL) do begin y:=x; if (z.key
27 Usuwanie węzła 3 przypadki:węzeł n nie ma dzieci if (n.p.left = n) then n.p.left = null; if (n.p.right = n) then n.p.right = null; węzeł n ma 1 dziecko if (n.left <> null) then dz = n.left; else dz = n.right; if (n.p.left = n) then n.p.left = dz; else n.p.right = dz; węzeł n ma 2 dzieci nast = SZUKAJ_MIN(n.right); if (n.p.left = n) then n.p.left = nast; else n.p.right = nast;
28 Drzewo AVL Def: uporządkowane drzewo BST jest drzewem AVL, jeżeli dla każdego węzła różnica wysokości jego poddrzew wynosi co najwyżej 1 W najgorszym wypadku wysokość drzewa AVL 1.44log(n+2) 6 5 9 12 8 2 3 6 5 9 12 8
29 Wstawianie elementów dl AVLWstaw jak do BST Jeśli drzewo utraciło własność AVL to należy je wyważyć wykonując rotację w lewo/w prawo pojedyncza/podwójna
30 Pojedyncza rotacja – w prawo1 2 -1 1 Drzewo AVL jest drzewem AVL po wykonaniu rotacji Uporządkowane drzewo AVL jest uporządkowanym drzewem AVL po wykonaniu rotacji
31 Podwójna rotacja – w prawo1 2 ±1 -1 ±1
32 Przykład: 4, 5, 7, 2, 1, 3, 6
33 AVL - usuwanie Usuwamy węzeł (BST), a następnie przywracamy równowagę od węzła do korzenia
34 Porównanie