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