Algorytmy i struktury danych

Temat: Metody równowa

ż

enia drzew BST

2

Algorytmy i struktury danych

Techniki równoważenia drzew BST

K

B

P

R

M

D

B

M

K

P

R

D

Różne drzewa BST zawierające te same dane

a)

b)

c)

B

M

D

K

R

P

3

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Ile maksymalnie w

ę

złów mo

ż

e mie

ć

drzewo binarne w zale

ż

no

ś

ci

od wysoko

ś

ci h?

...

...

...

n= 2

h

-1

2

h-1

h

...

...

...

16383= 2

14

-1

2

13

=8192

14

...

2047= 2

11

-1

2

10

=1024

11

...

...

...

15= 2

4

-1

2

3

=8

4

7= 2

3

-1

2

2

=4

3

3= 2

2

-1

2

1

=2

2

1= 2

1

-1

2

0

=1

1

W

ę

złów

w drzewie

W

ę

złów na

poziomie h

Wysoko

ść

dla np. n=10 000







 



14

3

,

13

10001

log

)

1

(

log

2

2

=

=

=

=

+

≤

n

h

4

Algorytmy i struktury danych

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,
drzewa czerwono-czarne))

5

Algorytmy i struktury danych

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 log

2

n );

6

Algorytmy i struktury danych

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 mid=(first+last)/2;
insert(data[mid]);
balance(data, first, mid-1);
balance(data, mid+1, last);

}

}

7

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Przykład u

ż

ycia funkcji balance

9

8

7

6

5

4

3

2

1

0

Strumie

ń

uporz

ą

dkowany

6

4

3

2

0

7

8

9

1

5

Strumie

ń

danych

9

8

7

6

5

4

3

2

1

0

9

8

7

6

5

4

3

2

1

0

9

8

7

6

5

4

3

2

1

0

9

8

7

6

5

4

3

2

1

0

4

1

7

8

5

2

0

3

6

9

8

Algorytmy i struktury danych

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.

D

ay, Q.

S

tout, B.

W

arren):

1)

przekształcenie drzewa w winoro

ś

l;

2)

przekształcenie winoro

ś

li w drzewo zrównowa

ż

one

(z wykorzystaniem rotacji).

9

Algorytmy i struktury danych

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ó

ć

lewy nast

ę

pnik w prawo wokół tmp;

ustaw tmp na nast

ę

pnik, który stał si

ę

poprzednikiem;

}

else

ustaw tmp na jego prawy nast

ę

pnik;

}

10

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Przykład przekształcenia drzewa w winoro

ś

l

5

10

20

30

40

15

25

28

23

tmp

5

10

20

30

40

15

25

28

23

tmp

5

10

20

15

tmp

30

40

28

23

25

5

10

20

15

tmp

30

40

28

25

23

5

10

20

15

tmp

28

40

25

23

30

11

Algorytmy i struktury danych

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 nast

ę

pnika):

p

ę

tla while wykonuje si

ę

2n – 1 razy, w tym wykonywanych jest

n – 1 rotacji; zatem: T(n)=O(n)

Pokaż algorytm

12

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Tworzenie drzewa zrównowa

ż

onego

UtwórzDrzewoZrównowa

ż

one( n ) {

wykonaj n-m rotacji w lewo, zaczynaj

ą

c od prawego nast

ę

pnika

korzenia winoro

ś

li;

while (m>1) {

m =



m/2



;

wykonaj m rotacji w lewo, zaczynaj

ą

c od prawego nast

ę

pnika

korzenia winoro

ś

li;

}

}





;

1

2

m

)

1

n

(

log

2

−

=

+

13

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Przykład tworzenia drzewa zrównowa

ż

onego

40

5

15

28

25

23

30

10

20

5

15

10

28

23

20

40

25

30

30

10

15

20

28

23

25

40

5

winorośl: n=9
m=2

3

-1=7

n-m=9-7=2

40

20

23

25

28

10

5

15

30

drzewo zrównoważone

14

Algorytmy i struktury danych

Zło

ż

ono

ść

przekształcania winoro

ś

li w drzewo

zrównowa

ż

one

Liczba rotacji w ramach p

ę

tli while:

Ł

ą

czna liczba rotacji:













)

1

n

(

log

n

)

1

2

(

1

3

7

15

...

)

1

2

(

1

)

1

n

(

log

1

i

2

i

1

)

1

n

(

log

2

2

∑

−

+

=

−

+

+

−

=

−

=

=

+

+

+

+

+

−









)

1

n

(

log

m

n

2

)

)

1

n

(

log

n

(

m

n

2

2

+

−

−

=

=

+

−

+

−

T(n)=O(n)

1

q

1

q

a

S

n

1

n

−

−

=

Pokaż algorytm

15

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Zło

ż

ono

ść

równowa

ż

enia drzewa

T(n) = max { O(n), O(n) } = O(n)

1.

Przekształcenie drzewa niezrównowa

ż

onego w winoro

ś

l: O(n)

2.

Przekształcenie winoro

ś

li w drzewo zrównowa

ż

one: O(n)

16

Algorytmy i struktury danych

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)

1. Drzewa samonaprawiaj

ą

ce si

ę

2. Ukosowanie (ang. splaying) drzewa

17

Algorytmy i struktury danych

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

18

Algorytmy i struktury danych

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

γ

β

y

x

γ

β

α

19

Algorytmy i struktury danych

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;

x

α

y

γ

β

y

x

γ

β

α

20

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Ilustracja idei: si

ę

gni

ę

cie do w

ę

zła D

P

F

E

D

A

H

Q

a) rotacja w prawo w

ę

zła D

P

D

A

F

H

E

Q

21

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Ilustracja idei: si

ę

gni

ę

cie do w

ę

zła R

b) przesuni

ę

cie w

ę

zła D do korzenia

(metod

ą

podwójnej rotacji w prawo)

D

A

Q

F

H

E

P

P

F

E

D

A

H

Q

P

D

A

F

H

E

Q

22

Algorytmy i struktury danych

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:

1.

Rodzic Q w

ę

zła R jest korzeniem.

2.

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).

3.

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).

23

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Ukosowanie – przykład (po si

ę

gni

ę

ciu do w

ę

zła B)

Przypadek 1. Rodzic węzła B jest korzeniem

(rotacja w prawo węzła B)

Q

B

A

C

R

B

A

R

C

Q

24

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Ukosowanie – przykład (po si

ę

gni

ę

ciu do w

ę

zła F)

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

F

A

Q

L

K

P

G

P

K

F

L

Q

G

A

K

F

G

A

P

Q

L

25

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Ukosowanie – przykład (po si

ę

gni

ę

ciu do w

ę

zła N)

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

P

K

A

N

Q

O

M

P

N

K

O

Q

M

A

N

K

M

A

P

Q

O

26

Algorytmy i struktury danych

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;

}

27

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Przykład ukosowania (po dost

ę

pie do w

ę

zła E)

P

N

K

O

E

L

I

A

Q

J

F

P

N

E

O

I

A

Q

F

J

K

L

E

A

P

I

N

F

J

K

L

Q

O

Stan po pierwszej parze rotacji

Stan po drugiej parze rotacji

28

Algorytmy i struktury danych

Techniki równoważenia drzew BST

Przykład ukosowania c.d. (dost

ę

p do w

ę

zła K)

K

E

N

A

I

Q

O

F

J

L

P

E

A

P

I

N

F

J

K

L

Q

O

Algorytmy i struktury danych

Temat:

Zastosowania drzew binarnych

Drzewa wyra

ż

e

ń

arytmetycznych

30

Algorytmy i struktury danych

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).

31

Algorytmy i struktury danych

Przykład drzewa wyrażeń

+

–

5

2

*

3

4

Wynik przej

ś

cia drzewa metod

ą

:



bezpo

ś

redni

ą

(inorder):

2 – 3 * 4 + 5



z wyprzedzeniem (preorder):

+ – 2 * 3 4 5



z opó

ź

nieniem (postorder):

2 3 4 * – 5 +

Binarne drzewa wyrażeń

= -5

= -5

= -5

32

Algorytmy i struktury danych

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.

Binarne drzewa wyrażeń

33

Algorytmy i struktury danych

Mnemotechniczna metoda przechodzenia drzewa:

Binarne drzewa wyrażeń

+

–

5

2

*

3

4

Wynik przej

ś

cia drzewa:

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

Kolejność preorder:

+

–

2 * 3 4 5

Kolejność postorder:

2 3 4 * – 5 +

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)

34

Algorytmy i struktury danych

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 +

35

Algorytmy i struktury danych

Przykłady drzew wyrażeń

Zapis wyra

ż

enia metod

ą

:



wzrostkow

ą

(inorder):

Binarne drzewa wyrażeń

*

–

+

2

3

4

5



przedrostkow

ą

(preorder):



przyrostkow

ą

(postorder):

2 – 3 * 4 + 5

2 3 – 4 5 + *

* – 2 3 + 4 5

= -9

= -9

= -9

36

Algorytmy i struktury danych

Przykłady drzew wyrażeń

Zapis wyra

ż

enia metod

ą

:



wzrostkow

ą

(inorder):

Binarne drzewa wyrażeń

–

2

+

3

4

*

5



przedrostkow

ą

(preorder):



przyrostkow

ą

(postorder):

2 – 3 * 4 + 5

2 3 4 * 5 + –

– 2 + * 3 4 5

= -15

= -15

= -15

37

Algorytmy i struktury danych