Algorytmy i struktury danych

Wykład 7: Drzewa AVL

Poj

ę

cie drzewa AVL

Rotacje

Podstawowe operacje na drzewie AVL

6

5

9

12

8

2

0

0

0

0

0

+1

2

Algorytmy i struktury danych

Drzewa AVL

Drzewo AVL (1962 –

A

delson-

V

elskij,

L

andis)



Drzewo AVL jest rozwini

ę

ciem drzewa BST

(z zachowaniem wszystkich jego własno

ś

ci);



Dla ka

ż

dego wierzchołka w drzewie AVL wysoko

ś

ci jego dwóch

poddrzew (lewego i prawego) o korzeniu w tym wierzchołku ró

ż

ni

ą

si

ę

co najwy

ż

ej o 1;



W

ę

zeł oprócz pól danych oraz lewego i prawego wska

ź

nika ma te

ż

pole

opisuj

ą

ce ró

ż

nic

ę

wysoko

ś

ci lewego i prawego poddrzewa;

Z definicji wynika,

ż

e to pole mo

ż

e mie

ć

warto

ść

ze zbioru {-1, 0, 1};

6

5

9

12

8

2

0

0

0

0

0

+1

Drzewo AVL

w( x) = h(LD)

−−−−

h(PD)

3

Algorytmy i struktury danych

Obliczanie wag wierzchołków drzewa AVL

Dla ka

ż

dego wierzchołka drzewa x współczynnik zrównowa

ż

enia w(x)

ma posta

ć

w( x) = h(LD)

−−−−

h(PD),

gdzie LD i PD s

ą

odpowiednio lewym i prawym poddrzewem

o korzeniu x;

H

C

M

J

A

-1

+1

-1

Drzewo BST jest drzewem AVL









dla każdego wierzchołka x:

w(x)

∈

∈

∈

∈

{-1, 0, +1}

+2

W jakiej kolejności dodawano poszczególne wartości do

drzewa?

0

K

0

4

Algorytmy i struktury danych

Operacje na drzewie AVL

Wyszukiwanie:



poniewa

ż

drzewo AVL jest te

ż

drzewem BST, ta operacja

wygl

ą

da tak jak dla drzew BST;

Wstawianie:



polega na wyszukaniu miejsca w drzewie, a nast

ę

pnie

wstawieniu elementu (jak w BST);



poniewa

ż

podczas operacji struktura drzewa zmienia si

ę

i mo

ż

e nie zosta

ć

zachowany warunek AVL (dotycz

ą

cy

ró

ż

nicy w wysoko

ś

ci poddrzew), trzeba t

ę

struktur

ę

przywróci

ć

(wymagana tzw. rotacja);

5

Algorytmy i struktury danych

Operacje na drzewie AVL

6

5

9

12

8

2

0

+1

0

0

Drzewo wyjściowe

+1

+2

-1

0

0

0

0

0

6

5

9

12

8

2

3

0

Drzewo z nowym węzłem

Jak przywrócić równowagę?

Dodajemy węzeł z wartością 3

6

Algorytmy i struktury danych

Operacje na drzewie AVL

Usuwanie:



polega na wyszukaniu elementu w drzewie a potem jego
usuni

ę

ciu (patrz BST)



mo

ż

e zaj

ść

potrzeba przywrócenia równowagi drzewa

(wymagana rotacja);

7

Algorytmy i struktury danych

Operacje na drzewie AVL

Rotacja:



zmiana konfiguracji w

ę

złów;



cel: przywrócenie struktury drzewa AVL;



podstawowa własno

ść

: po rotacji drzewo jest nadal

drzewem BST;



rodzaje rotacji:



lewe i prawe,



pojedyncze i podwójne;

8

Algorytmy i struktury danych

Operacje na drzewie AVL

Usuwanie – niespełniony warunek AVL



Usuni

ę

cie elementu z drzewa BST mo

ż

e zmniejszy

ć

wysoko

ść

poddrzewa (wymagana rotacja)

6

5

9

12

8

-1

0

0

0

6

9

12

8

0

-2

0

0

0

W jaki sposób zrównoważyć

otrzymane drzewo?

9

Algorytmy i struktury danych

Operacje na drzewie AVL

6

9

12

8

0

-2

0

0

W jaki sposób zrównoważyć

otrzymane drzewo?

8

0

9

12

6

1

-1

0

9

0

8

12

6

-1

0

1

10

Algorytmy i struktury danych

Operacje na drzewie AVL

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 nast

ę

pnikiem, a lewy

nast

ę

pnik w

ę

zła

y

zostaje prawym nast

ę

pnikiem w

ę

zła

x

;



Jej wykonanie ma sens, je

ż

eli prawy nast

ę

pnik w

ę

zła

y

nie jest

NULL;

x

y

αααα

ββββ

γγγγ

y

x

αααα

ββββ

γγγγ

Left_Rotate(x, y)

11

Algorytmy i struktury danych

Operacje na drzewie AVL

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 nast

ę

pnikiem, a

prawy nast

ę

pnik w

ę

zła

x

zostaje lewym nast

ę

pnikiem w

ę

zła

y

;



Jej wykonanie ma sens, je

ż

eli lewy syn w

ę

zła

x

nie jest NULL;

y

x

αααα

ββββ

γγγγ

x

y

αααα

ββββ

γγγγ

Right_Rotate(y, x)

12

Algorytmy i struktury danych

Operacje na drzewie AVL

Rotacja:



Lewa i prawa rotacja działaj

ą

symetrycznie

x

αααα

y

γγγγ

ββββ

y

x

γγγγ

ββββ

αααα

LeftRotate(x, y)

RightRotate(y, x)

13

Algorytmy i struktury danych

Operacje na drzewie AVL

Przykład – rotacja pojedyncza 7 wokół 5

Wynik: warunek AVL spełniony

3

5

4

7

6

9

2

1

8

3

5

4

7

6

9

2

1

8

C

B

A

y

x

C

B

A

y

x

-2

0

-2

-1

14

Algorytmy i struktury danych

Operacje na drzewie AVL

Przykład – rotacja pojedyncza 8 wokół 5

Wynik: warunek AVL niespełniony

3

5

4

8

6

9

2

1

7

3

5

4

8

6

9

2

1

7

C

B

A

y

x

C

B

A

y

x

-2

+2

Co dalej?

-2

-2

15

Algorytmy i struktury danych

Operacje na drzewie AVL

3

2

1

5

+1

-1

+2

Rotacja 2 wokół 3

2

1

3

5

0

-2

11

9

7

6

8

10

13

12

14

-1

-1

Po rotacji 9 wokół 5

5

2

7

9

0

0

13

11

10

6

8

12

14

-1

0

1

3

Co teraz?

3

2

4

1

5

+1

-1

11

9

7

6

8

10

13

12

14

-1

-1

Przykład – rotacja podwójna

Wynik: warunek AVL spełniony

16

Algorytmy i struktury danych

Operacje na drzewie AVL

Wstawianie

Po wstawieniu elementu do drzewa AVL na ogół trzeba
wykona

ć

1 rotacj

ę

pojedyncz

ą

lub podwójn

ą

w celu jego

zrównowa

ż

enia;

Przypadki charakterystyczne:

1.

wstawienie w

ę

zła do prawego poddrzewa prawego nast

ę

pnika

2.

wstawienie w

ę

zła do lewego poddrzewa lewego nast

ę

pnika

3.

wstawienie w

ę

zła do lewego poddrzewa prawego nast

ę

pnika

4.

wstawienie w

ę

zła do prawego poddrzewa lewego nast

ę

pnika

17

Algorytmy i struktury danych

1. Wstawienie węzła do prawego poddrzewa prawego następnika

Korekta: rotacja lewa w

ę

zła A wokół B

-2

A

B

Z

X

*

Y

*

B

A

Z

X

*

Y

0

0

h

h+1

h

h

h

h+1

-1

18

Algorytmy i struktury danych

2. Wstawienie węzła do lewego poddrzewa lewego następnika

Korekta: rotacja prawa w

ę

zła A wokół B

A

B

Z

X

*

Y

+2

+1

B

A

Z

X

*

Y

0

0

*

h

h+1

h

h+1

h

h

19

Algorytmy i struktury danych

3. Wstawienie węzła do lewego poddrzewa prawego następnika

Korekta: rotacja lewa w

ę

zła B wokół A i prawa w

ę

zła B wokół C

C

B

U

X

Z

0

-1

A

Y

0

A

C

U

X

Y

*

+2

-1

B

Z

+1

!

h

h

h-1

h

h

h

h

h-1

Stan po pierwszej rotacji?

20

Algorytmy i struktury danych

4. Wstawienie węzła do prawego poddrzewa lewego następnika

Korekta: Rotacja prawa w

ę

zła B wokół A i lewa w

ę

zła B wokół C

C

B

U

X

Z

0

A

Y

*

0

A

C

U

X

Y

*

-2

B

Z

-1

*

+1

h

h-1

h

h

h

h

h

h-1

+1

Stan po pierwszej rotacji?

21

Algorytmy i struktury danych

Równoważenie drzewa AVL po wstawieniu węzła

Wstawienie nowego węzła do lewego

poddrzewa węzła Q

-1

h

0

P

Q

h

h

-2

+1

P

Q

h

h

h+1

Przykład

-2

+1

P

Q

h

h

-1

R

h-1

h

4

Przypadek?

22

Algorytmy i struktury danych

Równoważenie drzewa AVL po wstawieniu węzła

Przypadek 3: Podwójna rotacja węzła R: wokół węzła Q i wokół węzła P

P

-2

-2

R

h

h

h-1

h

0

Q

h

h

R

0

0

Q

h-1

+1

P

h

Przykład (cd.)

P

-2

+1

Q

h

h

-1

R

h-1

h

23

Algorytmy i struktury danych

Operacje na drzewie AVL

Usuwanie



Po usuni

ę

ciu elementu z drzewa AVL mo

ż

e si

ę

zdarzy

ć

,

ż

e w celu jego zrównowa

ż

enia nale

ż

y wykona

ć

tyle rotacji,

ile jest poziomów w drzewie

24

Algorytmy i struktury danych

Równoważenie drzewa AVL po usunięciu węzła

-1

h

-1

h-1

h

-2

h-1

-1

h-1

h

P

Q

P

Przypadek 1 (pojedyncza rotacja)

Q

Q

0

0

h-1

h

P

h-1

Przykład

25

Algorytmy i struktury danych

Równoważenie drzewa AVL po usunięciu węzła

Przypadek 2 (pojedyncza rotacja)

-1

h

0

h

h

P

Q

-2

h-1

0

h

h

P

Q

Q

+1

-1

h-1

h

P

h

Przykład

26

Algorytmy i struktury danych

Równoważenie drzewa AVL po usunięciu węzła

Przypadek 3 (podwójna rotacja)

-1

h

+1

P

Q

+1

R

h-1

-2

h-1

+1

P

Q

h-1

h-2

+1

R

h-1

R

0

P

Q

-1

h-2

h-1

0

h-1

h-1

Przykład

Jaka?

27

Algorytmy i struktury danych

Równoważenie drzewa AVL po usunięciu węzła

h-2

h-1

Przypadek 4 (podwójna rotacja)

-1

h

+1

P

Q

-1

R

h-1

-2

h-1

+1

P

Q

-1

R

h-1

h-2

h-1

R

0

P

Q

0

h-1

+1

h-1

h-2

h-1

Przykład

Jaka?

28

Algorytmy i struktury danych

Operacje na drzewie AVL

Koszt operacji usuni

ę

cia w

ę

zła z drzewa AVL



Rotacje działaj

ą

w czasie O(1) - zmieniaj

ą

si

ę

tylko warto

ś

ci wybranych

wska

ź

ników; pozostałe pola w

ę

złów nie s

ą

zmieniane;



Jaka jest minimalna liczba wierzchołków n w drzewie AVL o wysoko

ś

ci h?



Liczba rotacji wynosi zatem co najwy

ż

ej 2 lg n;



Zło

ż

ono

ść

obliczeniowa równowa

ż

enia drzewa AVL po usuni

ę

ciu w

ę

zła:

Θ

Θ

Θ

Θ

(lg n)

n

1

=1

n

h

= n

h-1

+ n

h-2

+1

Można udowodnić, że:

lg (n+1)

≤≤≤≤

h

≤≤≤≤

2 lg n

LD

PD

h

h-1

h-2

29

Algorytmy i struktury danych