Aisd W07

Algorytmy i struktury danych Temat: Metody równoważenia drzew BST

Techniki równoważenia drzew BST a)

K

B

B

b)

c) D

B

K

P

D

M

K R

P

D

M Różne drzewa BST zawierające te same dane Algorytmy i struktury danych

M

R

P R 2

Techniki równoważenia drzew BST Ile maksymalnie węzłów może mieć drzewo binarne w zależności od wysokości h?

dla np. n=10 000

h =  log2 (n + 1) = =  log2 10001  =  13,3 = 14

Algorytmy i struktury danych

Wysokość

Węzłów na poziom

Węzłów w drzewie

1

20=1

1= 21-1

2

21=2

3= 22-1

3

22=4

7= 23-1

4

23=8

15= 24-1

...

...

...

11

210=1024

2047= 2111

14

213=8192

...

...

16383= 214 ...-1

h

2h-1

n= 2h-1

...

...

...

...

3

Techniki równoważenia drzew BST

Sposoby równoważenia drzewa BST: 1. Uporządkowanie danych przed tworzeniem drzewa (wybór na korzeń elementu ze środka listy danych) 2. Stałe poprawianie drzewa w miarę wstawiania węzłów (np. z wykorzystaniem rotacji; przykład: drzewa AVL)

Algorytmy i struktury danych

4

Techniki równoważenia drzew BST Tworzenie drzewa po uprzednim posortowaniu jego elementów:  przed utworzeniem drzewa dane porządkowane są w tablicy;  na korzeń drzewa wybierany jest element bliski wartości środkowej; element ten wyznacza podział tablicy na lewą i prawą podtablicę;  lewy następnik korzenia: środek lewej podtablicy; prawy następnik korzenia: środek prawej podtablicy;  otrzymane drzewo jest dobrze zrównoważone ( liczba elementów na drodze od korzenia do dowolnego liścia jest rzędu log2 n );

Algorytmy i struktury danych

5

Techniki równoważenia drzew BST Tworzenie drzewa po uprzednim posortowaniu jego elementów (idea algorytmu): void balance(T data[ ], int first, int last) { if (first<=last) { int middle=(first+last)/2; insert(data[middle]); balance(data, first, middle-1); balance(data, middle+1, last); } } Algorytmy i struktury danych

6

Techniki równoważenia drzew BST Przykład użycia funkcji balance

0 0 0

Strumień danych

5

1

9

8

7

0

2

3

4

6

Strumień uporządkowany

0

1

2

3

4

5

6

7

8

9

5

6

7

8

9

1 1 1

2 2 2

3 3 3

4 4 4

5 5

6 6

7 7

8 8

4

9

1

9

0

7 2

3 0

1

2

3

4

6

9

5 6

Algorytmy i struktury danych

8

5

7

8

9 7

Techniki równoważenia drzew BST Metoda poprawiania struktury drzewa:  zasadnicza wada poprzedniej metody: przed utworzeniem drzewa dane należało posortować;  inny sposób (bez sortowania): rozłożyć niezrównoważone drzewo i złożyć je ponownie;  stosunkowo efektywny może okazać się algorytm DSW (C.Day, Q.Stout, B.Warren):  przekształcenie drzewa w winorośl;  przekształcenie winorośli w drzewo zrównoważone (z wykorzystaniem rotacji).

Algorytmy i struktury danych

8

Techniki równoważenia drzew BST Przekształcenie drzewa w winorośl: UtwórzWinorośl (root, n ) { tmp=root; while ( tmp != 0 ) if ( tmp ma lewy następnik) { obróć następnik w prawo wokół tmp; ustaw tmp na następnik, który stał się poprzednikiem; } else ustaw tmp na jego prawy następnik; }

Algorytmy i struktury danych

9

Techniki równoważenia drzew BST Przykład przekształcenia drzewa w winorośl 5

5 10

10 20 15

10

30

15

25

tmp

20

20 25

23

23

25 40

23

30 28

23

15

15 20

30

40 tmp

10

10

20

28

5

5

tmp 15

25 23

5

25 40 tmp

30

28 28

Algorytmy i struktury danych

28 30 40 tmp 40 10

Techniki równoważenia drzew BST

Złożoność tworzenia winorośli  Przypadek optymistyczny (drzewo jest już winoroślą): pętla while wykonuje się n razy, nie są wykonywane żadne rotacje (tylko n instrukcji podstawienia); zatem T(n)=O(n)  Przypadek pesymistyczny (korzeń nie ma prawego dziecka): pętla while wykonuje się 2n – 1 razy, w tym wykonywanych jest n-1 rotacji; zatem: T(n)=O(n)

Algorytmy i struktury danych

11

Techniki równoważenia drzew BST Tworzenie drzewa zrównoważonego m = 2  log2 ( n +1 ) − 1; UtwórzDrzewoZrównoważone( n ) { wykonaj n-m rotacji w lewo, zaczynając od korzenia winorośli; while (m>1) { m=m/2; wykonaj m rotacji w lewo, zaczynając od korzenia winorośli; } }

Algorytmy i struktury danych

12

Techniki równoważenia drzew BST Przykład tworzenia drzewa zrównoważonego 5 10

10

20 20

5

15 20

15

23

5

28

40 10 5

30

28

40

30

25

30

28

25

Algorytmy i struktury danych

15 23

25

23

winorośl: n=9 m=23-1=7 n-m=9-7=2

25

10

20

30 23 28

40

15 drzewo zrównoważone

40 13

Techniki równoważenia drzew BST Złożoność przekształcania winorośli w drzewo zrównoważone  liczba rotacji w ramach pętli while:

( 2  log2 ( n +1 )  −1 − 1 ) + ... + 15 + 7 + 3 + 1 = =

 log 2 ( n +1 )  −1

∑( 2 i =1

i

− 1 ) = n −  log 2 ( n + 1 )

q n −1 Sn = a1 q −1

 łączna liczba rotacji:

n − m + ( n −  log 2 ( n + 1 ) ) =

= 2 n − m −  log 2 ( n + 1 )

Algorytmy i struktury danych

T(n)=O(n) 14

Techniki równoważenia drzew BST

Złożoność równoważenia drzewa •

Przekształcenie drzewa niezrównoważonego w winorośl: O(n)

•

Przekształcenie winorośli w drzewo zrównoważone: O(n) T(n) = max { O(n), O(n) } = O(n)

Algorytmy i struktury danych

15

Techniki równoważenia drzew BST Metoda poprawiania drzewa w miarę wstawiania węzłów Idea: elementy (dane), które wykorzystywane są najczęściej przesuwane są w górę drzewa (blisko korzenia) •

Drzewa samonaprawiające się

•

Ukosowanie (ang. splaying) drzewa

Algorytmy i struktury danych

16

Techniki równoważenia drzew BST Drzewa samonaprawiające się Idea: Przy sięganiu do elementu następuje korekta struktury drzewa poprzez: a) pojedynczą rotację (wokół poprzednika) b) przesunięcie elementu do korzenia

Algorytmy i struktury danych

17

Rotacja ◆

Lewa rotacja (lub „rotacja w lewo”) węzła y wokół węzła x ✦

Polega na obrocie węzła y wokół wyróżnionego węzła x przeciwnie do ruchu wskazówek zegara;

✦

W wyniku rotacji węzeł y staje się nowym korzeniem poddrzewa, węzeł x zostaje jego lewym synem, a lewy syn węzła y zostaje prawym synem węzła x;

✦

Można ją wykonać, jeżeli prawy syn węzła y nie jest NULL;

x α

y x

y β

Algorytmy i struktury danych

γ

α

γ β 18

Rotacja ◆

Prawa rotacja (lub „rotacja w prawo”) węzła x wokół węzła y: ✦

Polega na obrocie węzła x wokół wyróżnionego węzła y zgodnie z ruchem wskazówek zegara;

✦

W wyniku rotacji węzeł x staje się nowym korzeniem poddrzewa, węzeł y zostaje jego prawym synem, a prawy syn węzła x zostaje lewym synem węzła y;

✦

Można ją wykonać, jeżeli lewy syn węzła x nie jest NULL;

y

x α

x

γ β

Algorytmy i struktury danych

α

y β

γ 19

Techniki równoważenia drzew BST Ilustracja idei: sięgnięcie do węzła D P F D A

P Q

H

D A

E

Q F

E

H

a) rotacja w prawo węzła R

Algorytmy i struktury danych

20

Techniki równoważenia drzew BST Ilustracja idei: sięgnięcie do węzła R P F D A

Q H

E

D

P D A

Q

A F

F E

P

H

E

Q H

a) przesunięcie węzła R do korzenia (metodą podwójnej rotacji w prawo) Algorytmy i struktury danych

21

Techniki równoważenia drzew BST Ukosowanie (1985) 

Jest to modyfikacja strategii naprawiania drzewa poprzez przenoszenie do korzenia.



Korekta struktury drzewa następuje poprzez stosowanie pojedynczych rotacji parami, w kolejności zależnej od powiązania dziecka, rodzica i rodzica rodzica.



Wyróżnia się trzy przypadki (dostęp do węzła R, którego rodzicem jest Q, którego z kolei rodzicem jest P: •

Rodzic Q węzła R jest korzeniem.

•

Układ jednorodny: węzeł R jest lewym dzieckiem Q, zaś Q jest lewym dzieckiem P (lub kiedy w obu relacjach chodzi o prawe dziecko).

•

Układ niejednorodny: węzeł R jest lewym dzieckiem Q, zaś Q jest prawym dzieckiem P (lub kiedy R jest prawym dzieckiem, natomiast Q lewym).

Algorytmy i struktury danych

22

Techniki równoważenia drzew BST Ukosowanie – przykład (po sięgnięciu do węzła B) B

Q B A

R C

A

Q C

R

Przypadek 1. Rodzic węzła R jest korzeniem (rotacja w prawo węzła R) Algorytmy i struktury danych

23

Techniki równoważenia drzew BST Ukosowanie – przykład (po sięgnięciu do węzła F) P

K

F

F

Q A

L

F A

K

P G

L

A Q

K P

G

G

L

Q

Przypadek 2. Układ jednorodny (rotacja w prawo węzła K oraz rotacja w prawo węzła F) Algorytmy i struktury danych

24

Techniki równoważenia drzew BST Ukosowanie – przykład (po sięgnięciu do węzła N) P K A

P Q

N

N M

K O

A

N K

Q O

A

P M

O

Q

M

Przypadek 2. Układ niejednorodny (rotacja w lewo węzła N oraz rotacja w prawo węzła N) Algorytmy i struktury danych

25

Techniki równoważenia drzew BST Idea algorytmu ukosowania (przenoszenia węzła do korzenia) Ukosowanie ( P, Q, R ) { while (R nie jest korzeniem) if (rodzic R jest korzeniem) wykonaj pojedyncze ukosowanie: rotację R wokół jego rodzica; else if (R jest ze swoimi przodkami w układzie jednorodnym) wykonaj ukosowanie jednorodne: najpierw rotuj Q wokół P, potem R wokół Q; else // R jest ze swoimi przodkami w układzie niejednorodnym wykonaj ukosowanie niejednorodne: najpierw rotuj R wokół Q, potem R wokół P; } Algorytmy i struktury danych

26

Techniki równoważenia drzew BST Przykład ukosowania (po dostępie do węzła E) P N K I

A

Q

N

O L

J

E

P

F

E

E Q

A I

O

A

F

I

J

P K J

K

F

N

L

O

Q

L

Stan po drugiej parze rotacji

Stan po pierwszej parze rotacji Algorytmy i struktury danych

27

Techniki równoważenia drzew BST Przykład ukosowania c.d. (dostęp do węzła K) E

K

A

N

E

I F

P K J

O

N

A Q

I F

L J

P O

Q

L

Algorytmy i struktury danych

28

Algorytmy i struktury danych Temat: Zastosowania drzew binarnych  Drzewa wyrażeń arytmetycznych

Binarne drzewa wyrażeń  Jednym z zastosowań drzew binarnych jest jednoznaczny zapis wyrażeń arytmetycznych lub logicznych (bez używania nawiasów);  Drzewa wyrażeń konstruuje się, wykorzystując następujące założenia: ◆ każdy liść zawiera operand (argument) wyrażenia; ◆ każdy węzeł wewnętrzny zawiera operator np.: *, /, +, - itp.; ◆ wyrażenie powstaje w wyniku realizacji procedury przechodzenia drzewa jedną z trzech metod: ✦ ✦ ✦

bezpośredniej (inorder), z wyprzedzeniem (preorder), z opóźnieniem (postorder).

Algorytmy i struktury danych

30

Binarne drzewa wyrażeń Przykład drzewa wyrażeń + –

5

2

* 3

Algorytmy i struktury danych

4

Wynik przejścia drzewa metodą: ✦bezpośrednią (inorder): = -5 2–3*4+5 ✦z wyprzedzeniem = -5 (preorder): +–2*34= 5 -5 ✦z opóźnieniem (postorder): 234*–5+

31

Binarne drzewa wyrażeń Mnemotechniczna metoda przechodzenia drzewa:  wyruszamy z korzenia, okrążając drzewo w kierunku przeciwnym do ruchu wskazówek zegara;  staramy się być jak najbliżej mijanych węzłów (niektóre węzły odwiedzamy wielokrotnie);  chcą otrzymać listę węzłów odpowiadającą kolejności:  preorder, należy wypisywać każdy węzeł przy pierwszym jego odwiedzeniu;  postorder, należy wypisywać każdy węzeł przy ostatnim jego odwiedzeniu;  inorder, należy wypisywać każdy węzeł przy pierwszym jego odwiedzeniu jeżeli jest liściem, natomiast przy drugim odwiedzeniu, jeżeli jest węzłem wewnętrznym. Algorytmy i struktury danych

32

Binarne drzewa wyrażeń Mnemotechniczna metoda przechodzenia drzewa: Wynik przejścia drzewa:

+

+ – 2 – * 3 * 4 * – + 5 + –

5  Kolejność preorder: + – 2 * 3 4 5

2

* 3

 Kolejność postorder: 2 3 4 * – 5 +

4

 Kolejność inorder:

2–3 *4 + 5

UWAGA Niezależnie od metody każdy liść odwiedzany jest dokładnie jeden raz (i w tej samej kolejności) Algorytmy i struktury danych

33

Binarne drzewa wyrażeń Z uwagi na sposób przechodzenia drzewa wyróżniamy notację wyrażeń:  przedrostkową (prefiksową), np. + – 2 * 3 4 5  wzrostkową (infiksową), np. 2 – 3 * 4 + 5  przyrostkową (postfiksową), znanej jako notacja polska odwrotna, np. 2 3 4 * – 5 +

Algorytmy i struktury danych

34

Binarne drzewa wyrażeń Przykłady drzew wyrażeń Zapis wyrażenia metodą: ✦wzrostkową (inorder):

*

2 – 3 * 4 + 5 = -9 – 2

+ 3

4

✦przedrostkową

5

(preorder): * – 2 3 + 4 5 = -9 ✦przyrostkową

(postorder): 2 3 – 4 5 + * = -9

Algorytmy i struktury danych

35

Binarne drzewa wyrażeń Przykłady drzew wyrażeń Zapis wyrażenia metodą: ✦wzrostkową (inorder):

– 2

+ * 3

Algorytmy i struktury danych

5 4

2 – 3 * 4 + 5 = -15 ✦przedrostkową (preorder): – 2 + * 3 4 5 = -15 ✦przyrostkową (postorder): 2 3 4 * 5 + – = -15

36

Algorytmy i struktury danych

37