1
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
2
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
f)
Przykładowe struktury drzew.
a)
d)
e)
ASD
LJ
S
c)
b)
3
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ęźle określona jest
kolejność nastepników.
a
c
b
left neighbour
right neighbour
ASD
LJ
S
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ą.
Rekurncyjna definicja drzewa
1.
Pojedynczy węzeł jest zarazem drzewem i korzeniem.
2.
Załóżmy, że n jest węzłem, a T
1
, T
2
, ...,T
k
, są drzewami o korzeniach
odpowiednio n
1
, n
2
, ..., n
k
.
3.
Jeśli węzeł n jest przodkiem węzłów n
1
, n
2
, ..., n
k
to drzewa
T
1
, T
2
, ...,T
k
stają się poddrzewami utworzonego drzewa, a węzły potomkami
węzła n.
T
1
T
2
T
k
. . .
n
1
n
k
n
2
n
ASD
LJ
S
4
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.
Atrybuty węzeła x drzewa binarnego:
x.key, x.left, x.right.
x.left
x.right
x
x.key
ASD
LJ
S
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
{
int key;
node *left,*right;
};
node *root;
Reprezentacje drzew binarnych
Reprezentacje drzew binarnych:
1.
Tablicowa,
2.
Dowiązaniowa,
Reprezentacja tablicowa.
indeks
x. key
left
right
1
15
2
3
2
12
4
-1
3
6
5
-1
4
11
6
7
5
2
-1
-1
6
1
-1
-1
7
8
-1
-1
Reprezentacja rodzicielska (tablicowa)
(
parent representation
).
i
A[i]
1
0
2
1
3
1
4
2
5
3
6
4
7
4
A[i] = j gdy węzeł j jest rodzicem węzła i
A[i] = 0 gdy węzeł i jest korzeniem drzewa
1
15
3
6
2
12
5
2
4
11
7
8
6
1
ASD
LJ
S
5
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
/
/
/
/
/
/
/
/
/
/
ASD
LJ
S
Głębokość
0
root
1
2
3
Drzewa binarne
ASD
LJ
S
/
/
6
Przeglądanie drzewa
Przeglądanie drzewa (
tree traversal, node visiting
).
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.
y
z
x
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)
{
IF (x≠nil) {
INORDER (x.left);
P(x);
INORDER (x.right);
}
}
Przeglądanie inorder : < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
6
8
2
1
4
3
5
9
11
10
7
ASD
LJ
S
7
Przeglądanie drzewa
Przeglądanie wzdłużne
PREORDER
Klucz korzenia poddrzewa zostaje wypisany przed wypisaniem kluczy w obu
poddrzewach.
PREORDER (x)
{
IF (x≠nil) {
P(x);
PREORDER (x.left);
PREORDER (x.right);
}
}
Przeglądanie preorder : < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
1
7
2
3
4
5
6
10
11
9
8
ASD
LJ
S
Przeglądanie drzewa
Przeglądanie wsteczne
POSTORDER
:
Klucz korzenia poddrzewa zostaje wypisany po wypisaniu kluczy w obu
poddrzewach.
POSTORDER (x)
{
IF (x≠nil) {
POSTORDER (x.left);
POSTORDER (x.right);
P(x);
}
}
Przeglądanie postorder : < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
11
10
5
1
4
2
3
7
8
9
6
ASD
LJ
S
8
Przeglądanie drzewa
Przeglądanie poziomami L
EVEL-ORDER
Odwiedzane są węzły kolejnych poziomów, (zaczynając od korzenia) od lewej
do prawej.
Przeglądanie level-order: < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 >
1
3
2
4
5
8
9
10
11
7
6
ASD
LJ
S
Drzewa Poszukiwań Binarnych BST
Binary Search Trees
9
Drzewa BST
Drzewo BST - dowolne drzewo binarne, którego wierzchołki są ułożone zgodnie z
porządkiem symetrycznym.
Drzewa BST
Porządek symetryczny BSTP
(Binary search tree property
)
x.left
≤≤≤≤
≤
x
x.right
a)
13
25
10
2
12
29
31
20
b)
10
12
2
31
25
29
20
13
ASD
LJ
S
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.
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
10
Wyszukiwanie w BST
Wyszukiwanie w drzewach BST.
SEARCH_BST(x,v) //v-wyszukiwana wartość
klucza
// x- dany wskaźnik do
korzenia drzewa
{
IF((x==null)or(v==x.key)
return(x);
IF (v<x.key)
return(SEARCH_BST(x.left,v));
ELSE
return(SEARCH_BST(x.right,v));
}
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
Procedura wyznacza wskaźnik do węzła o kluczu v jeżeli istnieje, w przeciwnym
razie daje w wyniku nil.
17
22
20
21
24
19
9
9
8
5
11
Wyszukiwanie w BST
Iteracyjne wyszukiwanie w drzewach BST.
ITERATIVE_SEARCH_BST(x,v) // v-wyszukiwana wartość
// x- dany wskaźnik do korzenia drzewa
{
WHILE(x≠null)and(v≠x.key){
IF(v<x.key)
x=x.left;
ELSE
x=x.right;
}
return(x);
}
ASD
LJ
S
Procedura wyznacza wskaź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).
11
Wstawianie do drzewa BST
Wstawianie węzła do drzewa BST.
INSERT_BST(BST,z)
// wstawianie węzła z o kluczu v
// z.key=v; z.left=null;
// z.right=null;
{
y=null;
x=BST.root
WHILE(x≠null){
y=x;
IF (z.key<x.key ) x=x.left;
ELSE x=x.right;
}
z.parent=y;
IF (y=null) BST.root=z;
ELSE IF(z.key<y.key)y.left=z;
ELSE y.right=z;
}
Wstawianie węzła o kluczu v=18.
Procedura
INSERT_BST()
działa w czasie O(h).
ASD
LJ
S
17
9
20
22
19
21
24
8
11
9
5
18
Usuwanie w drzewach BST
1.
Usuwany węzeł z jest liściem - należy zastąpić wskaźnik do z w węźle-rodzicu
wartością null.
ASD
LJ
S
13
z
12
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.
ASD
LJ
S
16
z
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.
ASD
LJ
S
6
y
y
6
z
z
13
Drzewa BST
Wyszukiwanie: Minimum, Maximum.
MINIMUM_BST(x)
// x - wskaźnik do korzenia
{
WHILE(x.left≠null)x=x.left;
return(x);
}
MAXIMUM_BST(x)
{
WHILE(x.right≠null)x=x.right;
return(x);
}
Procedury działają na drzewie o wysokości h w czasie O(h).
ASD
LJ
S
Procedury wyznaczają odpowiednio wskaźniki do minimalnego oraz maksymalnego
elementu drzewa BST o korzeniu w węźle x.
Usuwanie w BST
Usuwanie węzła z w drzewie BST
(uwzględnienie przypadków 1-3).
DELETE_BST(BST,z)
//z-wskaź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
14
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
15
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
C
B
a)
B
A
c)
d)
A
ASD
LJ
S
A
b)
Operacja rotacji
Rodzaje rotacji:
Prawa rotacja R (
Right rotate
)
Lewa rotacja L (
Left rotate
)
A, B, C – poddrzewa.
Rotacja R(Y)
Rotacja L(X)
Rotacja R(Y) – prawa rotacja na węźle Y.
ASD
LJ
S
C
B
A
G
X
Y
C
B
A
G
Y
X
Rotacja L(X) – lewa rotacja na węźle X.
16
Rotacje węzłów
Prawa rotacja.
Rotation R(Y)
// Prawa rotacja na węź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;
}
}
Rotacja R(Y)
ASD
LJ
S
C
B
A
G
Y
X
C
B
A
G
X
Y
Rotacje węzłów
Lewa rotacja.
Rotation L(X)
// Lewa rotacja na węź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;
}
}
Rotacja L(X)
ASD
LJ
S
C
B
A
G
Y
X
C
B
A
G
X
Y
17
Rotacje węzłów
Rotacja zachowuje własność symetryczności drzewa BST.
Procedury rotacji działąją w czasie O(1).
Rotacja R(Y)
Inorder: <2, 3, 4, 6, 7, 9, 11, 14, 17, 18, 19>
ASD
LJ
S
7
4
3
6
Y
2
19
14
17
9
X
18
11
7
4
3
6
2
9
14
17
19
X
Y
11
18
Rotacje węzłów
Rotacja L(X)
Inorder: <2, 3, 4, 6, 7, 9, 11, 14, 17, 18, 19>
ASD
LJ
S
7
4
3
6
Y
2
19
14
17
9
X
18
11
7
4
3
6
2
9
14
17
19
X
Y
11
18
18
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).
CREATE_LINE (x,n)
// x wskaźnik do korzenia drzewa BST;
{
y=x;
WHILE(y ≠ null){
IF (y.left ≠ null)
Rotacja Prawa na węźle y;
ELSE
y=y.right;
}
Czas działania fazy 1 jest rzędu O
f1
(n).
Faza 1:
ASD
LJ
S
Równoważenie drzewa BST
Algorytm DSW - Faza 1 (przykład).
ASD
LJ
S
a)
5
y
10
20
30
40
15
25
28
23
e)
5
y
10
25
20
23
15
30
28
40
. . .
5
y
10
40
20
30
15
25
28
23
b)
19
Równoważenie drzewa BST
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;
}
}
Wartości początkowe: n=9, m=7.
b) Stan po (n-m) rotacjach,
Węzły podlegające rotacji są oznaczone linią ciągłą.
Faza 2:
25
30
28
23
40
a)
5
15
10
20
40
5
15
b)
10
23
28
20
25
30
10
5
15
23
28
40
c)
20
25
30
25
20
10
23
28
30
d)
40
5
15
ASD
LJ
S
Złożoność algorytmu DSW
Złożoność obliczeniowa fazy 1.
ASD
LJ
S
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 O
f1
(n).
Złożoność obliczeniowa fazy 2.
m=2
lg(n+1)
- 1 ≤ 2
lg(n+1)
-1= n
Zakładając, że:
Liczba rotacji:
2
i
i=1
n – m + Σ
lgm-1
m
→ n
dla dużych n
≤ n
2
i
i=1
Σ
lgm-1
1
2
i
Σ
i
1
→ 1
Czas działania drugiej fazy wynosi O
f2
(n).
Złożoność obliczeniowa algorytmu: O(n)=O
f1
(n)+O
f2
(n).
20
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.
-1
0
1
-1
0
0
1
-1
0
1
0
-1
0
Przykłady drzew AVL:
ASD
LJ
S
21
Drzewa AVL
ASD
LJ
S
Przykłady drzew AVL.
Drzewa AVL
Wstawianie węzła do prawego poddrzewa węzła Q.
h
h+1
h
c)
0
Q
0
P
Rotacja L(P)
h+1
h
h
h
a)
1 P
1 Q
h+2
h+1
h
h
b)
2 P
1 Q
ASD
LJ
S
22
Drzewa AVL
Wstawianie węzła do lewego poddrzewa węzła Q.
h
h
h
a)
1 P
0 Q
h+1
h
h
b)
2 P
-1 Q
h
h-1
h
h
c)
2 P
-1 Q
1 R
h
h-1
h
h
e)
0 R
0 Q
-1 P
Rotacja R(Q)
Rotacja L(P)
h
h-1
h
h
d)
2 P
2 R
0 Q
ASD
LJ
S
Drzewa AVL
Wstawianie węzła nie wymagające korygowania równoważenia.
ASD
LJ
S
23
Drzewa AVL
Wstawienia węzła wymagającego rotacji L do przywrócenia zrównoważenia.
ASD
LJ
S
L(P)
Drzewa AVL
Usuwanie węzła w lewym poddrzewie węzła P (
przypadek1
).
h
h-1
h
a)
1
P
1 Q
h-1
h-1
h
c)
0
Q
0
P
h
h-1
h-1
b)
2
P
1 Q
L(P)
ASD
LJ
S
24
Drzewa AVL
h
h
h
a)
1 P
0 Q
h
h
h-1
c)
-1 Q
1 P
L(P)
h-1
b)
h
h
2 P
1 Q
ASD
LJ
S
Usuwanie węzła w lewym poddrzewie węzła P (
przypadek 2
).
Drzewa AVL
h-2
h
h-1
a)
1 P
-1 Q
1 R
h-1
h-1
h-2
h-1
d)
0 R
1 Q
h-1
0 P
R(Q)
h-1
c)
2 P
-1 R
h-1
1 Q
h-1
h-2
h-2
h-1
h-1
b)
2 P
-1 Q
1 R
h-1
L(P)
L(P)
ASD
LJ
S
Usuwanie węzła w lewym poddrzewie węzła P (
przypadek 3
).
25
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)
26
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
).
27
2
2 18
1
44
1
26
16
1
1 14
1
17
null
null
null
null
null
null
null
null
ASD
LJ
S
27
Wstawianie do drzewa RB
27
18
44
26
16
14
17
Wstawianie węzła x.
ASD
LJ
S
x
15
null
null
Wstawiany węzeł
Wstawianie do drzewa RB
27
18
44
26
16
14
17
15
Krok 1. Wstawianie węzła (liścia, o kluczu 15).
ASD
LJ
S
Nowy węzeł powstanie jako prawostronny potomek węzła o kluczu14.
28
Wstawianie do drzewa RB
27
18
44
26
16
14
17
15
Krok 2. Uaktualnienie kolorów węzłów przodków.
ASD
LJ
S
Nowy węzeł powstanie jako prawostronny potomek węzła o kluczu14.
Wstawianie do drzewa RB
Krok 3. Prawa rotacja na węźle o kluczu 27 w celu spełnienia warunku (4).
27
18
44
26
15
16
17
14
ASD
LJ
S
16
27
17
44
26
14
15
18
29
Wstawianie do drzewa RB
16
17
44
26
14
15
18
27
Krok 4. Aktualizacja kolorów.
ASD
LJ
S
16
27
17
44
26
14
15
18
Wstawianie do drzewa RB
Drzewo czerwono-czarne po wstawieniu węzła o kluczu 15.
2
16
1
17
1
44
1
26
1
15
2
18
2
27
1
14
nul
l
nul
l
nul
l
nul
l
nul
l
nul
l
nul
l
nul
l
nul
l
ASD
LJ
S