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