1 STRUKTURY DANYCH

2 DRZEWA BINARNE

3 PEŁNE DRZEWO BINARNE T ilość węzłów = 15 ( n = 15 ) wysokość = ( hT = 3 ) h = log2n , n - ilość węzłów w pełnym drzewie binarnym n = … + 2h = 2h+1 - 1

4 METODY PRZEGLĄDANIA DRZEWA BINARNEGO* + - a d / * e f b c metoda pre-order (wzdłużna) notacja przedrostkowa metoda in-order ( poprzeczna) notacja powszechnie stosowana metoda post-order (wsteczna ) notacja przyrostkowa

5 * + - a d / * e f b c metoda in-order : a + b/c * d - e * f

6 IMPLEMENTACJA W PASCALUtype wsk= ^wezel; wezel = record lewe: wsk; klucz : integer; prawe: wsk end ; var drzewo : wsk ;

7 ZNAJDOWANIE W DRZEWIE POSZUKIWAŃ BINARNYCH ELEMENTU O PODANYM KLUCZUdrzewo

8 DAJE W WYNIKU LISTĘ POSORTOWANYCH KLUCZY PRZECHOWYWANYCH W WĘZŁACHPRZEGLĄDANIE BST METODĄ "IN-ORDER" DAJE W WYNIKU LISTĘ POSORTOWANYCH KLUCZY PRZECHOWYWANYCH W WĘZŁACH A D E G H K L M N O P T V

9 WSTAWIANIE DO DRZEWA BSTELEMENTU O PODANYM KLUCZU klucz = 21 drzewo

10 PROCEDURA WSTAWIANIA ELEMENTU O KLUCZU Z DO DRZEWA POSZUKIWAŃ BINARNYCH TREE-INSERT (T,z) begin y:= NIL; x:= root(T); {korzeń drzewa T} while x  NIL do y := x; if key(z) < key(x) then x := left(x) else x:= right(x); end; p(z) := y; { p(z) - ojciec węzła z} if y = NIL then root(T) := z else if key(z) < key(y) then left(y) := z else right(y) := z;

11 KOPCE BINARNE

12  ( klucz(v)  klucz(PARENT(v) ) vV(T) v  r 20JAKO PRAWIE PEŁNE DRZEWO BINARNE Tr :  ( klucz(v)  klucz(PARENT(v) ) vV(T) v  r 20 17 15 10 9 12 8 6 2 5  ( klucz(left(v))  klucz(v) and klucz(right(v))  klucz(v) ) vV(T)

13  ( A[i]  A[ PARENT (i) ] )JAKO TABLICA A[ 1..n ] , n > 0  ( A[i]  A[ PARENT (i) ] ) 2  i  n PARENT (i) return  i/2  ; LEFT (i) RIHGT (i) return 2*i; return 2*i +1;

14 OPERACJE NA KOPCACH BINARNYCHBUILD-HEAP EXTRACT -MAX INSERT

15 TWORZENIE KOPCA BINARNEGOBUILD-HEAP(A,n); begin hsize(A) := n; for i:= n/2 downto 1 do HEAPIFY (A, i ); end;

16 PRZYWRACANIE WŁASNOŚCI KOPCA BINARNEGOHEAPIFY (A, hsize,i) ; begin lewy := 2*i; prawy := 2*i+1; if lewy <= hsize then naj := indeks elementu większego spośród elementów: A[lewy], A[i]; if prawy <= hsize elementów: A[prawy], A[naj] if naj <> i then zamień A[i] z A[naj]; HEAPIFY (A, naj) end;

17 HEAP-EXTRACT-MAX (A, hsize )begin if hsize < 1 then error; max := A[1]; A[1] := A[hsize]; hsize := hsize - 1; HEAPIFY (A, 1); return max; end;

18 HEAP-INSERT (A, klucz, hsize);begin hsize := hsize + 1; i := hsize; while i > 1 and A[PARENT(i)] < klucz do begin A[i] := A[PARENT(i)] ; i:= PARENT(i); end; A[i] := klucz;

19 HEAPSORT (A, n); begin hsize := n; BUILD-HEAP (A);SORTOWANIE PRZEZ KOPCOWANIE HEAPSORT (A, n); begin hsize := n; BUILD-HEAP (A); for i := n downto 2 do zamień A[1] z A[i]; hsize := hsize -1; HEAPIFY (A,1); end;

20 DLA ZBIORÓW ROZŁĄCZNYCHSTRUKTURY DANYCH DLA ZBIORÓW ROZŁĄCZNYCH

21 X = {x1, ..., xn} S = { S1, S2, ..., Sk } - rodzina zbiorów parami rozłącznych, Si  X, i =1,...,k  (wyróżniamy element x  Si - reprezentant zbioru Si ) SiS Oznaczenie : Sx - zbiór z rodziny S o reprezentancie x

22 OPERACJE NA RODZINIE S :MAKE-SET(x) x S1 S2  ...  Sk - tworzy jednoelementowy zbiór zawierający x, którego reprezentantem jest x UNION(x,y) - dodaje do rodziny S zbiór Sz = Sx  Sy , gdzie z jest dowolnym elementem ze zbioru Sx  Sy , usuwa zbiory Sx , Sy z S FIND - SET(x) - znajduje reprezentanta zbioru zawierającego element x

23 PRZYKŁADY ZASTOSOWANIA STRUKTUR DANYCHDLA ZBIORÓW ROZŁĄCZNYCH : rozpoznawanie spójnych składowych w grafie niezorientownym algorytm Kruskala

24 LISTY DRZEWA REPREZENTACJE ZBIORÓW ROZŁĄCZNYCH : MAKE-SET(x) O(1) O(1)UNION(x,y) O(|Sx|) O(1) FIND - SET(x) O(1) O(|Sx|)