Aisd W7

Algorytmy i struktury danych Drzewa AVL

6

0

+1

5 0

9

2 0

8

0

12

0

Drzewa AVL


Drzewo AVL (1962 – Adelson-Velskii, Landis) 








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 0 w( x) = h(LD) − h(PD) +1

5

Drzewo AVL 0

9

2 0

Algorytmy i struktury danych

8

0

12

0

2

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; -1 H Drzewo BST jest drzewem AVL  dla kaŜdego wierzchołka x: w(x) ∈{-1, 0, +1}

+2

C

M

+1

0 A

-1 J

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

0 K

Algorytmy i struktury danych

3

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

Algorytmy i struktury danych

4

Operacje na drzewie AVL 0 6

Drzewo wyjściowe Dodajemy węzeł z wartością 3

+1

0 5

+1

9

0

6

0

2

0

8

Jak przywrócić równowagę?

12

+2 5

9

-1 0

drzewo z nowym węzłem

0

0

2

Algorytmy i struktury danych

0

8

12

3 5

Operacje na drzewie AVL




Usuwanie: 

polega na wyszukaniu elementu w drzewie a potem jego usunięciu (patrz BST)



moŜe zajść potrzeba przywrócenia zrównowaŜonej struktury drzewa (wymagana rotacja);

Algorytmy i struktury danych

6

Operacje na drzewie AVL

Rotacja: 

zmiana konfiguracji węzłów;



celem jest przywrócenie struktury drzewa AVL;



wyróŜniamy rotacje: 

lewe i prawe,



pojedyncze i podwójne;

Algorytmy i struktury danych

7

Operacje na drzewie AVL


Usuwanie – niespełniony warunek AVL Usunięcie elementu z drzewa BST moŜe zmniejszyć wysokość poddrzewa (wymagana rotacja)!



6

-2

-1

0 5

9

W jaki sposób zrównowaŜyć 0 otrzymane drzewo?

0

0 8 Algorytmy i struktury danych

6

12

0 8

0 9

0 12 8

Operacje na drzewie AVL W jaki sposób zrównowaŜyć otrzymane drzewo?

-2

1

6

-1

9

8

0 9

12

-1 6

0

12

6

1

0 0 8

Algorytmy i struktury danych

0 12

0

8

9

0

9

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

β Algorytmy i struktury danych

γ

x

y γ

α

β 10

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

γ

x

α Algorytmy i struktury danych

β

α

y

β

γ 11

Operacje na drzewie AVL


Rotacja: 

Lewa i prawa rotacja działają symetrycznie LeftRotate(T, y)

y

x α

y β

Algorytmy i struktury danych

RightRotate(T, x)

γ

γ

x α

β

12

Operacje na drzewie AVL  Przykład – rotacja pojedyncza 7 wokół 5  Wynik: warunek AVL spełniony

3

3 5 -2

1 2

4

1

7

7 5

2

6

9

4

8

y

y

x

A

C B

Algorytmy i struktury danych

9 6

8

x

0

C

A

B 13

Operacje na drzewie AVL  Przykład – rotacja pojedyncza 8 wokół 5  Wynik: warunek AVL niespełniony

3

3

5 -2

1 2

4

1

8 6

x

9

4 y

7

+2

9

5

2

y

6 7

x

Co dalej?

A

C B

Algorytmy i struktury danych

8

C

A

B 14

Operacje na drzewie AVL  Przykład – rotacja podwójna  Wynik: warunek AVL spełniony -1 5

-1 5

+1 3 2

9 4

+1 3 +2

-1 11 -1

7

1

6

8

10

1

12

2

9 3

10

09 0

5

11

2

13 12

Algorytmy i struktury danych

14

11 -1 8

Rotacja 2 wokół 3

Co teraz?

-1

7 6

1

13

-2 5 0

2

1 14

7 3

6

-1

10 8

13 12

0 14

Po rotacji 9 wokół 5 15

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

Algorytmy i struktury danych

16

1. Wstawienie węzła do prawego poddrzewa prawego następnika  Korekta: rotacja lewa węzła A wokół B

0

B -2 A -1

Z Y

X

A

0 B X Z

Y

h h+1 h

h+1

h

h

!

*! Algorytmy i struktury danych

17

2. Wstawienie węzła do lewego poddrzewa lewego następnika  Korekta: rotacja prawa węzła A wokół B

B

A

0 B 0

+1 A X

+2

Z

X

Y

Y

Z

h

h

h h+1 h+1

h

*

* Algorytmy i struktury danych

18

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

+2

Y h

C -1

U B +1

X

B

0

A 0

-1 A

h

Stan po pierwszej rotacji?

Z h-1

X

Y

h

Z

U

h-1 h

h

h

*! Algorytmy i struktury danych

19

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 Stan po pierwszej rotacji?

C -2

-1 B h

Z h-1

X

U

Y h

B

+1 C

A +1

U

0

0 A

Z

Y

X

h

h

h-1 h

h

*

* * Algorytmy i struktury danych

20

RównowaŜenie drzewa AVL po wstawieniu węzła Przykład P

P

P

-1

-2

-2 Q

Q

Q

0

+1

+1

h

h

h

R -1 h

h

h+1

Wstawienie nowego węzła do lewego poddrzewa węzła Q Algorytmy i struktury danych

h

h

h-1

h

21

RównowaŜenie drzewa AVL po wstawieniu węzła Przykład (cd.) P -2

-2

0

P

R

P R

Q

+1

-2

+1

Q 0

h

h

Q

R

0

-1

h

h-1 h

h

h-1

h

h-1 h

h

h

Podwójna rotacja węzła R: wokół węzła Q i wokół węzła P Algorytmy i struktury danych

22

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;

Algorytmy i struktury danych

23

RównowaŜenie drzewa AVL po usunięciu węzła Przykład P

P

-1

Q

-2

0

Q

Q

-1

P 0

-1

h

h-1

h-1

h

h-1 h

h-1

h-1

h

Przypadek 1 (pojedyncza rotacja) Algorytmy i struktury danych

24

RównowaŜenie drzewa AVL po usunięciu węzła Przykład P

P

-1

Q

-2

+1

Q

Q

0

P -1

0

h

h-1

h

h

h

h

h

h-1

h

Przypadek 2 (pojedyncza rotacja) Algorytmy i struktury danych

25

RównowaŜenie drzewa AVL po usunięciu węzła Przykład P

P

-1

R

-2

0

Q

Q

+1

P 0

+1

h

Q -1

h-1 R

R +1

h-2

+1 h-1

h-1

h-1 Algorytmy i struktury danych

h-2

h-1

h-1

h-1

Przypadek 3 (podwójna rotacja)

26

RównowaŜenie drzewa AVL po usunięciu węzła Przykład P

P

-1

R

-2

0

Q

Q

+1

P +1

+1

h

Q 0

h-1 R

R -1

-1

h-2

h-1 h-2

h-1

h-2 h-1

Algorytmy i struktury danych

h-1

h-1

h-1

Przypadek 4 (podwójna rotacja) h-1 27

Operacje na drzewie AVL  Koszt operacji usunięcia węzła w drzewie AVL 

Rotacje działają w czasie O(1)



Zmieniają się tylko wartości 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?

n0=1 n h= n h-1 + n h-2 +1 MoŜna udowodnić, Ŝe: log2(n+1) ≤ h ≤ 2 log2n

h LD

h-1

PD



Liczba rotacji wynosi zatem co najwyŜej 2 log2n;



ZłoŜoność obliczeniowa równowaŜenia po usunięciu węzła: Θ(log2n)

Algorytmy i struktury danych

h-2

28

Algorytmy i struktury danych

29