Notatki do wyk ladu 5

24 marzec 2011

Drzewo binarne – struktura zdefiniowana na sko´

nczonym zbiorze

we

,

z l´

ow, kt´

ora

nie zawiera ˙zadnych we

,

z l´

ow, lub

sk lada sie

,

z trzech roz la

,

cznych zbior´

ow we

,

z l´

ow:

– korzenia

– drzewa binarnego zwanego lewym poddrzewem

– drzewa binarnega zwanego prawym poddrzewem

Drzewo puste (drzewo zerowe) – drzewo binarne, kt´

ore nie ma

˙zadnych we

,

z l´

ow (oznaczane jako sta la NIL)

Je˙zeli w drzewie binarnym we

,

ze l ma tylko jednego syna, to jego

po lo˙zenie ma istotne znaczenie, tj. czy jest on lewym synem,
czy te˙z prawym synem

Regularne drzewo binarne

Regularne drzewo binarne – drzewo, w kt´

orym ka˙zdy z we

,

z l´

ow

jest ba

,

d´

z li´

sciem, ba

,

d´

z ma stopie´

n dwa. Porza

,

dek syn´

ow we

,

z la

odpowiada ich po lo˙zeniu.

Pe lne drzewo

Pe lne drzewo rze

,

du k – drzewo, w kt´

orym wszystkie li´

scie maja

,

te

,

sama

,

g le

,

boko´

s´

c, a wszystkie we

,

z ly wewne

,

trzne maja

,

stopie´

n k

Typeset by

AMS-TEX

1

2

Reprezentowanie drzew ukorzenionych

za pomoca

,

struktur wska´

znikowych

We

,

z ly drzewa reprezentowane sa

,

za pomoca

,

rekord´

ow.

Ka˙zdy

we

,

ze l ma pole klucz oraz pola s lu˙za

,

ce do zapamie

,

tywania wska´

znik´

ow

do innych we

,

z l´

ow.

Drzewa binarne

W ka˙zdym we

,

´

zle drzewa binarnego T pamie

,

tamy wska´

zniki do

ojca oraz lewego i prawego syna w polach p, lef t, right

p[x] = N IL – x jest korzeniem drzewa T

lef t[x] = N IL – we

,

ze l x nie ma lewego syna

right[x] = N IL – we

,

ze l x nie ma prawego syna

root[T ] – atrybut zawieraja

,

cy wska´

znik do korzenia

drzewa

root[T ] = N IL – drzewo puste

Drzewa o dowolnym stopniu rozga le

,

zie´

n

Reprezentacja

na lewo syn, na prawo brat

– root[T ] wskazuje na korze´

n drzewa T

– ka˙zdy we

,

ze l ma pole p wskazuja

,

ce na ojca

– zamiast wska´

znik´

ow do wszystkich syn´

ow ka˙zdy

we

,

ze l x ma dwa wska´

zniki:

1. lef t-child[x] - wskazuje na najbardziej lewego

syna x

3

2. right-sibling[x] - wskazuje na najbli˙zszego,

znajduja

,

cego sie

,

na prawo brata we

,

z la x

– lef t-child[x] = N IL - we

,

ze l x nie ma syn´

ow

– right-sibling[x] = N IL - we

,

ze l x jest najbardziej

wysunie

,

tym na prawo bratem

Twierdzenie 4.

Dowolny algorytm sortuja

,

cy n element´

ow za

pomoca

,

por´

owna´

n w przypadku pesymistycznym wymaga Ω(n lg n)

por´

owna´

n

Sortowanie przez zliczanie

Za lo ˙zenie:

* ka˙zdy z n element´

ow cia

,

gu wej´

sciowego jest liczba

,

ca lkowita

,

z przedzia lu od 0 do k dla pewnego ustalonego ca lkowitego k

Idea:

* dla ka˙zdego elementu x z cia

,

gu wej´

sciowego wyznaczamy

liczbe

,

element´

ow mniejszych od x; w ten spos´

ob otrzymujemy

dok ladna

,

pozycje

,

x w cia

,

gu posortowanym

* je˙zeli dozwolonych jest wie

,

cej element´

ow o tej samej warto´

sci,

to poste

,

powanie to nale˙zy zmodyfikowa´

c aby wszystkie takie

elementy nie trafia ly na te

,

sama

,

pozycje

,

* dane wej´

sciowe zawarte sa

,

w tablicy A[1..n]

* dane posortowane zostaja

,

umieszczone w tablicy B[1..n]

* tablica C[0..k] pocza

,

tkowo wyzerowana przechowuje

tymczasowe dane pomocnicze

4

Algorytm:

– dla ka˙zdego i = 0, 1, . . . , k wyznacz liczbe

,

element´

ow tablicy

A r´

ownych i (C[i] = liczba element´

ow r´

ownych i)

for j

← 1 to n

do C[A[j]]

← C[A[j]] + 1

– dla ka˙zdego i = 0, 1, . . . , k wyznacz liczbe

,

element´

ow tablicy

A mniejszych be

,

d´

z r´

ownych i

for i

← 1 to k

do C[i]

← C[i] + C[i − 1]

– umie´

s´

c wszystkie elementy A[j] na w la´

sciwych pozycjach

w tablicy B

for j

← n downto 1

do B[C[A[j]]]

← A[j]

C[A[j]]

← C[A[j]] − 1

Ca lkowity czas dzia lania, to

Θ(n + k)

Je˙zeli k = O(n), to czas sortowania wynosi Θ(n)