Aisd W8

Algorytmy i struktury danych Drzewa częściowo uporządkowane

Drzewa zrównowaŜone







Drzewo (binarne) jest zrównowaŜone, jeŜeli dla kaŜdego węzła wysokości dwóch jego poddrzew (lewego i prawego) róŜnią się co najwyŜej o 1 (własność tzw. drzew AVL) Dla drzewa zrównowaŜonego o liczbie węzłów równej n kaŜda droga od korzenia do któregokolwiek z węzłów ( w tym liści) nie jest dłuŜsza niŜ log2 n

Algorytmy i struktury danych

2

Drzewa zrównowaŜone Przykład zrównowaŜonego drzewa binarnego dane

dane

dane

dane

dane NULL NULL

dane

dane

NULL NULL

NULL NULL

Algorytmy i struktury danych

dane

dane

NULL NULL

NULL NULL

3

Drzewa częściowo uporządkowane


Drzewa częściowo uporządkowane (ang. Partially ordered tree) są to drzewa binarne mające następującą własność: Element przechowywany w węźle musi mieć co najmniej (co najwyŜej) tak duŜą wartość, jak wartości następników tego węzła Własność ta oznacza, Ŝe element w korzeniu dowolnego poddrzewa jest zawsze największym (najmniejszym) elementem tego poddrzewa

Algorytmy i struktury danych

4

Drzewa częściowo uporządkowane Przykład drzewa częściowo uporządkowanego 5

4

5 NULL

3

2

1

NULL NULL

NULL NULL

NULL NULL

Algorytmy i struktury danych

5

Drzewa częściowo uporządkowane


Drzewo częściowo uporządkowane jest zrównowaŜone, jeŜeli jest drzewem zrównowaŜonym. 9

6

5

7

4 NULL

4

3

0

NULL NULL

NULL NULL

NULL NULL

Algorytmy i struktury danych

2

1

NULL NULL

NULL NULL

6

Drzewa częściowo uporządkowane


Kopiec (sterta, stóg) 





Przykładem drzewa częściowo uporzadkowanego moŜe być tzw. kopiec (sterta, stóg), ang. heap Drzewo binarne jest kopcem jeŜeli wartości przechowywane w następnikach kaŜdego węzła są mniejsze od wartości w danym węźle (tzw. kopiec maksymalny) lub wartości przechowywane w następnikach kaŜdego węzła są większe od wartości w danym węźle (tzw. kopiec minimalny) Drzewo jest zrównowaŜone, a wszystkie liście najniŜszego poziomu znajdują się na jego skrajnych, lewych pozycjach

Algorytmy i struktury danych

7

Drzewa częściowo uporządkowane Przykłady kopców

10 8

8

2

7

3

6

Kopiec binarny maksymalny

Algorytmy i struktury danych

12

20

10

15

Kopiec binarny minimalny

8

Drzewa częściowo uporządkowane

 Kopiec moŜna zaimplementować bazując na tablicy jednowymiarowej (wektorze) o długości n  Elementy są umieszczane w drzewie w kolejnych węzłach od góry do dołu i od lewej strony do prawej  Uwaga: kaŜdy kopiec jest tablicą (ale nie kaŜda tablica jest kopcem)

Algorytmy i struktury danych

9

Drzewa częściowo uporządkowane  Cechy charakterystyczne tablicy A implementującej kopiec:  Korzeń znajduje się w A[ 0 ]  Po korzeniu zapisujemy w tablicy kolejne poziomy;  Zatem: lewy następnik korzenia znajduje się w A[ 1 ], prawy następnik korzenia – w A[ 2 ];  Ogólnie: lewy następnik węzła zapisanego w A[ i ] znajduje się w A[ 2i +1], prawy następnik – w A[ 2i+2 ] (jeŜeli następniki istnieją);

Algorytmy i struktury danych

10

Drzewa częściowo uporządkowane – reprezentacja tablicowa A[0]

A[1]

A[3]

A[0]

Algorytmy i struktury danych

A[1]

A[2]

A[4]

A[2]

A[5]

A[3]

A[6]

A[4]

A[5]

A[6]

11

Drzewa częściowo uporządkowane

A[k/2]

 następniki k-tego węzła mają indeksy równe: 2k +1 lewy następnik 2k +2 prawy następnik

A[k]

 węzeł nadrzędny ma indeks równy k / 2 (dzielenie całkowitoliczbowe) A[2k+1]

Algorytmy i struktury danych

A[2k+2]

12

Drzewa częściowo uporządkowane A[0]

tablica A:

10

A[1]

A[2] 8

7

2

3

A[3]

A[4]

0

1

2

3

4

5

10

8

7

2

3

6

6

A[5]

Zachodzi:

A[k ] ≥ A[2k + 1] oraz

A[k ] ≥ A[2k + 2] Algorytmy i struktury danych

13

Drzewa częściowo uporządkowane

Przekształcanie tablicy w kopiec (metodą wstępującą R. Floyda (1964)): for (i=indeks ostatniego węzła-nie liścia; i>=0; i--) odtwórz warunki kopca dla drzewa, którego korzeniem jest data[ i ] wywołując funkcję MoveDown(data, i, n-1);

Prototyp funkcji MoveDown: void MoveDown(T data[ ], int first, int last);

Algorytmy i struktury danych

14

Drzewa częściowo uporządkowane Idea działania funkcji MoveDown (tzw. przesiewanie) 9

Krok 1

25

20 17

7

19

14

Algorytmy i struktury danych

16

18

5

15

10

11

6

5

15

Drzewa częściowo uporządkowane

25

Krok 2

9

20 17

7

19

14

Algorytmy i struktury danych

16

18

5

15

10

11

6

5

16

Drzewa częściowo uporządkowane

25

Krok 3

18

20 17

7

19

14

Algorytmy i struktury danych

16

9

5

15

10

11

6

5

17

Drzewa częściowo uporządkowane

25

Krok 3 (drzewo jest kopcem)

18

20 17

7

19

14

Algorytmy i struktury danych

16

15

5

9

10

11

6

5

18

Drzewa częściowo uporządkowane void MoveDown(T data[ ], int first, int last) { int largest = 2* first +1; while (largest <= last) { if (largest < last && data[largest] < data[largest+1] ) largest ++ ; /* first ma dwa następniki: lewy w 2*first+1 oraz prawy w 2*first+2, przy czym prawy jest większy od lewego */ if (data[first] < data[largest]) { /* jeśli trzeba zamień większy następnik z jego poprzednikiem */ swap(data[first], data[largest]); first=largest; largest=2*firt+1; } else largest=last+1; } } Algorytmy i struktury danych

19

Drzewa częściowo uporządkowane Analiza złoŜoności algorytmu przekształcania tablicy w kopiec (algorytmem wstępującym Floyda)  Rozpatrujemy drzewo binarne o n węzłach i wysokości h  Zachodzi: n=2h−1 czyli h = lg (n+1)  Liczba węzłów na ostatnim (h-tym) poziomie drzewa nh = 2h-1  Związek pomiędzy liczba węzłów na i-tym od dołu poziomie drzewa a liczbą węzłów drzewa n, i=0, 1, 2, ..., h-1 lg ( n +1) −i −1

nh − i = 2 =2 lg nh−i = lg 2lg( n+1)−i−1 = lg(n + 1) − i − 1 = n +1 i +1 = lg(n + 1) − lg 2 = lg i+1 2 h −i −1

Algorytmy i struktury danych

20

Drzewa częściowo uporządkowane Analiza złoŜoności algorytmu przekształcania tablicy w kopiec (algorytmem wstępującym Floyda)  Mamy

lg nh−i  czyli

nh −i

n +1 = lg i+1 2

n +1 = i+1 2

 np. dla i=1 (przedostatni poziom);

n +1 nh−1 = 4 Algorytmy i struktury danych

dla i=2 (drugi od dołu poziom)

nh − 2

n +1 = 8 21

Drzewa częściowo uporządkowane Analiza złoŜoności algorytmu przekształcania tablicy w kopiec (algorytmem wstępującym Floyda)  W najgorszym razie funkcja MoveDown przenosi dane z przedostatniego poziomu zawierającego (n+1)/4 węzłów o jeden poziom w dół, przeprowadzając (n+1)/4 zamiany  Dane z drugiego od końca poziomu, który ma (n+1)/8 węzłów przenoszone są o dwa poziomy w dół, co oznacza 2 (n+1)/8 przesunięć itd. aŜ do korzenia  Korzeń moŜe być (w najgorszym razie) przeniesiony o log2(n+1) − 1= log2[(n+1)/2] poziomy  Łączna liczba przesunięć: log 2 ( n +1 )

∑ i =2

log 2 ( n +1 ) n +1 i −1 ( i −1) = ( n + 1) ∑ = i i 2 2 i =2

= ( n + 1 )[

log 2 ( n +1 )

∑ i =2

Algorytmy i struktury danych

i log2 ( n +1 ) 1 − ∑ ] = ( n + 1 )(1,5 − 0 ,5 ) = n + 1 = O( n ) i i 2 2 i =2 22

Drzewa częściowo uporządkowane Przykład Przekształcanie tablicy A=[ 2 8 6 1 10 15 3 12 11] w kopiec metodą wstępującą R.Floyda 2

6

8 1

12

10

15

3

11 2

Algorytmy i struktury danych

8

6

1

10

15

3

12

11 23

Drzewa częściowo uporządkowane

2

Krok 1

6

8 1

12

10

15

ostatni węzeł nie będący liściem: i = n/2-1 = 9/2 -1 = 3

11 2

Algorytmy i struktury danych

3

8

6

1

10

15

3

12

11 24

Drzewa częściowo uporządkowane

2

Krok 2

6

8 12

1

10

15

ostatni węzeł nie będący liściem: i = n/2 -2 = 9/2 -2 = 2

11 2

Algorytmy i struktury danych

3

8

6

12

10

15

3

1

11 25

Drzewa częściowo uporządkowane

2

Krok 3

15

8 12

1

10

6

ostatni węzeł nie będący liściem: i = n/2 -3 = 9/2 -3= 1

11 2

Algorytmy i struktury danych

3

8

15

12

10

6

3

1

11 26

Drzewa częściowo uporządkowane

2

Krok 4

15

12 8

1

10

6

3

11 2

Algorytmy i struktury danych

12

15

8

10

6

3

1

11 27

Drzewa częściowo uporządkowane

2

Krok 5

15

12 11

1

10

6

3

8 2

Algorytmy i struktury danych

12

15

11

10

6

3

1

8 28

Drzewa częściowo uporządkowane

15

Krok 6

2

12 11

1

10

6

3

8 15

Algorytmy i struktury danych

12

2

11

10

6

3

1

8 29

Drzewa częściowo uporządkowane

15

Kopiec

6

12 11

1

10

2

3

8 15

Algorytmy i struktury danych

12

6

11

10

2

3

1

8 30

Algorytmy i struktury danych Temat: Drzewa losowe - drzepce

Losowo skonstruowane drzewa BST

 Losowe drzewo BST o n wartościach (kluczach) – drzewo BST, które powstaje z drzewa pustego w wyniku wstawienia wartości (kluczy) w losowej kolejności, przy załoŜeniu, Ŝe kaŜda z n! permutacji tych wartości jest jednakowo prawdopodobna;  MoŜna pokazać, Ŝe oczekiwana wysokość losowego drzewa BST o n kluczach wynosi log2n, tzn. E[H] = log2n;  Losowe drzewo BST ma tendencję bycia zrównowaŜonym;

Algorytmy i struktury danych

32

Drzepce  Co zrobić, jeŜeli wszystkich wstawianych elementów nie mamy od razu?  Drzepiec (ang. treap) – drzewo BST, w którym porządek wstawiania elementów określany jest w pewien specjalny sposób;  W kaŜdym węźle drzepca, oprócz pola wartości występuje pole priorytet, którego wartością jest losowo określana liczba, niezaleŜnie dla kaŜdego węzła (przy załoŜeniu, Ŝe wszystkie wartości i wszystkie priorytety są róŜne);  Elementy (węzły) w drzepcu są uporządkowane w taki sposób, Ŝe wartości (klucze) spełniają kryteria drzewa BST, natomiast priorytety spełniają własność kopca minimalnego, tj. z najmniejszym priorytetem w korzeniu;  Drzepiec jest zatem połączeniem drzewa BST i kopca (stąd nazwa: drzewo BST + kopiec) Algorytmy i struktury danych

33

Drzepce

 Pomocne jest, aby myśleć o drzepcach w następujący sposób:  załóŜmy, Ŝe wstawiamy do drzepca węzły x1, x2, ..., xn wraz ze związanymi z nimi wartościami (kluczami);  aby otrzymać drzepiec wstawiamy te węzły w kolejności wyznaczonej przez ich (losowo ustalone) priorytety, tzn. xi jest wstawiany przed xj, jeŜeli priorytet( xi ) < priorytet( xj )

Algorytmy i struktury danych

34

Drzepce wartość węzłą (klucz)

priorytet

G/4

H/5

B G// 47

A /10

K / 65

E / 23

I / 73

Przykład drzepca

Algorytmy i struktury danych

35

Drzepce Idea algorytmu wstawiania węzła do drzepca

G/4

C / 25

H/5

B G// 47 A /10

G/4

K / 65

E / 23 I / 73

Algorytmy i struktury danych

H/5

B G// 47 A /10

K / 65

E / 23 C / 25

I / 73

36

Drzepce Idea algorytmu wstawiania węzła do drzepca

G/4

G/4 D/9

A /10

K / 65

E / 23 I / 73

C / 25 D/9

Algorytmy i struktury danych

H/5

B G// 47

H/5

B G// 47

A /10

K / 65

E / 23 D/9

I / 73

C / 25

37

Drzepce Idea algorytmu wstawiania węzła do drzepca

G/4

G/4 H/5

B G// 47 A /10

K / 65

E / 23 D/9

I / 73

H/5

B G// 47 A /10

K / 65

D /9 C /25

E /23

I / 73

C / 25

Algorytmy i struktury danych

38

Drzepce Idea algorytmu wstawiania węzła do drzepca

F/2

G/4 H/5

B G// 47 A /10

F/2

K /65

D/9 C /25

E /23

I /73

... ?

G/4

B G// 47

A /10

H/5

D/9 C /25

E /23

K /65 I /73

Algorytmy i struktury danych

39

Algorytmy i struktury danych

40