Hierarchiczne struktury danych
Drzewa
Trees
Drzewa
Podstawowe pojęcia.
Drzewo - kolekcja węzłów, z których jeden wyróżniony jest jako korzeń (root).
Węzły powiązane są ze sobą relacją rodzicielstwa (parenthood), która decyduje
o ich hierarchicznym układzie.
Węzły, mające tego samego rodzica tworzą rodzeństwo (sibling).
Węzeł, występujący w grupie rodzeństwa bezpośrednio na prawo nazywa się
prawym sąsiadem (right neighbour, right sibling ), (analogiczna definicja lewego
sąsiada).
Ścieżka (path)  ciąg krawędzi. Liczba krawędzi na ścieżce nazywa się
długością (length).
Wysokość (height) węzła  liczba krawędzi na najdłuższej ścieżce prowadzącej
od tego węzła do liścia.
Wysokość drzewa jest wysokością jego korzenia.
Głębokość (depth) (poziom) węzła - długość ścieżki łączącej węzeł z korzeniem.
ASD LJ S
1
Drzewa
Podstawowe pojęcia.
Przodkiem (ancestor) węzła jest każdy węzeł znajdujący się na drodze do
korzenia.
Potomkiem (descendant) węzła jest każdy węzeł, dla którego jest on przodkiem.
Nastepnikiem (successor) węzła jest jego bezpośredni potomek.
Poprzednikiem (predecessor) węzła jest jego bezpośredni przodek.
Liściem (leaf) (węzłem zewnętrznym) nazywamy węzeł, który nie ma
nastepników.
Węzeł wewnętrzny (internal node) węzeł nie będący liściem.
Poddrzewem (subtree) o korzeniu v nazywamy węzeł v wraz ze wszystkimi
potomkami.
Stopień (degree) węzła nazywamy liczbę poddrzew skojarzonych z tym węzłem.
Lasem (forest) nazywamy zbior rozłącznych drzew.
ASD LJ S
Struktury drzew
Przykładowe struktury drzew.
b) c)
a)
d)
e)
f)
ASD LJ S
2
Rodzaje drzew
Drzewo nieuporzadkowane (unordered tree)  drzewo, w którym kolejność
węzłów jest dowolna.
Drzewo jest uporządkowane (ordered tree) jeśli w każdym węz
le określona jest
kolejność nastepników.
a
b c
left neighbour right neighbour
Drzewo binarne (binary tree)  drzewo uporządkowane, w którym każdy węzeł
ma co najwyżej dwa następniki.
Drzewo etykietowane (labeled tree) posiada etykietę związaną z każdym węzłem
lub krawędzią.
ASD LJ S
Rekurncyjna definicja drzewa
1. Pojedynczy węzeł jest zarazem drzewem i korzeniem.
2. Załóżmy, że n jest węzłem, a T1, T2, ...,Tk, są drzewami o korzeniach
odpowiednio n1, n2, ..., nk.
3. Jeśli węzeł n jest przodkiem węzłów n1, n2, ..., nk to drzewa
T1, T2, ...,Tk stają się poddrzewami utworzonego drzewa, a węzły potomkami
węzła n.
n
nk
n2
n1
T2 Tk
T1
. . .
ASD LJ S
3
Drzewo binarne
Drzewo binarne BT (Binary Tree) - drzewo, którego każdy z węzłów posiada:
1. lewe i prawe poddrzewo,
2. posiada jedno z nich,
3. nie posiada poddrzew.
Drzewo binarne jest szczególnym przypadkiem drzewa uporządkowanego, w
którym każdy węzeł wewnętrzny ma co najwyżej dwóch potomków (każdy węzeł
wewnętrzny jest stopnia co najwyżej drugiego).
struct node Atrybuty węzeła x drzewa binarnego:
{
x.key, x.left, x.right.
int key;
node *left,*right;
x x.key
};
node *root;
x.left x.right
ASD LJ S
Reprezentacje drzew binarnych
1
Reprezentacje drzew binarnych:
15
1. Tablicowa,
2
12 3
6
2. Dowiązaniowa,
4
11
5
2
6
1 7
8
Reprezentacja tablicowa.
Reprezentacja rodzicielska (tablicowa)
indeks x. key left right
(parent representation).
1 15 2 3
2 12 4 -1
i 1 2 3 4 5 6 7
3 6 5 -1
A[i] 0 1 1 2 3 4 4
4 11 6 7
5 2 -1 -1
A[i] = j gdy węzeł j jest rodzicem węzła i
6 1 -1 -1
A[i] = 0 gdy węzeł i jest korzeniem drzewa
7 8 -1 -1
ASD LJ S
4
Reprezentacja dowiązaniowa
Rodzaje implementacji dowiązaniowej.
Implementacja dwuodsyłaczowa
- mniej pamięci
Implementacja trójodsyłaczowa
- więcej pamięci
- elastyczna nie wymagająca przeglądania drzewa od korzenia
Głębokość
root
/
/
0
/
/
1
/ /
2
3 / /
/ /
ASD LJ S
Drzewa binarne
/
/
ASD LJ S
5
Przeglądanie drzewa
Przeglądanie drzewa (tree traversal, node visiting).
x
y z
1. Poprzeczny (inorder): < y, x, z >
2. Wzdłużny (preorder): < x, y, z>
3. Wsteczny (postorder): < y, z, x >
4. Poziomami (level-order): kolejne poziomy od lewej do prawej.
ASD LJ S
Przeglądanie drzewa
Przeglądanie poprzeczne INORDER.
Klucz korzenia poddrzewa zostaje wypisany między wartościami z jego
lewego poddrzewa a wartościami z jego prawego poddrzewa.
INORDER (x)
6
{
2 8
IF (x`"nil) {
INORDER (x.left);
1 10
P(x);
4 7
INORDER (x.right);
}
3 9 11
5
}
Przeglądanie inorder : < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
ASD LJ S
6
Przeglądanie drzewa
Przeglądanie wzdłużne PREORDER
Klucz korzenia poddrzewa zostaje wypisany przed wypisaniem kluczy w obu
poddrzewach.
PREORDER (x) 1
{
2 7
IF (x`"nil) {
P(x);
3 9
4 8
PREORDER (x.left);
PREORDER (x.right);
5 10 11
6
}
}
Przeglądanie preorder : < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
ASD LJ S
Przeglądanie drzewa
Przeglądanie wsteczne POSTORDER:
Klucz korzenia poddrzewa zostaje wypisany po wypisaniu kluczy w obu
poddrzewach.
11
POSTORDER (x)
{ 5 10
IF (x`"nil) {
POSTORDER (x.left);
1 9
4 6
POSTORDER (x.right);
P(x);
2 7 8
}
3
}
Przeglądanie postorder : < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
ASD LJ S
7
Przeglądanie drzewa
Przeglądanie poziomami LEVEL-ORDER
Odwiedzane są węzły kolejnych poziomów, (zaczynając od korzenia) od lewej
do prawej.
1
2 3
4 7
5 6
8 10 11
9
Przeglądanie level-order: < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
ASD LJ S
Drzewa Poszukiwań Binarnych BST
Binary Search Trees
8
Drzewa BST
Własność drzewa BST: jeśli węzeł x zawiera wartość x.key to wszystkie wartości
przechowywane w jego lewym poddrzewie są nie większe od x.key a wszystkie
wartości przechowywane w prawym poddrzewie są nie mniejsze od x.key.
Własność ta ustala porządek symetryczności.
Drzewo BST - dowolne drzewo binarne, którego wierzchołki są ułożone zgodnie z
porządkiem symetrycznym.
b)
a)
10
x
13
2 12
10 25
25
2 31
12 20
20 31
29
x.right
x.left
13 29
Porządek symetryczny BSTP
Drzewa BST
(Binary search tree property)
ASD LJ S
Interfejs drzewa BST
Podstawowe operacje na drzewach BST:
Wyszukiwanie (Search) O(h)
Wstawianie (Insert) O(h)
Usuwanie (Delete) O(h)
Wyszukiwanie minimum (Minimum) O(h)
Wyszukiwanie maksimum (Maximum) O(h)
Predecessor, Successor O(h)
ASD LJ S
9
d"
d"
d"
d"
d"
Wyszukiwanie w BST
Wyszukiwanie w drzewach BST.
SEARCH_BST(x,v) //v-wyszukiwana wartość
klucza
17
// x- dany wskaz
nik do
20
korzenia drzewa
8
{
IF((x==null)or(v==x.key)
5 19 22
9
return(x);
IF (vreturn(SEARCH_BST(x.left,v));
9 21 24
ELSE 11
return(SEARCH_BST(x.right,v));
}
Procedura wyznacza wskaz
nik do węzła o kluczu v jeżeli istnieje, w przeciwnym
razie daje w wyniku nil.
Wyszukiwanie klucza o wartości 11 wymaga przejścia po ścieżce:
17 8 9 11
Czas działania procedury SEARCH_BST() wynosi O(h), gdzie h jest wysokością drzewa.
ASD LJ S
Wyszukiwanie w BST
Iteracyjne wyszukiwanie w drzewach BST.
ITERATIVE_SEARCH_BST(x,v) // v-wyszukiwana wartość
// x- dany wskaz
nik do korzenia drzewa
{
WHILE(x`"null)and(v`"x.key){
IF(vx=x.left;
ELSE
x=x.right;
}
return(x);
}
Procedura wyznacza wskaz
nik do węzła o kluczu v jeżeli istnieje, w przeciwnym
razie daje w wyniku nil.
Czas działania procedury ITERATIVE_SEARCH_BST() wynosi O(h).
ASD LJ S
10
Wstawianie do drzewa BST
Wstawianie węzła do drzewa BST.
INSERT_BST(BST,z)
Wstawianie węzła o kluczu v=18.
// wstawianie węzła z o kluczu v
// z.key=v; z.left=null;
17
// z.right=null;
{
8
y=null; 20
x=BST.root
WHILE(x`"null){
5
9 19 22
y=x;
IF (z.keyELSE x=x.right; 9 11 21 24
18
}
z.parent=y;
IF (y=null) BST.root=z;
ELSE IF(z.keyELSE y.right=z;
}
Procedura INSERT_BST() działa w czasie O(h).
ASD LJ S
Usuwanie w drzewach BST
1. Usuwany węzeł z jest liściem - należy zastąpić wskaz
nik do z w węz
le-rodzicu
wartością null.
13
z
ASD LJ S
11
Usuwanie w drzewach BST
2. Usuwany węzeł z ma jednego syna. Należy połączyć ojca węzła z oraz
syna usuwnego węzła.
z
16
ASD LJ S
Usuwanie w drzewach BST
3. Usuwanie węzła z o dwóch synach  należy wyciąć następnik (successor)
(w uporządkowaniu inorder) y węzła z, o którym wiadomo, że nie ma
lewego syna oraz zastąpić zawartość z zawartością y.
y z
6
z
6
y
ASD LJ S
12
Usuwanie w BST
Usuwanie węzła z w drzewie BST (uwzględnienie przypadków 1-3).
DELETE_BST(BST,z)
//z-wskaz
nik do usuwanego węzła
{
IF(z.left==null or z.right==null) y=z;
ELSE {
y=z.right;
WHILE(y.left`"null) y=y.left;
}
IF(y.left`"null) x=y.left;
ELSE x=y.right;
IF(x`"null) x.parent=y.parent;
IF(y.parent=null) BST.root=x
ELSE {
IF(y=y.parent.left)y.parent.left=x;
ELSE y.parent.right=x
}
// Skopiowanie zawartości węzła y do węzła z
IF (y`"z) BST.copy (y,z);
}
Procedura działa na drzewie o wysokości h w czasie O(h).
ASD LJ S
Drzewa BST
Wyszukiwanie: Minimum, Maximum.
MINIMUM_BST(x) MAXIMUM_BST(x)
// x - wskaz
nik do korzenia {
{ WHILE(x.right`"null)x=x.right;
WHILE(x.left`"null)x=x.left; return(x);
return(x); }
}
Procedury wyznaczają odpowiednio wskaz
niki do minimalnego oraz maksymalnego
elementu drzewa BST o korzeniu w węz
le x.
Procedury działają na drzewie o wysokości h w czasie O(h).
ASD LJ S
13
Zrównoważone drzewa BST
Balanced trees
Równoważenie drzew BST
Złożoność obliczeniowa operacji na drzewach BST jest proporcjonalna do
wysokości drzewa,
Zrownoważone drzewo binarne to drzewa, w których różnica wysokości obu
poddrzew każdego węzła w drzewie wynosi 0 lub 1,
Drzewo w pełni zrownoważone - jeśli jest zrównoważone, a wszystkie liście
znajdują się na jednym lub dwóch poziomach,
Drzewa w pełni zrównoważone są drzewami BST gwarantującymi wysokość
O(lg n).
ASD LJ S
14
Równoważenie drzew BST
a) Lewostronnie w pełni zrównoważone drzewo BST.
b) W pełni zrównoważone drzewo BST.
c) Drzewo nie jest zrównoważone (współczynnik wyważenia dla węzła A wynosi 3).
d) Najgorszy przypadek zrównoważenia, drzewo binarne zdegenerowane (skewed
tree, dla A współcz. wynosi 4).
a)
d)
c)
A A
b) A
A
B C
B
ASD LJ S
Operacja rotacji
Rodzaje rotacji:
Prawa rotacja R (Right rotate)
Lewa rotacja L (Left rotate)
G
G
Rotacja R(Y)
Y X
X C Y
A
Rotacja L(X)
B C
A B
A, B, C  poddrzewa.
Rotacja R(Y)  prawa rotacja na węz
le Y.
Rotacja L(X)  lewa rotacja na węz
le X.
ASD LJ S
15
Rotacje węzłów
Prawa rotacja.
Rotation R(Y)
// Prawa rotacja na węz
le Y;
// Węzeł X jest lewym synem węzła Y;
{ IF (Y.left `" null){
1. Dziadek G węzła X staje się jego ojcem (X zastępuje Y);
2. Węzeł Y staje się prawym synem swego dotychczasowego lewego
syna X;
3. Prawe poddrzewo X staje się lewym poddrzewem wezła Y;
}
}
G
G
Rotacja R(Y)
Y
X
X C
Y
A
A B
B C
ASD LJ S
Rotacje węzłów
Lewa rotacja.
Rotation L(X)
// Lewa rotacja na węz
le X;
// Węzeł Y jest prawym synem węzła X;
{ IF (X.right `" null){
1. Dziadek węzła Y staje się jego ojcem (Y zastępuje X);
2. Węzeł X staje się lewym synem swego dotychczasowego prawego
syna Y;
3. Lewe poddrzewo węzła Y staje się prawym poddrzewem wezła X;
}
}
G
G
Rotacja L(X)
Y
X
X C
Y
A
A B
B C
ASD LJ S
16
Rotacje węzłów
Rotacja zachowuje własność symetryczności drzewa BST.
Procedury rotacji działąją w czasie O(1).
7
7
4 X
11
Rotacja R(Y)
4 Y
18
3 Y
18
6
9
3
19
6
11
X
2
14 19
2
14
9
17
17
Inorder: <2, 3, 4, 6, 7, 9, 11, 14, 17, 18, 19>
ASD LJ S
Rotacje węzłów
7
7
4 X
11
4 Y
18
Rotacja L(X)
3 Y
18
6
9
3
19
6
11
X
2
14 19
2
14
9
17
17
Inorder: <2, 3, 4, 6, 7, 9, 11, 14, 17, 18, 19>
ASD LJ S
17
Równoważenie drzewa BST
Algorytm DSW (C. Day, Q. Stout, L. Warren):
Faza 1. Przekształcenie drzewa BST w strukurę liniową (rotacje w prawo).
Faza 2. Przekształcenie strukury liniowej w zrównoważone drzewo BST
(rotacje w lewo).
Faza 1:
CREATE_LINE (x,n)
// x wskaz
nik do korzenia drzewa BST;
{
y=x;
WHILE(y `" null){
IF (y.left `" null)
Rotacja Prawa na węz
le y;
ELSE
y=y.right;
}
Czas działania fazy 1 jest rzędu Of1(n).
ASD LJ S
Równoważenie drzewa BST
Algorytm DSW - Faza 1 (przykład).
e)
5
a)
b)
5
y
5
10
10
10
15
15
. . .
20 20
20
23
30
15
y
30
25
40
25
25 40
28
23
28
28
30
23
40
y
ASD LJ S
18
Równoważenie drzewa BST
Faza 2:
CREATE Tree(n)
{ // m liczba węzłów w najbli\
szym pełnym drzewie binarnym;
// pełne drzewo binarne posiada wszystkie liście na jednym poziomie.
m=2�łlg(n+1)�ł-1;
wykonać n-m rotacji w lewo, zaczynając od początku linii;
WHILE (m > 1){
m=m/2;
wykonać m rotacji w lewo, zaczynając od początku linii;
}
}
a)
5 b) 10
c) 25
20
d)
20
10 5
20 30
10
25
15 15 23
10 23
5 15 28 40
23 30
20 25
5 15
28 40
23
28
25
Wartości początkowe: n=9, m=7.
28 30
b) Stan po (n-m) rotacjach,
30
Węzły podlegające rotacji są oznaczone linią ciągłą.
40
40
ASD LJ S
Złożoność algorytmu DSW
Złożoność obliczeniowa fazy 1.
W najgorszym przypadku w pętli WHILE wykona się (n-1) rotacji, gdzie n jest liczbą
węzłów w drzewie. Czas działania pierwszej fazy wynosi Of1(n).
Złożoność obliczeniowa fazy 2.
Zakładając, że:
m=2�łlg(n+1)�ł - 1 d" 2lg(n+1) -1= n
Liczba rotacji:
lgm-1
lgm-1
1
m
d" n Ł n dla dużych n
Ł
n  m +
2i i=1 2i
i=1
1
Łi 2i 1
Czas działania drugiej fazy wynosi Of2(n).
Złożoność obliczeniowa algorytmu: O(n)=Of1(n)+Of2(n).
ASD LJ S
19
Drzewa AVL
(Adelson, Velskii, Landis)
G. Adelson-Velskii, J. Landis (1962)
Drzewa AVL
Zrównoważone drzewa AVL.
Drzewa równoważone lokalnie,
Dla każdego węzła wysokość poddrzew różni się nie więcej niż o jeden
poziom,
Współczynnik wyważenia węzła (różnice wysokości lewego i prawego
poddrzewa węzła): 1, -1, 0.
Przykłady drzew AVL:
1
1
-1
-1 -1
-1
0
0
0
1 0
0
0
ASD LJ S
20
Drzewa AVL
Przykłady drzew AVL.
ASD LJ S
Drzewa AVL
Wstawianie węzła do prawego poddrzewa węzła Q.
c)
b)
a)
1 P
0 Q
2 P
Rotacja L(P)
1 Q
1 Q
h
h 0 P
h+1
h+1
h+2
h
h h
h
h+1
h
ASD LJ S
21
Drzewa AVL
Wstawianie węzła do lewego poddrzewa węzła Q.
c)
b)
a)
1 P 2 P
2 P
0 Q
-1 Q
h
-1 Q
h h
1 R
h
h
h
h
h+1
h-1
h
d)
e)
2 P
0 R
Rotacja L(P)
Rotacja R(Q)
2 R
h
0 Q
-1 P
0 Q
h-1
h h
h
h h-1 h
ASD LJ S
Drzewa AVL
Wstawianie węzła nie wymagające korygowania równoważenia.
ASD LJ S
22
Drzewa AVL
Wstawienia węzła wymagającego rotacji L do przywrócenia zrównoważenia.
L(P)
ASD LJ S
Drzewa AVL
Usuwanie węzła w lewym poddrzewie węzła P (przypadek1).
c)
a)
b) 0
Q
1 P
2 P
L(P)
0
P
1 Q 1 Q
h
h-1
h-1
h-1 h
h
h
h-1
h-1
ASD LJ S
23
Drzewa AVL
Usuwanie węzła w lewym poddrzewie węzła P (przypadek 2).
c)
b)
a)
2 P -1 Q
1 P
L(P)
1 Q
0 Q 1 P
h-1
h
h
h h-1 h
h h
h
ASD LJ S
Drzewa AVL
Usuwanie węzła w lewym poddrzewie węzła P (przypadek 3).
a)
b)
c)
1 P 2 P
2 P
-1 Q
h-1 -1 Q
R(Q) h-1 -1 R
h
L(P)
h-1
1 Q
1 R h-1 1 R h-1
h-2
h-1
h-1 h-2 h-1 h-2
d)
0 R
L(P)
0 P 1 Q
h-1 h-1
h-2 h-1
ASD LJ S
24
Drzewa AVL
Własności drzew AVL:
Drzewo zawsze zrownoważone,
Dla każdego wierzchołka wysokości dwóch jego poddrzew różnią się
co najwyżej o 1,
Wyszukiwanie zawsze O(log(n))
Search, min, max, successor, predecessor  nie zmieniają struktury
drzewa,
Insert, delete  zmieniają strukturę drzewa.
ASD LJ S
Drzewa czerwono-czarne
Red-Black
R. Bayer (1972)
25
Drzewa RB
Własności drzew RB:
1. Każdy węzeł jest czerwony lub czarny,
2. Korzeń drzewa jest czarny,
3. Każdy liść (null) jest czarny,
4. Jeśli węzeł jest czerwony to obaj jego synowie są czarni,
5. Każda ścieżka z ustalonego węzła do liścia ma tyle samo czarnych węzłów,
6. Każdy węzeł drzewa zawiera pola color, key, left, right oraz parent.
7. Search, min, max, successor, predecessor  nie zmieniają drzewa,
8. Insert, delete  zmieniają drzewo.
9. Pesymistyczna złożoność operacji O(lgn).
ASD LJ S
Drzewa RB
Przykład drzewa czerwono-czarnego. Podane są czarne wysokości węzłów bh
(black height).
2 27
2 1
18 44
null null
1 16 1
26
null null
1 1
17
14
null null null null
ASD LJ S
26
Wstawianie do drzewa RB
Wstawianie węzła x.
27
18 44
x
16
15
26
null null
14 17
Wstawiany węzeł
ASD LJ S
Wstawianie do drzewa RB
Krok 1. Wstawianie węzła (liścia, o kluczu 15).
27
18 44
16
26
14 17
15
Nowy węzeł powstanie jako prawostronny potomek węzła o kluczu14.
ASD LJ S
27
Wstawianie do drzewa RB
Krok 2. Uaktualnienie kolorów węzłów przodków.
27
18 44
16
26
14 17
15
Nowy węzeł powstanie jako prawostronny potomek węzła o kluczu14.
ASD LJ S
Wstawianie do drzewa RB
Krok 3. Prawa rotacja na węz
le o kluczu 27 w celu spełnienia warunku (4).
27
18
18 44
16 27
16
26
44
17
14 26
17
14
15
15
ASD LJ S
28
Wstawianie do drzewa RB
Krok 4. Aktualizacja kolorów.
18
18
16 27
16 27
44
17
44 14 26
17
14 26
15 15
ASD LJ S
Wstawianie do drzewa RB
Drzewo czerwono-czarne po wstawieniu węzła o kluczu 15.
2
18
2
16
2
27
1
14
1
17
1 1
26 44
nul
nul nul
l nul nul nul nul
1
l l
15
l l l l
nul nul
l l
ASD LJ S
29