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