STRUKTURY DANYCH

Jak ju» zostaªo wspomniane, do rozwi¡zania ró»nego rodzaju problemów
sªu»¡ odpowiednie algorytmy (które implementujemy przy pomocy ró»nego
rodzaju j¦zyków programowania wy»szego rz¦du).

Do pracy algorytmu  jak dla ka»dego programu komputerowego  niezb¦dne
s¡ struktury danych, przechowuj¡ce niezb¦dne informacje (dane), czyli:

•

dane wej±ciowe problemu,

•

ewentualne dane po±rednie,

•

dane wynikowe (czyli rozwi¡zanie problemu).

W zale»no±ci od charakterystyki rozwi¡zywanego problemu oraz od sposobu
dziaªania danego algorytmu, struktury te s¡ bardziej lub mniej skomp-
likowane.

Najprostsze struktury to tablica i lista.

Tablic¡

okre±lamy zwarty obszar pami¦ci, gdzie ka»da komórka przechowuje infor-
macje okre±lonego typu i do ka»dej z nich jest bezpo±redni dost¦p poprzez
jej indeks.

Zwró¢my uwag¦, »e ka»da komórka tablicy mo»e by¢ pojedyncz¡ warto±ci¡
(np. warto±ci¡ danego elementu w Problemie Podziaªu) lub bardziej skom-
plikowan¡ struktur¡ (np. polem dwuelementowym zawieraj¡cym rozmiar
i warto±¢ konkretnego elementu w Problemie Komiwoja»era, a nawet rozbu-
dowanym zestawem danych osobowych, skªadaj¡cym si¦ z wielu pól ró»nego
typu  ªa«cuchów znaków, liczb, dat, ci¡gów cyfr o okre±lonej strukturze,
itp.).

Zaªó»my, »e w ogólno±ci tablica zawiera n elementów (komórek).

Jaka jest efektywno±¢ podstawowych operacji na takiej strukturze?

Dost¦p do okre±lonego elementu: natychmiastowy, ze wzgl¦du na indekso-
wanie ka»dej komórki tablicy 

O(1)

.

Wyszukanie elementu o okre±lonej warto±ci:

w najgorszym wypadku

b¦dziemy musieli odczyta¢ wszystkie n komórek 

O(n)

.

Wstawienie nowego elementu na okre±lon¡ pozycj¦:
wstawienie nowego elementu na koniec tablicy wymaga po prostu powi¦k-
szenia rozmiaru tablicy o 1 i wpisania warto±ci do ostatniej komórki (zatem
jest to staªa liczba operacji, niezale»na od liczby elementów, czyli

O(1)

),

jednak wstawienie nowego elementu w ±rodek tablicy wymaga powi¦kszenia
rozmiaru tablicy o 1 oraz przesuni¦cia wszystkich elementów le»¡cych na
prawo od wstawianego o 1 pozycj¦ w prawo, czyli w najgorszym wypadku
(wstawienie elementu na pierwsz¡ pozycj¦):
staªa liczba operacji zwi¦kszania rozmiaru tablicy + n przesuni¦¢ + 1 za-
pisanie

= O(1) + O(n) + O(1) = O(n)

.

Usuni¦cie elementu: analogicznie do wstawiania, w najgorszym wypadku
(usuni¦cie pierwszego elementu) trzeba przesun¡¢ n−1 elementów o 1 pozy-
cj¦ w lewo (n − 1 operacji) i zmniejszy¢ rozmiar tablicy o 1 (staªa liczba
operacji) 

O(n)

.

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Odczyt: TAB[2] ?

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Odczyt: TAB[2] = N

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Wyszukanie: TAB[i] = N ?

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Wyszukanie: TAB[i] = N ?

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Wyszukanie: TAB[i] = N ?

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Wyszukanie: TAB[i] = N ? i = 2.

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

N

I

E

G

Usuwanie: TAB[2]

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Usuwanie: TAB[2]

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Usuwanie: TAB[2]

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Usuwanie: TAB[2]

TAB:

[1]

[2]

[3]

[4]

Ś

I

E

G

Usuwanie: TAB[2]

TAB:

[1]

[2]

[3]

[4]

Ś

I

E

G

Wstawianie: TAB[2] = C

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Wstawianie: TAB[2] = C

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Wstawianie: TAB[2] = C

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Wstawianie: TAB[2] = C

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

I

E

G

Wstawianie: TAB[2] = C

TAB:

[1]

[2]

[3]

[4]

[5]

Ś

C

I

E

G

Wstawianie: TAB[2] = C

Lista

jest to struktura wykorzystuj¡ca wska¹niki, gdzie ka»da komórka skªada si¦
z dwóch pól: pola danych (mog¡cego by¢  jak w przypadku tablicy 
rozbudowan¡ struktur¡) oraz wska¹nika na nast¦pny element. Ponadto,
lista musi mie¢ (co najmniej) jedn¡ wyszczególnion¡ komórk¦ zawieraj¡c¡
wyª¡cznie wska¹nik na pierwszy element, tzw. gªow¦.

W porównaniu do tablicy, lista posiada t¦ zalet¦, »e nie musi by¢ zwartym
obszarem pami¦ci. Jakie s¡ zatem koszty takiego rozwi¡zania?

Dost¦p do elementu: je»eli element jest umieszczony na ko«cu listy, to
aby do niego dotrze¢, trzeba przejrze¢ wszystkie pozostaªe n − 1 elementów


O(n)

.

Wyszukanie elementu: jak wy»ej 

O(n)

.

Wstawienie elementu: nale»y utworzy¢ now¡ komórk¦ O(1), wypeªni¢
warto±¢ pola danych O(1), pole wska¹nika wypeªni¢ warto±ci¡ gªowy O(1),
a warto±¢ gªowy wypeªni¢ warto±ci¡ wskazuj¡c¡ na nowy element O(1) 
caªkowity czas omawianej operacji wynosi zatem

O(1)

.

Usuni¦cie elementu: warto±¢ wska¹nika elementu poprzedzaj¡cego nale»y
wypeªni¢ warto±ci¡ wskazuj¡c¡ na element nast¦pny O(n) (trzeba ten wska-
¹nik znale¹¢!) i usun¡¢ z pami¦ci dany element O(1) 

O(n)

.

T

U

J

A

LST:

T

U

J

A

LST:

T

U

J

A

LST:

Odczyt: LST[3] ?

T

U

J

A

LST:

Odczyt: LST[3] ?

T

U

J

A

LST:

Odczyt: LST[3] ?

T

U

J

A

LST:

Odczyt: LST[3] ?

T

U

J

A

LST:

Odczyt: LST[3] = J

T

U

J

A

LST:

Wyszukanie: LST[i] = J ?

T

U

J

A

LST:

Wyszukanie: LST[i] = J ?

T

U

J

A

LST:

Wyszukanie: LST[i] = J ?

T

U

J

A

LST:

Wyszukanie: LST[i] = J ? i = 3.

T

U

J

A

LST:

Usuwanie: LST[3]

T

U

J

A

LST:

Usuwanie: LST[3]

T

U

J

A

LST:

Usuwanie: LST[3]

T

U

J

A

LST:

Usuwanie: LST[3]

T

U

J

A

LST:

Usuwanie: LST[3]

T

U

A

LST:

Usuwanie: LST[3]

T

U

A

LST:

Wstawianie: LST[1] = B

T

U

A

LST:

Wstawianie: LST[1] = B

B

T

U

A

LST:

Wstawianie: LST[1] = B

B

T

U

A

LST:

Wstawianie: LST[1] = B

B

T

U

A

LST:

Wstawianie: LST[1] = B

B

Istniej¡ te» bardziej zaawansowane postaci list:

Lista dwukierunkowa  ka»dy element, oprócz warto±ci i wska¹nika na
nast¦pny element zawiera te» wska¹nik na element poprzedzaj¡cy, a oprócz
gªowy zawiera te» (cho¢ nie jest to konieczne) tzw. ogon, czyli wska¹nik
na ostatni element struktury.
Takie rozwi¡zanie skraca operacje wyszukiwania elementu (a co za tym
idzie  wstawiania i usuwania) w najgorszym wypadku o poªow¦, jednak
z punktu widzenia efektywno±ci to nadal jest zªo»ono±¢ tego samego rz¦du
(

O(n/2) = O(n)

).

Lista cykliczna  wska¹nik ostatniego elementu wskazuje na pierwszy ele-
ment.

K

O

T

Lista dwukierunkowa:

K

O

T

Lista dwukierunkowa cykliczna:

Lista smoorganizuj¡ca si¦ (posortowana)  elementy w strukturze s¡
uporz¡dkowane niemalej¡co lub nierosn¡co (wzgl¦dem warto±ci pól danych).
Ró»nica w stosunku do standardowej listy dotyczy operacji dodawania
elementu  nale»y utworzy¢ now¡ komórk¦ O(1), wypeªni¢ warto±¢ pola
danych O(1), pole wska¹nika wypeªni¢ warto±ci¡ wskazuj¡c¡ na element,
który ma by¢ nast¦pnikiem elementu wstawianego (trzeba znale¹¢ warto±¢
tego wska¹nika, wyszukuj¡c element pierwotnie go poprzedzaj¡cy  O(n)),
pole wska¹nika elementu poprzedzaj¡cego wypeªni¢ warto±ci¡ wskazuj¡c¡
na nowy element O(1) 

O(n)

.

Korzy±ci pojawiaj¡ si¦ w niektórych szczególnych sytuacjach (gdy np. in-
teresuj¡ nas gªównie maksymalne / minimalne elementy).

Zwró¢my uwag¦, »e ide¦ listy mo»na zaimplementowa¢ przy pomocy tablicy.

Realizacja listy za pomocą tablicy:

[1] [2] [3] [4] [5] [6]

Ś N

I

E Ć

6

4

5

1

2

Z kolei poni»ej zaprezentowane struktury mo»na zaimplementowa¢

zarówno za pomoc¡ tablicy, jak i listy.

Kolejka (bufor)

jest struktur¡ typu FIFO (ang.

First In First Out), w której odczyt

nast¦puje tylko z pierwszej pozycji, a wstawienie nowego elementu mo»e
nast¡pi¢ tylko na koniec struktury (za ostatni element).

Zatem dost¦p (pobranie) oraz wstawienie nowego elementu zajmuje

O(1)

czasu, natomiast wyszukanie i usuni¦cie konkretnego elementu 

O(n)

.

Stos

jest struktur¡ typu LIFO (ang. Last In First Out), czyli tak¡, w której
dost¦p (bezpo±redni) jest tylko do pierwszego elementu, a dodanie nowego
nast¦puje przed pierwszy (na pierwsz¡ pozycj¦).

Zatem  tak jak w przypadku kolejki  zªo»ono±¢ operacji dost¦pu (po-
brania) oraz dodania elementu wynosi

O(1)

, natomiast dla wyszukania i

usuni¦cia konkretnego elementu to

O(n)

.

WE

WY

3

Kolejka:

5

11

9

9

0

WE

WY

3

Stos:

5

11

9

9

0

Powy»ej opisane struktury mo»na okre±li¢ jako liniowe i jak zostaªo to
przeanalizowane, ka»da z nich posiada okre±lone wady i zalety.

Generalnie mo»na stwierdzi¢, »e w powy»szych strukturach niektóre pod-
stawowe operacje mo»na wykona¢ w czasie O(1) ale inne w czasie O(n).

Czy mo»na opracowa¢ struktury, w których ka»d¡ z analizowanych operacji
b¦dzie mo»na wykona¢ w czasie mniejszym ni» O(n)?

Rozwa»my struktur¦ inn¡ ni» liniow¡  struktur¦ drzewa.

Ogóln¡ denicj¦ drzewa  jako szczególnego typu grafu  podamy pó¹niej,
przy okazji omawiania teorii grafów. Obecnie opiszemy pewien szczególny
typ drzewa  drzewa ukorzenionego.

Drzewo ukorzenione jest struktur¡ hierarchiczn¡, tzn. ka»dy element posia-
da element(y) podrz¦dny(e) i/lub element nadrz¦dny.

Element nadrz¦dny nazywa si¦ rodzicem, a podrz¦dny potomkiem. Wymo-
giem drzewa jest to, »e ka»dy element mo»e posiada¢ co najwy»ej jednego
rodzica i (w ogólno±ci) dowoln¡ liczb¦ potomków (≥ 0).

W drzewie wyró»niony jest element zwany korzeniem, który nie posiada
rodzica (istnieje dokªadnie jeden taki element).

Z kolei elementy nie posiadaj¡ce potomków zwane s¡ li±ciami.

korzeń

liście

x

rodzic

węzła x

potomek

węzła x

Drzewo

Szczególnym przypadkiem drzewa ukorzenionego jest drzewo binarne, które
charakteryzuje si¦ m.in. tym, »e ka»dy element (nie b¦d¡cy li±ciem) posiada
co najwy»ej dwóch potomków.

Policzmy liczb¦ poziomów,

k

, drzewa binarnego peªnego, tzn. takiego, »e:

•

ka»dy element z wyj¡tkiem li±ci posiada dokªadnie 2 potomków,

•

li±cie znajduj¡ si¦ tylko na ostatnim poziomie.

k = 4 poziomy

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[12]

[13]

[8]

[10]

[14]

[15]

[11]

[9]

n = 15 elementów

Drzewo binarne pełne

Wychodz¡c od spostrze»enia, »e w ka»dym kolejnym poziomie drzewa jest
dwa razy wi¦cej elementów ni» w poprzednim,
liczb¦ wszystkich elementów mo»na wyznaczy¢ jako sum¦ nast. ci¡gu:

2

0

+ 2

1

+ 2

2

+ . . . + 2

k−1

= n.

Korzystaj¡c ze wzoru na sum¦ ci¡gu:

a

0

+ a

0

q + a

0

q

2

+ . . . + a

0

q

n−1

= a

0

1

− q

n

1

− q

,

podstawiaj¡c a

0

= 1

oraz q = 2 otrzymamy:

2

k

− 1 = n.

Korzystaj¡c teraz z denicji logarytmu otrzymamy:

k = log

2

(n + 1),

a zatem

k = O(log n)

.

Szczególnym przypadkiem drzewa binarnego jest

kopiec,

czyli takie drzewo binarne (prawie) peªne, w którym warto±¢ rodzica jest
zawsze nie mniejsza (nie wi¦ksza) od obu potomków (w przypadku ele-
mentu bn/2c i nieparzystej liczby elementów  od jedynego potomka).

Dzi¦ki temu w korzeniu mamy zawsze element maksymalny (minimalny).

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[10]

[9]

12

9

8

7

5

1

2

3

6

4

Kopiec zbudowany z n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}

8 ≥ max {1, 2}

element



n/2



element maksymalny

Dost¦p do elementu: w kopcu mamy dost¦p tylko do korzenia 

O(1)

.

Usuni¦cie (pobranie) elementu: procedura pobrania (pierwszego) ele-
mentu wymaga,

po odczytaniu go z korzenia,

przywrócenia wªa±ciwo±ci kopca.

Polega to na tym, »e ostatni element ze struktury wstawiamy do korzenia
(w miejsce pobranego elementu) i sukcesywnie zamieniamy go z wi¦kszym
z potomków dopóki ten potomek jest wi¦kszy od zamienianego elementu.
Zatem w najgorszym wypadku wykonamy

O(log n)

takich zamian, co stanowi

zªo»ono±¢ obliczeniow¡ caªej procedury.

Wstawienie elementu: nowy element wstawiamy na koniec struktury
i zamieniamy go z rodzicem dopóki rodzic jest mniejszy od wstawionego
elementu 

O(log n)

.

Bior¡c pod uwag¦ powy»sze, utworzenie poprawnego kopca ze zbioru n
losowych warto±ci sprowadza si¦ do n-krotnego wykonania operacji wsta-
wienia elementu 

O(n log n)

.

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[10]

[9]

12

9

8

7

5

1

2

3

6

4

Usunięcie elementu z kopca:

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[10]

[9]

12

9

8

7

5

1

2

3

6

4

Usunięcie elementu z kopca:

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[10]

[9]

9

8

7

5

1

2

3

6

4

Usunięcie elementu z kopca:

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

9

8

7

5

1

2

3

6

Usunięcie elementu z kopca:

4

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

9

8

7

5

1

2

3

6

Usunięcie elementu z kopca:

4

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

4

8

7

5

1

2

3

6

Usunięcie elementu z kopca:

9

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

4

8

7

5

1

2

3

6

Usunięcie elementu z kopca:

9

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

4

5

1

2

3

6

Usunięcie elementu z kopca:

9

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

4

5

1

2

3

6

Usunięcie elementu z kopca:

9

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

5

1

2

3

4

Usunięcie elementu z kopca:

9

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

5

1

2

3

4

Usunięcie elementu z kopca:

9

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

5

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

5

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

8

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

5

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

8

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

8

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

5

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

7

8

6

8

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

5

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

8

8

6

7

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

5

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

8

8

6

7

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

5

[1]

[3]

[2]

[6]

[4]

[7]

[5]

[6]

[4]

[5]

[8]

[9]

8

8

6

7

1

2

3

4

Wstawianie nowego elementu do kopca:

9

8

[10]

5

PODSUMOWANIE

Struktura Dost¦p Wyszukanie Wstawienie Usuni¦cie

Tablica

O(1)

O(n)

O(n)

O(n)

Lista

O(n)

O(n)

O(1)

O(n)

Kolejka

O(1)

O(n)

O(1)

O(n)

Stos

O(1)

O(n)

O(1)

O(n)

Kopiec

O(1)

O(n log n)

O(log n)

O(log n)

•

Kolejka i Stos s¡ strukturami o specycznych zastosowaniach i tylko
dzi¦ki naªo»onym ograniczeniom posiadaj¡ korzystniejsze czasy dost¦pu
lub wstawiania elementu (w stosunku do Tablicy i Listy).

•

Kopiec ma korzystne czasy wstawiania i usuwania elementów w sto-
sunku do pozostaªych struktur (wprawdzie czasy wstawiania dla Listy,
Kolejki i Stosu s¡ szybsze, jednak suma czasów wstawiania i usuwania
jest mniejsza wªa±nie dla Kopca).

•

Kopiec nie jest dobr¡ struktur¡ do wyszukiwania elementów.

Co zrobi¢, aby przyspieszy¢ operacj¦ Wyszukiwania?

Zaawansowane struktury danych

W±ród struktur przeznaczonych do wyszukiwania elementów mo»na wymieni¢

drzewo poszukiwa« binarnych

(ang. Binary Search Tree, czyli drzewo BST), w którym dla ka»dego
w¦zªa, x, musi by¢ speªniony nast¦puj¡cy warunek:

warto±¢ ka»dego elementu le»¡cego w lewym poddrzewie w¦zªa
x

jest nie wi¦ksza ni» warto±¢ w¦zªa x, natomiast warto±¢

ka»dego elementu le»¡cego w prawym poddrzewie w¦zªa x jest
nie mniejsza ni» warto±¢ tego w¦zªa.

7

3

9

1

5

8

12

6

2

4

Przykłady drzew BST dla danych: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}

3

1

4

2

7

9

5

6

8

12

k = 4

k = 7

Zwró¢my uwag¦, »e drzewo BST nie musi by¢ peªne. Zatem jego liczba
poziomów, k, mo»e by¢ wi¦ksza ni» log n (maksymalnie mo»e wynosi¢ n).
Mo»na jednak wykaza¢, »e ±rednia warto±¢

k

dla losowo zbudowanego

drzewa wynosi

O(log n)

.

Dosy¢ ªatwo doj±¢ do tego, »e wyszukanie elementu mo»na wykona¢ w
czasie

O(k)

(zaczynamy w korzeniu i schodzimy pojedyncz¡ ±cie»k¡ w dóª).

Operacje wstawiania i usuwania równie» zajmuj¡

O(k)

operacji (zasada

wstawiania podobna jak przy wyszukiwaniu, usuwania nieco bardziej skom-
plikowana  zob. np. Cormen i in.).

W drzewach BST problemem mo»e by¢ zbyt du»a wysoko±¢ drzewa. Prob-

lem ten mo»na rozwi¡za¢ stosuj¡c

drzewa czerwono-czarne.

S¡ to takie drzewa BST, w których ka»dy w¦zeª posiada dodatkowy para-

metr - kolor, mog¡cy przyjmowa¢ dwie warto±ci: czerwony lub czarny.

Dodatkowo, musz¡ by¢ speªnione nast¦puj¡ce warunki:

•

ka»dy li±¢ (NIL) musi by¢ czarny,

•

oba w¦zªy potomne w¦zªa czerwonego musz¡ by¢ czarne,

•

wszystkie ±cie»ki z danego w¦zªa do li±ci maj¡ tyle samo czarnych

w¦zªów.

Dzi¦ki temu ka»da ±cie»ka w drzewie jest co najwy»ej dwa razy dªu»sza ni»

dowolna inna, co zapewnia, »e drzewo jest w przybli»eniu zrównowa»one,

a jego wysoko±¢ wynosi

O(log n)

.

7

3

9

1

5

8

12

6

2

4

Przykład drzewa czerwono-czarnego

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

Przy okazji zaawansowanych struktur danych warto równie» wspomnie¢ o

tablicach haszuj¡cych.

Sªu»¡ one do efektywnego realizowania operacji sªownikowych (wsta-
wianie, wyszukiwanie, usuwanie).

Zaªó»my, »e mamy zbiór n elementów o okre±lonych warto±ciach. Tablica
haszuj¡ca zbudowana jest typowo z tablicy wska¹ników o rozmiarze

m

(gdzie m ≤ n).

Kluczowym elementem takiej struktury jest funkcja haszuj¡ca

h(k)

zwraca-

j¡ca dla okre±lonego elementu o warto±ci k warto±¢ z zakresu [0, m − 1].

Dodatkowym wymogiem jest, aby funkcja taka byªa deterministyczna, tzn.
zawsze dla elementu o wartosci k musi zwróci¢ t¡ sam¡ warto±¢.

Element, dla którego

h(k) = j

jest umieszczany w li±cie pod indeksem

j

(0 ≤ j < m) tablicy haszuj¡cej.

Oczywi±cie efektywno±¢ tablicy haszuj¡cej ±ci±le zale»y od czasu wyliczania
funkcji haszujacej. Najlepiej, aby byªo to

O(1)

. Prostym przykªadem takiej

funkcji mo»e by¢

h(k) = k

mod m.

Inn¡ wa»n¡ cech¡, jak¡ powinna posiada¢ dobra funkcja haszuj¡ca, jest
równomierne haszowanie, tzn. losowo wybrana warto±¢ ma by¢ z jed-
nakowym prawdopodobie«stwem odwzorowywana na ka»d¡ z m pozycji.

Dzi¦ki równomiernemu haszowaniu, wszystkie listy tablicy haszuj¡cej maj¡
podobn¡ dªugo±¢, co gwarantuje, »e maksymalny czas wykonywania ope-
racji sªownikowych jest mo»liwie krótki (najkrótszy byªby, gdyby wszystkie
listy miaªy identyczn¡ dªugo±¢). Wynika to z faktu, »e nie natramy na
dªug¡ list¦, a jak ju» wiemy  czas powy»szych operacji zale»y wªa±nie od
dªugo±ci listy.

0
1
2
3

Przykładowa tablica haszująca

16

40

36

100

5

38

14

95

99

m = 4; n = 9