Drzewa

Def. Graf T nazywamy drzewem, je»eli T jest grafem

spójnym i nie posiada cykli.
Def. Las G to graf, który nie posiada cykli (mo»e by¢

niespójny). Oczywi±cie spójne podgrafy takiego grafu G s¡

drzewami.

drzewo

las

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

1

Drzewa

Rozwa»my drzewo T .

Dla drzewa T musi istnie¢

dokªadnie jedna ±cie»ka prosta pomi¦dzy dwoma dowolnymi

wierzchoªkami.

Gdyby istniaªy dwie takie ±cie»ki, to

tworzyªyby one cykl. Ponadto:

•

Zaªó»my, »e w drzewie T nie ma kraw¦dzi {u, v}. Je»eli

do drzewa T dodamy kraw¦d¹ e = {u, v}, to kraw¦d¹

ta wraz ze ±cie»k¡ prost¡ z u do v w T tworzy cykl.

Tak powi¦kszony graf nie jest zatem drzewem.

•

Z drugiej strony zaªó»my, »e w drzewie T jest kraw¦d¹
e = {u, v}

. Je»eli z drzewa T usuniemy kraw¦d¹ e, to

T

staje si¦ grafem niespójnym (nie istnieje ±cie»ka z u

do v). Tak zmodykowany graf nie jest zatem drzewem.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

2

Drzewa

Dla grafów sko«czonych (grafów o sko«czonej liczbie

w¦zªów) zachodzi nast¦puj¡ce twierdzenie.
Tw. Niech G b¦dzie grafem o n > 1 wierzchoªkach.

Poni»sze stwierdzenia s¡ równowa»ne:

(i) G jest drzewem.

(ii) G jest grafem bez cyklów i ma n − 1 kraw¦dzi.

(iii) G jest spójny i ma n − 1 kraw¦dzi.

Z powy»szego twierdzenia wynika nast¦puj¡cy wniosek:
Wn. Je»eli T jest drzewem o n w¦zªach, to drzewo T ma
n − 1

kraw¦dzi.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

3

Drzewo rozpinaj¡ce grafu

Def. Podgraf T grafu spójnego G nazywamy drzewem

rozpinaj¡cym grafu G, je»eli T jest drzewem oraz T zawiera

wszystkie wierzchoªki grafu G.
Na poni»szym rysunku przedstawiono pewien graf G oraz

trzy przykªadowe drzewa rozpinaj¡ce T

1

, T

2

i T

3

.

1

T

2

T

3

T

G

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

4

Drzewa ukorzenione

Def.

Drzewo ukorzenione (drzewo z wyró»nionym

korzeniem) to takie drzewo T , w którym pewien wierzchoªek
r

jest wyró»niony. Wyró»niony wierzchoªek r nazywamy

korzeniem.
W drzewie ukorzenionym jest dokªadnie jedna ±cie»ka od

korzenia r do dowolnego wierzchoªka v drzewa T . Oznacza

to, »e drzewo ukorzenione mo»emy traktowa¢ jako graf

skierowany.
Z dowolnego drzewa T mo»emy uczyni¢ drzewo ukorzenione

wybieraj¡c jeden z w¦zªów na korze«.
Rozwa»my drzewo ukorzenione T .

Dªugo±¢ drogi od

korzenia r do wierzchoªka v nazywamy gª¦boko±ci¡

(wysoko±ci¡, poziomem) wierzchoªka v.

Maksymaln¡

gª¦boko±¢ wierzchoªka w drzewie T nazywamy gª¦boko±ci¡

(wysoko±ci¡) drzewa. Wierzchoªki stopnia 1, inne ni»

korze«, nazywamy li±¢mi. ‘cie»ka skierowana od pewnego

wierzchoªka do li±cia nazywana jest gaª¦zi¡

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

5

Drzewa ukorzenione

Przykªad. Rozwa»my drzewo ukorzenione przedstawione

przedstawione na poni»szym rysunku.

r

b

f

a

c

g

d

h

i

j

e

Powy»sze drzewo ma 5 li±ci: d, h, f, i, j. Gª¦boko±¢

wierzchoªka a wynosi 1, wierzchoªka f wynosi 2, natomiast

wierzchoªka j wynosi 3. Gª¦boko±¢ drzewa wynosi 3.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

6

Drzewa binarne

Def. Drzewo binarne T deniujemy na sko«czonym zbiorze

elementów nazywanych w¦zªami, w nast¦puj¡cy sposób:

(1) T jest drzewem pustym (zbiorem pustym), albo

(2) T

zawiera wyró»niony w¦zeª R,

nazywany

korzeniem T , natomiast pozostaªe w¦zªy T tworz¡

par¦ uporz¡dkowan¡ rozª¡cznych drzew binarnych T

1

i

T

2

Uwagi.

1. Powy»sza denicja drzewa binarnego jest rekurencyjna.

2. Zgodnie z t¡ denicj¡, drzewo binarne nie jest drzewem

ukorzenionym.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

7

Drzewa binarne

Przykªad. Rozpatrzmy drzewo binarne T przedstawione na

poni»szym rysunku.

A

B

C

D

E

F

Z denicji powy»sze drzewo mo»na zapisa¢ nast¦puj¡co:

T = (A, (T

1

, T

2

))

T

1

= (B, (T

3

, T

4

))

T

2

= (C, (T

5

, T

6

))

T

3

= (D, (T

7

, T

8

))

T

5

= ∅

T

4

= (E, (T

9

, T

10

))

T

6

= (F, (T

11

, T

12

))

gdzie drzewa T

7

= T

8

= T

9

= T

10

= T

11

= T

12

= ∅

.

Zatem:

T =

A,

„

“

B,

`(D, (∅, ∅)) , (E, (∅, ∅))´

”

,

“

C,

`∅, (F, (∅, ∅))´

”

«

!

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

8

Drzewa binarne

Je»eli T zawiera korze« R, to drzewa T

1

i T

2

nazywamy

odpowiednio lewym i prawym poddrzewem R. Je»eli

poddrzewo T

1

nie jest zbiorem pustym, to jego korze«

N

1

nazywamy lewym dzieckiem R. Podobnie korze« N

2

niepustego poddrzewa T

2

nazywamy prawym dzieckiem R.

W¦zeª R jest rodzicem dla w¦zªów N

1

i N

2

.

W¦zeª L jest nazywany potomkiem w¦zªa N (N jest

nazywany wówczas przodkiem w¦zªa L), je»eli istnieje ci¡g

dzieci z N do L.
Ka»dy w¦zeª w drzewie T ma przypisany poziom w

nast¦puj¡cy sposób. Korze« R drzewa T ma przypisany

poziom 0. Ka»dy inny w¦zeª ma przypisany poziom o 1

wi¦kszy ni» poziom jego rodzica.
Gª¦boko±¢ (wysoko±¢) drzewa T to maksymalna liczba

w¦zªów w dowolnej gaª¦zi T . Gª¦boko±¢ drzewa jest zatem

o 1 wi¦ksza ni» najwi¦kszy poziom w drzewie.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

9

Drzewa binarne

Przykªad. Rozwa»my poni»sze drzewo binarne.

A

B

C

D

E

F

G

H

I

J

K

L

M

W¦zeª A jest korzeniem drzewa. W¦zªy B i C s¡ dzie¢mi
A

(A jest rodzicem B i C), analogicznie np.: G i H

s¡ dzie¢mi D (D jest rodzicem G i H). W¦zeª L jest

potomkiem mi¦dzy innymi A i B, w¦zeª K jest potomkiem

mi¦dzy innymi A i C. Poziom w¦zªa A wynosi 0, w¦zªów
B

i C jest 1, w¦zªów D, E, F wynosi 2, w¦zªów G, H,

I

, J, K wynosi 3, natomiast w¦zªów L i M wynosi 4.

Gª¦boko±¢ drzewa T jest równa 5.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

10

Zupeªne drzewo binarne

W drzewie binarnym T ka»dy w¦zeª mo»e mie¢ co

najwy»ej dwoje dzieci.

Zatem poziom r drzewa T

mo»e mie¢ maksymalnie 2

r

w¦zªów.

Drzewo binarne

T

nazywamy zupeªnym je»eli wszystkie jego poziomy, z

wyj¡tkiem ostatniego, maj¡ maksymaln¡ mo»liw¡ liczb¦

w¦zªów, natomiast wszystkie w¦zªy ostatniego poziomu

s¡ umieszczone w sposób ci¡gªy od lewej strony.

Drzewo zupeªne, oznaczane przez T

n

, jest jednoznacznie

wyznaczone przez liczb¦ w¦zªów n.
Przykªad. T

12

1

2

3

4

5

7

8

9

10

11

6

12

Uwaga. Przy oznaczeniach jak na powy»szym rysunku,

dzieci w¦zªa o numerze k to 2k i 2k + 1. Numer rodzica

w¦zªa o numerze k to cz¦±¢ caªkowita z k/2.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

11

Notacja polska

Polski matematyk Jan Šukasiewicz zauwa»yª, »e je»eli

zapiszemy symbol operacji binarnej przed jej argumentami,

to do zapisu dowolnego dziaªania nie s¡ potrzebne nawiasy.
Na przykªad:

+ab

zamiast a + b

/cd

zamiast c/d

Rozpatrzmy drzewo operacji X = (a − b)/(c ∗ d + e)

/

−

+

*

b

d

e

c

a

W notacji polskiej X = / − ab + ∗cde.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

12

Przechodzenie drzewa

Przechodzenie drzewa T jest to odwiedzanie w¦zªów T

zgodnie z pewnym algorytmem.
Wyró»niamy trzy standardowe metody przechodzenia

drzewa binarnego T z korzeniem R:

Preorder:

(1) Wypisz korze« R.

(2) Przejd¹ przez lewe poddrzewo R

zgodnie z algorytmem preorder.

(3) Przejd¹ przez prawe poddrzewo R

zgodnie z algorytmem preorder.

Inorder:

(1) Przejd¹ przez lewe poddrzewo R

zgodnie z algorytmem inorder.

(2) Wypisz korze« R.

(3) Przejd¹ przez prawe poddrzewo R

zgodnie z algorytmem inorder.

Postorder: (1) Przejd¹ przez lewe poddrzewo R

zgodnie z algorytmem postorder.

(2) Przejd¹ przez prawe poddrzewo R

zgodnie z algorytmem postorder.

(3) Wypisz korze« R.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

13

Przechodzenie drzewa

Przykªad. Znale¹¢ przej±cie algorytmem preoreder, inorder

i postorder po nast¦puj¡cym drzewie binarnym T .

A

B

C

D

E

F

G

H

I

J

K

L

M

Preorder: ABDGHLEICF JMK

Inorder: GDLHBEIACMJF K

Postorder: GLHDIEBMJKF CA

Porz¡dek li±ci G, L, I, M, K jest zawsze taki sam.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

14

Organizacja uporz¡dkowanych danych

Posortowana tablica A:
Elementy tablicy A umieszczone s¡ w kolejno±ci od

najmniejszego do najwi¦kszego.

Ka»demu elementowi

przypisany jest indeks rozpoczynaj¡c od 0. Zatem pierwszy

element to A[0], drugi A[1], itd.

Je»eli w tablicy

jest n elementów, ostatnim elementem jest A[n − 1].

Wyszukiwanie elementów tablicy jest szybkie. Wstawianie

i kasowanie elementów jest wolne (ka»da z tych operacji

wymaga przesuwania wielu elementów).
Lista poª¡czona (jedno albo dwukierunkowa) L:
Ka»dy z elementów listy, poza swoj¡ warto±ci¡, zawiera

informacj¦ 'gdzie szuka¢' elementu nast¦pnego w kolejno±ci

(lub elementu poprzedniego i nast¦pnego dla listy

dwukierunkowej). Dost¦p do listy zapewnia si¦ podaj¡c

pierwszy element.

Operacje wstawiania i kasowania

elementów listy s¡ szybkie (modykowana jest informacja

'gdzie szuka¢' w elementach s¡siaduj¡cych z miejscem

operacji). Wyszukiwanie elementów jest wolne (wymaga

przej±cia przez elementy od pierwszego do poszukiwanego).

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

15

Binarne drzewa poszukiwa«

Def.

Niech T b¦dzie drzewem binarnym.

Drzewo

T

nazywamy binarnym drzewem poszukiwa« (drzewem

poszukiwa« binarnych, BST), je»eli ka»dy w¦zeª N drzewa
T

ma nast¦puj¡c¡ wªasno±¢:

Warto±¢ w¦zªa N jest wi¦ksza ni» warto±¢ ka»dego

w¦zªa w lewym poddrzewie N oraz jest mniejsza ni»

warto±¢ ka»dego w¦zªa w prawym poddrzewie N.

Je»eli T jest binarnym drzewem poszukiwa«, to przej±cie

algorytmem inorder daje w wyniku posortowany ci¡g

warto±ci w¦zªów drzewa T .
Uwaga. W powy»szym drzewie BST zakªada si¦, »e

wszystkie warto±ci w¦zªów s¡ ró»ne.

Aby dopu±ci¢

powtarzaj¡ce si¦ warto±ci, wprowadza si¦ nast¦puj¡c¡

zmodykowan¡ wªasno±ci ka»dego w¦zªa:

(a) N > M, dla w¦zªów M w lewym poddrzewie N

(b) N ≤ M, dla w¦zªów M w prawym poddrzewie N

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

16

Binarne drzewa poszukiwa«

Algorytm 1. Wyszukiwanie i wstawianie elementów w BST.

Dane: binarne drzewo poszukiwa« T ,

element do znalezienia/wstawienia E.

Krok 1. Porówna¢ E z korzeniem N drzewa T .

(a) Je»eli E < N, przej±¢ do lewego

dziecka T .

(b) Je»eli E > N, przej±¢ do prawego

dziecka T .

Krok 2. Powtarza¢ Krok 1 dopóki:

(a) W¦zeª N = E, poszukiwanie

zako«czone sukcesem, albo

(b) Napotkano puste poddrzewo.

Nie znaleziono E w drzewie T .

Wstawi¢ E w miejsce pustego

poddrzewa.

Krok 3. Koniec.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

17

Binarne drzewa poszukiwa«

Przykªad. Gdzie nale»y wstawi¢ w¦zeª 77 w poni»szym

drzewie BST?

57

39

42

47

26

13

29

34

66

81

74

68

95

Odp. Jako prawe dziecko elementu 74.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

18

Binarne drzewa poszukiwa«

Algorytm 2. Usuwanie elementów z BST.

Dane: binarne drzewo poszukiwa« T ,

element E do usuni¦cia.
P (N )

 rodzic N.

S(N )

 nast¦pnik N (algorytm inorder).

S(N )

nie ma lewego dziecka!

Krok 1. Za pomoc¡ Algorytmu 1 znale¹¢ w¦zeª N,

który zawiera element E.

Krok 2. Rozpatrzy¢ trzy przypadki:

(a) N nie ma dzieci 

usun¡¢ N, zmodykowa¢ P (N).

(b) N ma dokªadnie jedno dziecko M 

usun¡¢ N, oraz

zast¡pi¢ N w P (N) przez M.

(c) N ma dwoje dzieci 

usun¡¢ S(N) za pomoc¡ (a) lub (b),

zast¡pi¢ N przez S(N) w T .

Krok 3. Koniec.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

19

Binarne drzewa poszukiwa«

Przykªad. Opisa¢ algorytm usuwania elementu 26.

57

39

42

47

26

13

29

34

66

81

74

68

95

Przej±cie inorder: 13,26,29,34,39,42,47,57,66,68,74,81,95.

Element 26 ma dwoje dzieci. Nast¦pnik 26 to S(26) = 29.

Usuwamy 29 z drzewa T i podstawiamy w miejsce 26.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

20

Binarne drzewa poszukiwa«

Zªo»ono±¢ obliczeniowa Algorytmu 1 i 2.
Niech T b¦dzie drzewem binarnym o n w¦zªach i

gª¦boko±ci d. Oba algorytmy (wyszukiwanie/wstawianie

oraz usuwanie) zaczynaj¡ od korzenia drzewa i post¦puj¡ w

ka»dym kroku na kolejny poziom drzewa. Oznacza to, »e

liczba operacji wykonywanych w ka»dym z tych algorytmów

zale»y od gª¦boko±ci drzewa T .
Def. Drzewo BST jest drzewem zrównowa»onym, je»eli

gª¦boko±¢ poddrzew dla dowolnego w¦zªa N ró»ni si¦

maksymalnie o 1.
Dla drzewa zrównowa»onego gª¦boko±¢ d ≈ log

2

n

.

Oznacza to, »e wyszukiwanie/wstawianie oraz usuwanie

elementów jest szybkie.
Niestety, nie ma gwarancji, »e drzewo zrównowa»one

pozostanie takim, po wstawieniu dowolnego elementu (w

najgorszym przypadku d ≈ n). Istniej¡ jednak algorytmy,

które po operacji wstawiania sprowadzaj¡ drzewo do drzewa

zrównowa»onego (drzewa czerwono-czarne, drzewa AVL).

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

21