Aisd W8

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Aisd W8 as PDF for free.

More details

  • Words: 1,917
  • Pages: 40
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

Related Documents

Aisd W8
November 2019 8
Aisd Statement
June 2020 8
Aisd W02
November 2019 14
Aisd W12
November 2019 28
Aisd W11
November 2019 10
Aisd W7
November 2019 16