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