Algorytmy i struktury danych

Algorytmy i struktury danych

wykład 8

 Słowniki 

wykładowca:  Wojciech Folta

Niniejsza prezentacja nie 

wyczerpuje zakresu 

tematycznego przedmiotu: 

„Algorytmy i struktury 

danych” nie stanowi też 

pełnej wiedzy na 

określony temat.

Slajdy prezentacji są 

jedynie uzupełnieniem 

wykładu.

Wojciech Folta

Słownik

to struktura danych 

reprezentująca dynamiczny

(tzn. mogący zmieniać się w czasie)

zbiór elementów (kluczy) 

Na słowniku

można wykonywać następujące operacje: 

-

Find(S,x): zwraca klucz x ze słownika S, 
albo NULL jeśli tego klucza nie ma w 
słowniku;

-

Insert(S,x): wstawia klucz x do słownika 
S;

-

Delete(S,x): usuwa klucz x ze słownika S.

Słownik

implementować można za pomocą 

drzew.

W uniwersum wszystkich 
potencjalnych elementów 
słownika wprowadza się liniowy 
porządek, 
a podstawowym mechanizmem
w zarządzaniu słownikiem jest 
porównywanie kluczy. 

Drzewa BST

Drzewa poszukiwań binarnych

(BST, od ang. Binary Search Tree) 

pesymistyczny koszt 

wymienionych wyżej operacji 

słownikowych

(Find, Insert, Delete)

jest proporcjonalny do wysokości 

drzewa. 

Drzewa BST

Kształt drzewa - więc i jego 

wysokość - zależy od ciągu 

wykonywanych na nim 

operacji. 

Nietrudno podać przykład ciągu 

operacji konstruującego 

drzewo o      węzłach

i wysokości   

Drzewa AVL

(od Adelson-Velskij, Landis) 

do warunku BST umożliwiającego
wyszukiwanie w czasie proporcjonalnym do
wysokości drzewa, dołożono warunek
zrównoważenia, gwarantujący, że wysokość
drzewa zawsze pozostaje logarytmiczna
względem jego rozmiaru:
W każdym węźle wysokości obu jego 

poddrzew różnią się co najwyżej o 1.

Drzewa AVL

W każdym węźle przechowywany jest dodatkowy 

atrybut, 

"współczynnik zrównoważenia", 
przyjmujący wartości:

"-" jeśli lewe poddrzewo jest o 1 wyższe niż prawe;

"0" jeśli oba poddrzewa są takiej samej wysokości;

"+" jeśli prawe poddrzewo jest o 1 wyższe niż 

lewe.

Drzewa AVL

Problem: 

wykonywać wszystkie operacje 
słownikowe na drzewach AVL z 
kosztem co najwyżej 
proporcjonalnym do wysokości 
drzewa 
(czyli logarytmicznym). 

Operacja Find

Operacja Find

jest wykonywana tak samo jak w zwykłych 
drzewach BST: schodzimy w dół drzewa po 
ścieżce od korzenia do szukanego węzła 
(albo do węzła zewnętrznego NULL), o 
wyborze lewego lub prawego poddrzewa 
na każdym poziomie rozstrzygając na 
podstawie porównania szukanego klucza z 
zawartością aktualnego węzła na ścieżce. 

Operacje Insert i Delete

Operacje Insert i Delete

są bardziej skomplikowane, 
ponieważ wymagają aktualizowania 
współczynników zrównoważenia, a 
niekiedy również przywracania 
warunku AVL. 

Rotacje

Do zmiany kształtu drzewa w celu jego 
zrównoważenia służy mechanizm rotacji. 
Po wykonaniu rotacji pojedynczej ROT1  
węzła   z jego ojcem   oba węzły zamieniają 
się rolami ojciec-syn, przy zachowaniu 
własności BST: 

Rotacja podwójna

W rotacji podwójnej ROT2(p,q,r) uczestniczą 

trzy węzły: 

p

, jego ojciec 

q

  i jego dziadek 

r

, 

przy czym albo 

p

 jest lewym synem, a 

q

 

prawym (ten właśnie przypadek rozważamy), 
albo odwrotnie.

Po rotacji 

p

 staje się korzeniem całego drzewa, 

przy zachowaniu własności BST: 

Rotacja podwójna

rotacja podwójna ROT2(p,q,r) jest
w rzeczywistości złożeniem dwóch rotacji 
pojedynczych ROT1(p,q) i ROT1(p,r).
Koszt wykonania jednej rotacji jest stały. 

Wstawianie węzłów w drzewach 

AVL

Podczas operacji Insert tak samo jak dla 

zwykłych drzew BST schodzimy po 
ścieżce od korzenia w dół do węzła 
zewnętrznego NULL i w jego miejscu 
tworzymy nowy liść ze wstawianym 
kluczem. 

Następnie wracamy po ścieżce do 

korzenia, aktualizując współczynniki 
zrównoważenia. 

Wstawianie węzłów w drzewach 

AVL

Jeśli stwierdzamy, że wysokość poddrzewa wzrosła 

(mogła wzrosnąć co najwyżej o 1!), kontynuujemy 

marsz w górę drzewa. Jeśli w wyniku wzrostu 

wysokości jednego z poddrzew aktualnie 

rozważanego węzła został w nim zaburzony 

warunek AVL, to przywracamy go za pomocą 

rotacji. Z dokładnością do symetrii mamy wtedy 

dwa przypadki (w obydwu zakładamy, że 

p

 jest 

węzłem, w którym zaburzony został warunek AVL 

wskutek wzrostu wysokości jego prawego 

poddrzewa o korzeniu 

q

; w pierwszym przypadku 

zakładamy, że wzrosła wysokość prawego 

poddrzewa 

q

, a w drugim - lewego) 

Wstawianie węzłów w drzewach 

AVL

Zauważmy, że w 
obydwu 
przypadkach po 
rotacji 
wysokość 
całego 
poddrzewa jest 
taka sama jak 
przed całą 
operacją, zatem 
wykonanie 
jednej rotacji 
(pojedynczej lub 
podwójnej) 
kończy operację 

Insert.

 

Operację Delete, 

tak samo jak w przypadku usuwania ze 

zwykłego drzewa BST, sprowadzamy 

do przypadku usuwania węzła 

mającego co najwyżej jednego syna. 

Usuwanie węzłów w 

drzewach AVL

W drzewie AVL albo sam węzeł, albo jego 

jedyny syn musi być liściem. Po 
usunięciu węzła wracamy po ścieżce do 
korzenia, aktualizując współczynniki 
zrównoważenia. 

Usuwanie węzłów w 

drzewach AVL

jeśli stwierdzamy, że wysokość poddrzewa 

spadła (mogła spaść co najwyżej o 1!), to 

kontynuujemy marsz w górę drzewa. Jeśli 

w wyniku spadku wysokości jednego z 

poddrzew aktualnie rozważanego węzła 

został w nim zaburzony warunek AVL, to 

przywracamy go za pomocą rotacji. 

Usuwanie węzłów w 

drzewach AVL

Z dokładnością do symetrii mamy wtedy dwa 

przypadki (w obydwu zakładamy, że 

p

 jest 

węzłem, w którym zaburzony został 

warunek AVL wskutek spadku wysokości 

jego lewego poddrzewa, a 

q

 jest 

korzeniem prawego poddrzewa 

p

; w 

pierwszym przypadku zakładamy, że 

współczynnik zrównoważenia w 

q

 przed 

operacja Delete był równy "0" lub "+", a w 

drugim, że "-").

Usuwanie węzłów w 

drzewach AVL

Usuwanie węzłów w 

drzewach AVL

a

Usuwanie węzłów w 

drzewach AVL

a

W pierwszym przypadku, jeśli 

współczynnik zrównoważenia w 

q

 przed 

operacją Delete był równy "0", po 

rotacji wysokość całego poddrzewa jest 

taka sama jak przed całą operacją, 

wykonanie rotacji kończy więc operację 

Delete. Jeśli jednak współczynnik był 

równy "+", wysokość spada o 1. W 

przypadku 2 wysokość całego 

poddrzewa również spada o 1 i trzeba 

kontynuować marsz w stronę korzenia. 

Operacja Delete może zatem wymagać 

wykonania logarytmicznej liczby rotacji. 

Samoorganizujące się 

drzewa BST 

Sleator i Tarjan [ST]

Opisali drzewa splay - czyli drzewa 
BST, w których wykorzystuje się 
rotacje do ich równoważenia, jednak 
nie trzeba przechowywać żadnych 
dodatkowych atrybutów w węzłach. 

Samoorganizujące się 

drzewa BST 

koszt zamortyzowany

operacji słownikowych w tej strukturze 

danych

jest logarytmiczny. 

Procedura splay ( S ,  ) 

przekształca drzewo S w taki sposób, że jego 

korzeniem staje się węzeł z kluczem  

(albo - jeśli klucza  nie ma w S – to w węzeł 

z kluczem najbliższym  ).

Procedura splay ( S ,  ) 

Jeżeli  jest w S:

korzeniem staje się węzeł z kluczem 
 

jeśli klucza  nie ma w S:

węzeł z kluczem y takim, że w S nie 
ma żadnego klucza pomiędzy
min (  , y )  a max (  , y ) 

Procedura splay ( S ,  ) 

Operacja Find ( S ,  )

sprowadza się do wywołania

splay ( S ,  ) 

i sprawdzenia, czy  jest w korzeniu. 

operacja Insert ( S ,  )

 

W celu wykonania Insert( S ,  ) wywołuje się 

najpierw splay( S ,  ), w wyniku czego w korzeniu 

znajduje się klucz 

y

; bez straty ogólności można 

przyjąć, że 

y < 

 . Odcinamy prawe poddrzewo 

R

 

węzła 

y

, jego ojcem (a zarazem nowym korzeniem) 

zostaje węzeł z kluczem 



, którego prawym 

poddrzewem czynimy 

R

. 

operacja 

Delete

 ( S ,  )

 

Operację Delete( S ,  ) zaczynamy od wywołania 
splay( S ,  ), sprowadzając usuwany klucz do 

korzenia. Niech 

L

 i 

R

 będą odpowiednio lewym i 

prawym poddrzewem uzyskanego drzewa. Odcinamy 

korzeń i - jeśli 

L

 jest niepuste - wywołujemy splay(

L

 , 

 ), a następnie przyłączamy 

R

 jako prawe 

poddrzewo korzenia. 

Definicja procedury splay 

( S ,  ) 

Najpierw szukany jest węzeł 

v

 z kluczem  w drzewie 

S

, 

tak jak w zwykłym drzewie BST (jeśli klucza  nie ma 

w drzewie, to jako 

v

 bierzemy ostatni węzeł na 

ścieżce przed węzłem zewnętrznym NULL). 

Następnie, dopóki 

v

 nie stanie się korzeniem, 

wykonujemy sekwencję rotacji zgodnie z poniższym 

schematem: 

• Jeżeli 

v

 jest synem korzenia 

w

, to wykonuje 

ROT1

(v,w)

.

• Jeżeli 

v

 ma ojca 

w

 i dziadka 

u

, przy czym oba węzły i 

są lewymi synami, albo oba prawymi, to wykonujemy 

ROT1

(w,u)

, a następnie ROT1

(v,w)

.  

• Jeżeli 

v

 ma ojca 

w

 i dziadka 

u

, przy czym jeden z 

węzłów 

v

 jest lewym synem, a drugi 

w

 prawym, to 

wykonujemy ROT1

(v,w)

, a następnie ROT1

(v,u)

 (czyli 

w sumie rotację podwójną ROT2 

(v,w,u) 

). 

Definicja procedury splay 

( S ,  ) 

1. Jeżeli 

v

 jest synem korzenia 

w

, to wykonuje 

ROT1

(v,w)

.

2. Jeżeli 

v

 ma ojca 

w

 i dziadka 

u

, przy czym oba 

węzły i są lewymi synami, albo oba prawymi, to 
wykonujemy ROT1

(w,u)

, a następnie ROT1

(v,w)

.  

Definicja procedury splay 

( S ,  ) 

3. Jeżeli 

v

 ma ojca 

w

 i dziadka 

u

, przy czym jeden z 

węzłów 

v

 jest lewym synem, a drugi 

w

 prawym, 

to wykonujemy ROT1

(v,w)

, a następnie ROT1

(v,u)

 

(czyli w sumie rotację podwójną ROT2 

(v,w,u) 

). 

B – drzewa 

Drzewa BST (nawet w wersjach 
zrównoważonych), nie najlepiej nadają się 
do przechowywania na dysku komputera.

 

Specyfika pamięci dyskowej polega na tym, że czas 
dostępu do niej jest znacznie (o kilka rzędów wielkości) 
dłuższy niż do pamięci wewnętrznej (RAM), a odczytu i 
zapisu danych dokonuje się większymi porcjami 
(zwanymi blokami lub stronami). 
Chaotyczne rozmieszczenie węzłów drzewa BST na 
dysku bez brania pod uwagę struktury tego rodzaju 
pamięci prowadzi do większej niż to naprawdę konieczne 
liczby dostępów. 

B – drzewa 

Wynalezione na początku lat 
sześćdziesiątych XX wieku przez:

Bayera i MacCreighta [BM] 

B-drzewa to drzewa poszukiwań 
wyższych rzędów. 

B – drzewa 

W węźle drzewa BST mamy dwa wskaźniki do lewego i prawego syna i 
jeden klucz, który rozdziela wartości przechowywane w lewym i prawym 
poddrzewie.

W węźle drzewa poszukiwań rzędu 

l

 jest 

l

 wskaźników 

do synów 

p

1

, p

2

, ... , p

l

 oraz 

l-1

 kluczy 

k

1

< k

2

< ... < k

l-1

 , 

które rozdzielają elementy poszczególnych poddrzew: 
wartości w poddrzewie wskazywanym przez 

p

i

 muszą 

mieścić się w przedziale otwartym 

(k

i-1

..k

i

)

 dla 

1 



 i 



 l

 

(przyjmując, że 

k

0

=-



 oraz 

k

l

=



 ). 

Rozmiar węzła w B-drzewie dobiera się zwykle tak, aby 
możliwie dokładnie wypełniał on stronę na dysku - pojedynczy 
węzeł może zawierać nawet kilka tysięcy kluczy i wskaźników. 
Zachowanie zrównoważenia umożliwione jest dzięki 
zmiennemu stopniowi wypełnienia węzłów. 

Definicja B – drzewa rzędu m 

(m3)

1. Korzeń jest liściem, albo ma od 

2

 do 

m

 synów.

2. Wszystkie liście są na tym samym poziomie.
3. Każdy węzeł wewnętrzny oprócz korzenia ma 

od 

[m/2]

 do 

m

 synów. Węzeł mający 

l

 synów 

zawiera 

l-1

 kluczy.

4. Każdy liść zawiera od 

[m/2]-1

 do 

m-1

 kluczy.

Definicja B – drzewa rzędu m 

(m3)

Warunki (3) i (4) gwarantują wykorzystanie 
przestrzeni dysku przynajmniej w ok. 50%,
a warunek (2) - niewielką wysokość drzewa 
(w najgorszym razie ok. 

log

m/2

 n/(m/2)

, a w 

najlepszym ok. 

log

m

 n/m) 

dla drzewa 

zawierającego kluczy). 

Definicja B – drzewa rzędu m 

(m3)

Koszt operacji słownikowych na B-
drzewach jest co najwyżej proporcjonalny 
do wysokości drzewa.
Na przykład, można dla 

m = 101

 znaleźć 

jeden spośród miliona kluczy w drzewie 
przy pomocy trzech odwołań do węzłów. 

Przykładowe B – drzewo rzędu 

3

zwane też 2-3 drzewem
(1-2 klucze i 2-3 synów w węźle): 

Operacja Find w B – drzewie

Jest analogiczna jak w drzewach BST. 
Poszukiwanie klucza 



 rozpoczynamy od korzenia.

W aktualnym węźle zawierającym klucze 

k

1

< 

k

2

< ... < k

l-1

 szukamy klucza 

 

(sekwencyjnie lub 

binarnie).
Jeśli to poszukiwanie kończy się niepowodzeniem, 

to albo - jeśli aktualny węzeł jest liściem - klucza 



 w ogóle nie ma w drzewie, albo, mając 

wyznaczony indeks 

i

 o tej własności, że 

k

i-1 

<  < 

k

i

 (przy założeniu, że 

k

0

=-



 oraz 

k

l

=



 ), 

rekurencyjnie poszukujemy klucza 



 w 

poddrzewie o korzeniu wskazywanym przez 

p

i

. 

Operacja Insert ( S , 



 ) w B – 

drzewie

Operacja Insert ( S , 



 ) zaczyna się od 

odszukania (jak w operacji Find) liścia, w 

którym powinien znaleźć się wstawiany klucz. 

Jeśli ten liść nie jest całkowicie wypełniony 

(czyli zawiera mniej niż 

m-1

 kluczy), po prostu 

wstawia się 



 w odpowiednie miejsce w węźle, 

przesuwając część kluczy (koszt tego zabiegu 

jest pomijalnie mały w porównaniu z kosztem 

odczytu i zapisu węzła na dysk).
W przeciwnym razie po dołożeniu nowego 

klucza węzeł jest przepełniony i trzeba 

przywrócić warunek zrównoważenia. 

Operacja Insert ( S , 



 ) w B – 

drzewie

Najpierw próbujemy wykonać przesunięcie kluczy: ta 

metoda daje się zastosować, jeśli któryś z dwóch 

sąsiednich braci przepełnionego węzła (który nie musi 

koniecznie być liściem) ma mniej niż 

m-1

 kluczy. Dla 

ustalenia uwagi przyjmijmy, że jest to lewy brat i 

oznaczmy go przez 

p

, sam przepełniony węzeł przez 

q

, a 

klucz rozdzielający wskaźniki do 

p

 i 

q

 w ich ojcu przez 

k

. 

Klucz 

k

 przenosimy z ojca do 

p

 jako największy klucz w 

tym węźle, w jego miejsce w ojcu przenosimy najmniejszy 

klucz z 

q

, po czym skrajnie lewe poddrzewo 

p

 czynimy 

skrajnie prawym poddrzewem 

q

.

Przesunięcie kluczy w prawo wykonuje się symetrycznie. 
Po takim zabiegu warunki równowagi zostają odtworzone 

i cała operacja się kończy. 

Operacja Insert ( S , 



 ) w B – 

drzewie

Jeśli przepełniony węzeł nie ma niepełnego sąsiada, 

to wykonujemy rozbicie węzła. Listę kluczy dzielimy 

na trzy grupy: 

[m-1]/2

 najmniejszych kluczy, jeden 

klucz środkowy oraz 

[m-1]/2 = [m/2]+1

 największych 

kluczy. Z pierwszej i trzeciej grupy tworzymy nowe 

węzły, a środkowy klucz wstawiamy do ojca (co może 

spowodować jego przepełnienie i konieczność 

kontynuowania procesu przywracania 

zrównoważenia o jeden poziom wyżej) i odpowiednio 

przepinamy poddrzewa. Kiedy następuje 

przepełnienie korzenia, rozbijamy go na dwa węzły i 

tworzymy nowy korzeń mający dwóch synów (to jest 

właśnie powód, dla którego korzeń stanowi wyjątek 

w warunku (3)) - to jest jedyna sytuacja, w której 

wysokość B-drzewa się zwiększa. 

Operacja Delete (S , 



 ) w B – 

drzewie

Operację Delete  również zaczynamy od 

odszukania węzła z kluczem do usunięcia. 

Poddrzewa rozdzielane przez klucz 



 

oznaczmy przez 

p

 i 

q

. 

Tak jak przy usuwaniu z BST, w miejsce 



 

przenosimy - znajdujący się w liściu - 

największy klucz z 

p

 (albo największy z 

q

). 

Lukę po przeniesionym kluczu niwelujemy 

zsuwając pozostałe. Jeśli jest ich co najmniej 

[m/2]-1

, cała operacja jest zakończona, 

natomiast w razie niedoboru w celu 

przywrócenia równowagi musimy dokonać 

przesunięcia kluczy albo sklejenia węzłów. 

Operacja Delete (S , 



 ) w B – 

drzewie

Jeśli któryś z dwóch sąsiednich braci węzła 
z niedoborem ma co najmniej o jeden klucz 
więcej niż dozwolone minimum, to - 
podobnie jak przy wstawianiu - przesuwamy 
skrajny klucz z niego do ojca w miejsce 
klucza rozdzielającego braci, który z kolei 
wędruje do węzła z niedoborem. 

Operacja Delete (S , 



 ) w B – 

drzewie

Niemożność wykonania przesunięcia kluczy 
oznacza, że brat węzła z niedoborem ma 
dokładnie 

[m/2]-1

 kluczy. Sklejamy te dwa węzły 

w jeden, wstawiając jeszcze pomiędzy ich klucze 
klucz rozdzielający z ojca i odpowiednio 
przepinając poddrzewa. Powstaje w ten sposób 
węzeł o 

2*[m/2]-2 



  m-1

 kluczach, a z ojca 

ubywa jeden klucz, co może spowodować w nim 
niedobór i konieczność kontynuowania procesu 
przywracania zrównoważenia wyżej w drzewie. 

Operacja Delete (S , 



 ) w B – 

drzewie

Jeśli korzeń traci swój jedyny klucz, 
usuwamy ten węzeł, a jego jedynego syna 
czynimy nowym korzeniem - to jest jedyna 
sytuacja, w której wysokość B-drzewa 
maleje. 

G. M. Adelson-Velskij, E. M. Landis, An algorithm for 

the organization of information, Soviet Math. 

Doklady 3, 1962, 1259-1263.

R. Bayer, E. M. McCreight, Organization and 

Maintenance of Large Ordered Indexes, Acta 

Informatica 1, 1972, 173-189.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. 

Rivest, Clifford Stein, 'Wprowadzenie do 

algorytmów', WNT, Warszawa 2004.

D.D. Sleator, R.E. Tarjan, Self-Adjusting Binary 

Search Trees, Journal of the ACM 32:3, 1985, 652-

686. Źródło: 

http://wazniak.mimuw.edu.pl/index.php?

title=Algorytmy_i_struktury_danych/Kolejki_prioryte

towe

Literatura