Algorytmy i struktury danych

Wykład 6: Drzewa cz

ęś

ciowo uporz

ą

dkowane

Kopiec binarny

Tablicowa reprezentacja kopca

Przekształcanie tablicy w kopiec metod

ą

wst

ę

puj

ą

c

ą

R.Floyda

Kopiec jako kolejka priorytetowa

Binarne drzewa losowe

Drzepiec binarny

13

25

10

15

2

12

29

20

2

Algorytmy i struktury danych

Drzewo (binarne) jest

zrównowa

ż

one,

je

ż

eli dla ka

ż

dego w

ę

zła

wysoko

ś

ci dwóch jego poddrzew (lewego i prawego) ró

ż

ni

ą

si

ę

co

najwy

ż

ej o 1 (własno

ść

tzw. drzew AVL)

Dla drzewa zrównowa

ż

onego o liczbie w

ę

złów równej

n

ka

ż

da droga

od korzenia do któregokolwiek z w

ę

złów ( w tym li

ś

ci) nie jest dłu

ż

sza

ni

ż

lg n

Drzewa zrównoważone

3

Algorytmy i struktury danych

Drzewa zrównoważone

dane

dane

dane

NULL NULL

dane

NULL NULL

dane

NULL NULL

dane

NULL NULL

dane

NULL NULL

Przykład zrównoważonego drzewa binarnego

dane

dane

4

Algorytmy i struktury danych

Drzewa cz

ęś

ciowo uporz

ą

dkowane

(ang. Partially ordered

tree) s

ą

to drzewa binarne maj

ą

ce nast

ę

puj

ą

c

ą

własno

ść

:

Element przechowywany w w

ęź

le musi mie

ć

co najmniej

(co najwy

ż

ej) tak du

żą

warto

ść

, jak warto

ś

ci nast

ę

pników

tego w

ę

zła

Własno

ść

ta oznacza,

ż

e element w korzeniu dowolnego

poddrzewa jest zawsze najwi

ę

kszym (najmniejszym)

elementem tego poddrzewa

Drzewa częściowo uporządkowane

5

Algorytmy i struktury danych

Przykład drzewa cz

ęś

ciowo uporz

ą

dkowanego

Drzewa częściowo uporządkowane

5

5

NULL

4

2

NULL NULL

1

NULL NULL

3

NULL NULL

6

Algorytmy i struktury danych

Drzewo cz

ęś

ciowo uporz

ą

dkowane jest

zrównowa

ż

one

, je

ż

eli jest

drzewem zrównowa

ż

onym.

9

6

7

5

4

NULL

1

NULL NULL

2

NULL NULL

3

NULL NULL

4

NULL NULL

0

NULL NULL

Drzewa częściowo uporządkowane

7

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

Kopiec



Przykładem drzewa cz

ęś

ciowo uporz

ą

dkowanego mo

ż

e

by

ć

tzw. kopiec (sterta, stóg, zwał), ang. heap



Drzewo binarne jest kopcem je

ż

eli warto

ś

ci

przechowywane w nast

ę

pnikach ka

ż

dego w

ę

zła s

ą

mniejsze od warto

ś

ci w danym w

ęź

le (tzw. kopiec

maksymalny) lub je

ż

eli warto

ś

ci przechowywane w

nast

ę

pnikach ka

ż

dego w

ę

zła s

ą

wi

ę

ksze od warto

ś

ci w

danym w

ęź

le (tzw. kopiec minimalny)



Drzewo jest zrównowa

ż

one, a wszystkie li

ś

cie najni

ż

szego

poziomu znajduj

ą

si

ę

na jego skrajnych, lewych pozycjach

8

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

10

8

7

2

3

6

Przykłady kopców

8

12

10

20

15

Kopiec binarny maksymalny

Kopiec binarny minimalny

9

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

Kopiec mo

ż

na zaimplementowa

ć

bazuj

ą

c na tablicy

jednowymiarowej (wektorze) o długo

ś

ci n

Elementy s

ą

umieszczane w drzewie w kolejnych w

ę

złach od

góry do dołu i od lewej strony do prawej

Uwaga: ka

ż

dy kopiec jest tablic

ą

(ale nie ka

ż

da tablica jest

kopcem)

10

Algorytmy i struktury danych

Cechy charakterystyczne tablicy

A

implementuj

ą

cej kopiec:

Korze

ń

znajduje si

ę

w

A[ 0 ]

Po korzeniu zapisujemy w tablicy kolejne poziomy;

Zatem: lewy nast

ę

pnik korzenia znajduje si

ę

w

A[ 1 ],

prawy nast

ę

pnik korzenia – w

A[ 2 ]

;

Ogólnie: lewy nast

ę

pnik w

ę

zła zapisanego w

A[ i ]

znajduje

si

ę

w

A[ 2i +1]

, prawy nast

ę

pnik – w

A[ 2i+2 ]

(je

ż

eli

nast

ę

pniki istniej

ą

);

Drzewa częściowo uporządkowane

11

Algorytmy i struktury danych

Drzewa częściowo uporządkowane – reprezentacja tablicowa

A[0]

A[1]

A[2]

A[3]

A[4]

A[5]

A[6]

A[0]

A[2]

A[1]

A[3]

A[4]

A[5]

A[6]

12

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

A[(k-1)/2]

A[k]

A[2k+1]

A[2k+2]

nast

ę

pniki k-tego w

ę

zła maj

ą

indeksy

równe:
2k +1 lewy nast

ę

pnik

2k +2 prawy nast

ę

pnik

w

ę

zeł nadrz

ę

dny ma indeks równy

(

k

–1)

/ 2 (dzielenie całkowitoliczbowe)

13

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

10

8

7

2

3

6

tablica A:

6

3

2

7

8

10

5

4

3

2

1

0

]

1

k

2

[

A

]

k

[

A

+

≥

Zachodzi:

oraz

]

2

k

2

[

A

]

k

[

A

+

≥

A[0]

A[2]

A[3]

A[1]

A[4]

A[5]

14

Algorytmy i struktury danych

Drzewa cz

ęś

ciowo uporz

ą

dkowane

Idea algorytmu przekształcania tablicy data[ ] w kopiec metod

ą

wst

ę

puj

ą

c

ą

R. Floyda (1964):

for (i=indeks ostatniego w

ę

zła-nie li

ś

cia; i>=0; i--)

odtwórz warunki kopca dla drzewa, którego korzeniem jest
data[i], wywołuj

ą

c funkcj

ę

MoveDown(data, i, n-1);

Prototyp funkcji MoveDown:

void MoveDown(T data[ ], int first, int last);

15

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

Idea działania funkcji MoveDown (tzw. przesiewanie)

9

25

20

18

10

15

11

6

5

17

19

7

14

16

5

Krok 1

16

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

25

9

20

18

10

15

11

6

5

17

19

7

14

16

5

Krok 2

17

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

25

18

20

9

10

15

11

6

5

17

19

7

14

16

5

Krok 3

18

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

25

18

20

15

10

9

11

6

5

17

19

7

14

16

5

Krok 3

(drzewo jest kopcem)

19

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

void MoveDown(T data[ ], int first, int last)

{

int largest = 2* first +1;

while (largest <= last) {

if (largest < last && data[largest] < data[largest+1] )

largest ++ ;

/* first ma dwa nast

ę

pniki: lewy w 2*first+1 oraz prawy

w 2*first+2, przy czym prawy jest wi

ę

kszy od lewego */

if (data[first] < data[largest]) {

// je

ś

li trzeba zamie

ń

wi

ę

kszy nast

ę

pnik z jego poprzednikiem

zamien(data[first], data[largest]);
first=largest;
largest=2*first+1;

}
else largest=last+1;

// nast

ą

pi wyj

ś

cie z p

ę

tli; poddrzewo jest kopcem

}

}

20

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

Idea przekształcania tablicy A=[ 2 8 6 1 10 15 3 12 11]

w kopiec metod

ą

wst

ę

puj

ą

c

ą

R. Floyda

1

11

12

3

15

10

6

8

2

10

1

12

11

2

6

8

15

3

21

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

1

11

12

3

15

10

6

8

2

10

1

12

11

2

6

8

15

3

Krok 1

ostatni węzeł nie będący liściem:
i = n/2

−−−−

1 = 9/2

−−−−

1 = 3

22

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

12

11

1

3

15

10

6

8

2

10

12

1

11

2

8

Krok 2

ostatni węzeł nie będący liściem:
i = n/2

−−−−

2 = 9/2

−−−−

2 = 2

6

15

3

23

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

12

11

1

3

6

10

15

8

2

12

1

11

2

10

8

Krok 3

ostatni węzeł nie będący liściem:
i = n/2

−−−−

3 = 9/2

−−−−

3= 1

15

6

3

24

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

8

11

1

3

6

10

15

12

2

8

1

11

2

10

12

Krok 4

15

6

3

25

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

11

8

1

3

6

10

15

12

2

11

1

8

2

10

12

Krok 5

15

6

3

26

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

11

8

1

3

6

10

2

12

15

11

1

8

15

10

12

Krok 6

2

6

3

27

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

11

8

1

3

2

10

6

12

15

11

1

8

15

10

12

Kopiec

6

2

3

28

Algorytmy i struktury danych

void Alg_Wst_Floyda( Tab data[ ], int n)

{

int i;

for (i=n/2-1; i>=0; i--)

// utworzenie kopca

MoveDown(Tab, i, n-1);

}

Przekształcanie tablicy w kopiec

(algorytmem wstępującym Floyda)

Program 6.1

29

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

Analiza zło

ż

ono

ś

ci algorytmu przekształcania tablicy

w kopiec (algorytmem wst

ę

puj

ą

cym Floyda)

Rozpatrujemy drzewo binarne o n w

ę

złach i wysoko

ś

ci h

Zachodzi:

n = 2

h

−−−−

1 czyli h = lg (n+1)

Liczba w

ę

złów na ostatnim (h-tym) poziomie drzewa

n

h

= 2

h-1

Zwi

ą

zek pomi

ę

dzy liczba w

ę

złów na i-tym od dołu poziomie drzewa

a liczb

ą

w

ę

złów drzewa n, i=0, 1, 2, ..., h-1

1

i

1

i

1

i

)

1

n

lg(

i

h

1

i

)

1

n

lg(

1

i

h

i

h

2

1

n

lg

2

lg

)

1

n

lg(

1

i

)

1

n

lg(

2

lg

n

lg

2

2

n

+

+

−

−

+

−

−

−

+

−

−

−

+

=

−

+

=

=

−

−

+

=

=

=

=

30

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

1

i

i

h

2

1

n

lg

n

lg

+

−

+

=

Analiza zło

ż

ono

ś

ci algorytmu przekształcania tablicy

w kopiec (algorytmem wst

ę

puj

ą

cym Floyda)

Mamy zatem

czyli

4

1

n

n

1

h

+

=

−

np. dla i=1 (przedostatni poziom); dla i=2 (drugi od dołu poziom)

1

i

i

h

2

1

n

n

+

−

+

=

8

1

n

n

2

h

+

=

−

31

Algorytmy i struktury danych

Drzewa częściowo uporządkowane

Analiza zło

ż

ono

ś

ci algorytmu przekształcania tablicy

w kopiec (algorytmem wst

ę

puj

ą

cym Floyda)

funkcja MoveDown przenosi (w najgorszym razie) dane
z przedostatniego poziomu zawieraj

ą

cego

(n+1)/4

w

ę

złów o jeden

poziom w dół, przeprowadzaj

ą

c

(n+1)/4

zamiany

Dane z drugiego od ko

ń

ca poziomu, który ma

(n+1)/8

w

ę

złów

przenoszone s

ą

o dwa poziomy w dół, co oznacza

2 (n+1)/8

przesuni

ęć

itd. a

ż

do korzenia

Korze

ń

mo

ż

e by

ć

(w najgorszym razie) przeniesiony

o

lg(n+1)

−−−−

1 = lg[(n+1)/2]

poziomy

Ł

ą

czna liczba przesuni

ęć

:

)

n

(

O

1

n

)

5

,

0

5

,

1

)(

1

n

(

]

2

1

2

i

)[

1

n

(

2

1

i

)

1

n

(

)

1

i

(

2

1

n

)

1

n

lg(

2

i

i

)

1

n

lg(

2

i

i

)

1

n

lg(

2

i

i

)

1

n

lg(

2

i

i

=

+

=

−

+

=

−

+

=

=

−

+

=

−

+

∑

∑

∑

∑

+

=

+

=

+

=

+

=

32

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Kopiec może być podstawą bardzo efektywnej implementacji kolejki
priorytetowej;

Aby wstawić element do kolejki dodaje się go na koniec jako ostatni liść
(należy wówczas najczęściej odtworzyć własność kopca);

Pobieranie elementu z kolejki polega na pobraniu wartości z korzenia; na
jego miejsce przesuwany jest ostatni liść (najczęściej trzeba potem
odtworzyć własność kopca);

33

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Idea algorytmu wstawiania elementu do kolejki:

Wstaw_Do_Kolejki_Kopca(elm) {

wstaw elm na koniec kopca;
while (elm nie jest korzeniem && elm > poprzednik(elm))

zamień miejscami elm i poprzednik(elm);

}

34

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Idea algorytmu wstawiania elementu do kolejki-kopca

25

18

20

9

10

17

19

7

14

16

Należy dodać do kolejki wartość 22

22

35

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Przywracanie własności kopca

25

18

20

9

10

17

19

7

14

16

22

36

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Kopiec z dodanym elementem

25

18

22

9

10

17

20

7

14

16

19

37

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Idea algorytmu pobierania elementu z kolejki:

Pobierz_Z_Kolejki_Kopca() {

pobierz element z korzenia;
wstaw do korzenia element z ostatniego liścia;
usuń ostatni liść;

// lewe i prawe poddrzewo są kopcami

p=korzeń;
while (p nie jest liściem && p < którykolwiek następnik(p))

zamień miejscami p i większy następnik(p);

}

Ostatnie trzy wiersze algorytmu to przywracanie drzewu własności kopca
(realizuje to funkcja MoveDown)

38

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Idea algorytmu pobierania elementu z kolejki

25

18

22

9

10

17

20

7

14

16

19

39

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Zastąpienie korzenia ostatnim liściem

19

18

22

9

10

17

20

7

14

16

40

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Przywrócenie własności kopca

19

18

22

9

10

17

20

7

14

16

41

Algorytmy i struktury danych

Kopiec jako kolejka priorytetowa

Kolejka z usuniętym elementem o najwyższym priorytecie

22

18

20

9

10

17

19

7

14

16

42

Algorytmy i struktury danych

Losowe drzewa BST

Losowe drzewo BST o

n

warto

ś

ciach (kluczach) – drzewo BST, które

powstaje z drzewa pustego w wyniku wstawienia warto

ś

ci (kluczy) w

losowej kolejno

ś

ci, przy zało

ż

eniu,

ż

e ka

ż

da z

n!

permutacji tych

warto

ś

ci jest jednakowo prawdopodobna;

Mo

ż

na pokaza

ć

,

ż

e oczekiwana wysoko

ść

losowego drzewa BST

o

n

kluczach wynosi

lg n

, tzn.

E[H] = lg n

;

Losowe drzewo BST ma tendencj

ę

bycia zrównowa

ż

onym;

43

Algorytmy i struktury danych

Drzepce

Drzepiec (ang. treap) – drzewo BST, w którym porz

ą

dek

wstawiania elementów okre

ś

lany jest w pewien specjalny sposób;

W ka

ż

dym w

ęź

le drzepca, oprócz pola warto

ś

ci wyst

ę

puje pole

priorytet, którego warto

ś

ci

ą

jest losowo okre

ś

lana liczba,

niezale

ż

nie dla ka

ż

dego w

ę

zła (przy zało

ż

eniu,

ż

e wszystkie

warto

ś

ci i wszystkie priorytety s

ą

ró

ż

ne);

Elementy (w

ę

zły) w drzepcu s

ą

uporz

ą

dkowane w taki sposób,

ż

e

warto

ś

ci (klucze) spełniaj

ą

kryteria drzewa BST, natomiast

priorytety

spełniaj

ą

własno

ść

kopca

minimalnego,

tj. z najmniejszym priorytetem w korzeniu;

Drzepiec jest zatem poł

ą

czeniem drzewa BST i kopca (st

ą

d

nazwa:

drze

wo BST + ko

piec

)

44

Algorytmy i struktury danych

Drzepce

Pomocne jest, aby my

ś

le

ć

o drzepcach w nast

ę

puj

ą

cy sposób:



załó

ż

my,

ż

e wstawiamy do drzepca w

ę

zły x

1

, x

2

, ..., x

n

wraz ze

zwi

ą

zanymi z nimi warto

ś

ciami (kluczami);



aby otrzyma

ć

drzepiec wstawiamy te w

ę

zły w kolejno

ś

ci

wyznaczonej przez ich (losowo ustalone) priorytety, tzn. x

i

jest

wstawiany przed x

j

, je

ż

eli priorytet( x

i

) < priorytet( x

j

)

45

Algorytmy i struktury danych

Drzepce

G / 4

G/ 4

A /10

E / 23

K / 65

B / 7

H / 5

I / 73

Przykład drzepca

priorytet

wartość węzła

(klucz)

46

Algorytmy i struktury danych

Drzepce

G / 4

G/ 4

A /10

E / 23

K / 65

B / 7

H / 5

I / 73

Idea algorytmu wstawiania węzła do drzepca

C / 25

G / 4

G/ 4

A /10

E / 23

K / 65

B / 7

H / 5

I / 73

C / 25

47

Algorytmy i struktury danych

Drzepce

Idea algorytmu wstawiania węzła do drzepca

D / 9

G / 4

G/ 4

A /10

E / 23

K / 65

B / 7

H / 5

I / 73

C / 25

G / 4

G/ 4

A /10

E / 23

K / 65

B / 7

H / 5

I / 73

D / 9

C / 25

D / 9

48

Algorytmy i struktury danych

Drzepce

Idea algorytmu wstawiania węzła do drzepca

G / 4

G/ 4

A /10

E / 23

K / 65

B / 7

H / 5

I / 73

D / 9

C / 25

G / 4

G/ 4

A /10

K / 65

B / 7

H / 5

I / 73

C /25

E /23

D /9

49

Algorytmy i struktury danych

Drzepce

Idea algorytmu wstawiania węzła do drzepca

G / 4

G/ 4

A /10

K /65

B / 7

H / 5

I /73

C /25

E /23

D / 9

F / 2

F / 2

G/ 4

A /10

H / 5

B / 7

G / 4

K /65

C /25

E /23

D / 9

I /73

. . . ?

50

Algorytmy i struktury danych