ALGORYTMY
I STRUKTURY DANYCH
Temat 6:
Drzewa BST, AVL
Drzewa BST, AVL
Wykładowca: dr inż. Zbigniew TARAPATA
dr inż. Zbigniew TARAPATA
e-mail: [e-mail]
http://www.tarapata.strefa.pl/p_algorytmy_i_struktury_danych/
Współautorami wykładu są: A.Najgebauer, D.Pierzchała
Wykład : Algorytmy przetwarzania struktur
drzewiastych
drzewa poszukiwań binarnych;
podstawowe operacje na drzewach BST;
drzewa AVL;
algorytmy rotacji;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
2
Przypomnienie  struktura drzewiasta
DrzewiastÄ… strukturÄ… danych nazywamy strukturÄ™
danych S=(D, R, e), w której relacja porządkująca N
opisuje kolejne, rekurencyjne powiązania pomiędzy
danymi elementarnymi drzewa, tworzÄ…cymi kolejne
 poddrzewa .
Przykład struktury drzewiastej
Uniwersytet
Wydział Wydział Wydział Wydział
Instytut Instytut Instytut Instytut
Instytut
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
3
Element struktury drzewiastej
Element drzewa zawiera:
Dane elementarne,
Realizację relacji następstwa  dowiązania do
następników;
Dane
Korzeń
DowiÄ…zanie na
DowiÄ…zanie na
lewego potomka
prawego potomka
Przodek Potomek
Liść
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
4
Drzewa poszukiwań binarnych
Wysokość węzła x:
Największa liczba węzłów na drodze prostej z węzła
x do liści (bez węzła x);
Inaczej jest to liczba krawędzi na tej drodze;
Wysokość drzewa:
Wysokość korzenia;
Wpływa na złożoność operacji na drzewie;
Głębokość węzła x:
Największa liczba węzłów na drodze prostej z
korzenia do węzła x (bez korzenia);
Inaczej jest to liczba krawędzi na tej drodze;
Głębokość drzewa:
Głębokość najodleglejszego liścia;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
5
Drzewa poszukiwań binarnych
Drzewo binarne:
Każdy węzeł ma co najwyżej dwóch potomków;
Zupełne drzewo binarne (dwójkowe):
Każdy węzeł, z wyjątkiem liści, ma dokładnie dwóch
potomków niepustych;
Drzewo poszukiwań binarnych (BST):
Dla każdego węzła (nie liścia) wszystkie wartości
przechowywane w lewym poddrzewie sÄ… mniejsze od jego
wartości oraz przeciwnie dla drzewa prawego;
Drzewo binarne zrównoważone:
Dla każdego węzła różnica wysokości obu poddrzew
wynosi co najwyżej 1;
Drzewo doskonale zrównoważone:
Wszystkie liście znajdują się na jednym poziomie;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
6
Drzewa poszukiwań binarnych
Ograniczenia w drzewie poszukiwań binarnych (BST):
Podstawowe operacje realizują się szybko, dzięki
symetrycznemu porzÄ…dkowi;
Jeśli jednak będziemy do drzewa wstawiać elementy np.
posortowane, drzewo rozrośnie się w jedną ze stron (może
w skrajnym przypadku być zdegenerowane do listy
powiÄ…zanej);
Wtedy złożoność przeszukiwania (a tym samym
wszystkich innych operacji) jest liniowa: O(n);
Aby równoważyć drzewa BST wymyślono ich różne
odmiany, np. drzewa AVL, czerwono-czarne, splay;
Dzięki zrównoważeniu nie stracimy podstawowej zalety
struktury drzewiastej: złożoności obliczeniowej mniejszej
niż liniowa;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
7
Drzewa poszukiwań binarnych
Lemat 1
Liczba węzłów w drzewie doskonale zrównoważonym
wynosi: 2h+1-1;
Dowód (przez indukcję)
Przyjmijmy, że dowolny poziom mają numer l, l=1..h;
Liczba wszystkich węzłów wynosi:
h
l
-1
"2 = 2h+1
l=0
Przez indukcjÄ™:
0
l
-1
"2 = 20 =1 Ô! 20+1 = 2 -1 =1
dla 0:
l=0
H +1 H
l l +1 +1 +1 +2
-1+ -1
"2 = "2 + 2H = 2H 2H = 2H
a dla H+1:
l=0 l =0
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
8
Drzewa AVL
Drzewo AVL (1962  Adelson-Velskii, Landis)
Drzewo AVL jest rozwinięciem drzewa BST;
Dla każdego wierzchołka w drzewie AVL wysokości
dwóch poddrzew różnią się o co najwyżej 1 poziom;
Węzeł oprócz pól danych, lewego i prawego
dowiązania ma też pole opisujące różnicę wysokości
lewego i prawego poddrzewa;
z definicji wynika, że to pole może mieć wartość z podzbioru
{-1, 0, 1};
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
9
Operacje na drzewie AVL
Wyszukanie:
drzewo AVL jest też drzewem BST, zatem operacja
wyglÄ…da tak jak dla drzew BST;
Wstawianie:
polega na wyszukaniu miejsca w drzewie a potem
wstawieniu elementu (jak w BST);
ponieważ podczas operacji struktura drzewa zmienia
się i może nie zostać zachowany warunek AVL (o
różnicy w wysokości poddrzew), trzeba tę strukturę
przywrócić;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
10
Operacje na drzewie AVL
Usuwanie:
polega na wyszukaniu elementu w drzewie a potem jego
usunięciu (patrz BST)
podczas operacji należy utrzymać zrównoważoną strukturę
drzewa (j.w.);
Rotacja:
zmiana konfiguracji węzłów;
celem jest przywrócenie struktury drzewa AVL;
wyróżniamy rotacje:
lewe i prawe,
pojedyncze i podwójne;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
11
Operacje na drzewie AVL
Obliczanie wag wierzchołków:
Dla każdego wierzchołka drzewa:
w( x) = h(LD) - h(PD),
gdzie LD i PD sÄ… odpowiednio lewym i prawym
poddrzewem drzewa o korzeniu w x;
0
6
Pamiętaj!
+1
5
0
9
Drzewo BST jest drzewem AVL

2
0
12
dla każdego wierzchołka w:
8
0
0
w(x) "{-1, 0, +1}
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
12
Operacje na drzewie AVL
Wstawianie  niespełniony warunek AVL:
Wstawienie nowego elementu do drzewa BST może
zwiększyć wysokość poddrzewa (wymagana rotacja);
+1
6
0
+2 0
5
+1 0
9
-1
2
0
12
0 0
0
8
0
3
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
13
Operacje na drzewie AVL
Usuwanie  niespełniony warunek AVL:
Usunięcie elementu z drzewa BST może zmniejszyć
wysokość poddrzewa (wymagana rotacja)!
-2
-1
6
0
5
9
12
8
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
14
Operacje na drzewie AVL
Rotacja:
Lewa rotacja (lub  w lewo ):
Polega na obrocie 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;
y x
x a
c y
b
c
a
b
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
15
Operacje na drzewie AVL
Rotacja:
Prawa rotacja (lub  w prawo ):
Działa symetrycznie do lewej rotacji;
Rotację rozpoczynamy od węzła z wagą równą ą2;
Kierunek zależy od znaku;
Przy wstawianiu elementu do drzewa AVL musimy
wykonać co najwyżej 1 rotację;
Przy usuwaniu elementu z AVL może się zdarzyć, że
będziemy musieli wykonać tyle rotacji ile jest poziomów
w drzewie;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
16
Operacje na drzewie AVL
Rotacja lewa wokół B:
0
-2
B A
B
0
-1
A
Z
X
Z
Y Y
X
!
!
*
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
17
Operacje na drzewie AVL
Rotacja prawa wokół B:
+2 0
B A
B
0
+1
A
Z
X
Z
Y Y
X
!
!
*
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
18
Operacje na drzewie AVL
Rotacja lewa wokół A i prawa wokół C:
+2 0
C B
A C
0 -1
-1
A
U
B
+1
U
X X Y
Z
Y
Z
!
*
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
19
Operacje na drzewie AVL
Rotacja prawa wokół A i lewa wokół C:
0
-2
C B
C A
0
+1
A
U
-1
B
U
X Y X
Z
Y
Z
!
!
*
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
20
Operacje na drzewie AVL
Przykład  rotacja pojedyncza: AVL spełniony
3 3
1 5 1 7
2 4 7 2 5 9
6 9
4 6 8
8
y
x
y
x
A C
B C A B
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
21
Operacje na drzewie AVL
Przykład  rotacja pojedyncza: AVL niespełniony
3 3
1 5 1 8
2 4 8 2 5 9
6 9
4 6
y
x 7
7
y
x
A C
B C A B
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
22
Operacje na drzewie AVL
Jeszcze jeden przykład  rotacja podwójna: AVL
spełniony
-1
5
-1
5
+1 -1
3
+1
Usunięcie 4 9 +2
3
2 4 -1
7 11
Rotacja wokół 3
2
1
6 8 10 13
1
12 14 0 9
-2
5
-1
0
5 11
Co teraz?
0 -1
2
9
-1
2 7 10
13
1 3 -1
7 11
6 8 12 14
1 3
6 8 10 13
Po rotacji wokół 5
12 14
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
23
Operacje na drzewie AVL
Koszt operacji wstawiania i usuwania w AVL:
Rotacje działają w czasie O(1);
Zmieniają tylko wartości wskaz
ników a pozostałe pola węzłów są
bez zmian;
Dla drzewa o  n wierzchołkach:
minimalna liczba wierzchołków w drzewie AVL o wysokości h?
N0=1
N = N h-1 + N h-2 +1
h
h
Można udowodnić przez
indukcję, że Nh e" 2 h/2 h-2
PD
h-1
StÄ…d h d" 2 lg Nh LD
Liczba rotacji (koszt operacji) wynosi co najwyżej  lg n ;
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6
24
Dziękuję za uwagę
Z.Tarapata, Algorytmy i struktury danych, wykład nr 6