Algorytmy i struktury danych/Słowniki

From Studia Informatyczne

Spis treści

Efektywne słowniki

Słownik to struktura danych reprezentująca dynamiczny (tzn. mogący zmieniac się w czasie) zbiór elementów (kluczy), na którym 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.

W tym module dotyczącym słowników implementowanych za pomocą drzew będziemy zakładali, że uniwersum wszystkich potencjalnych elementów słownika jest liniowo uporządkowane, a podstawowym mechanizmem w zarządzaniu słownikiem będzie porównywanie kluczy.

Drzewa AVL

W drzewach poszukiwań binarnych (BST, od ang. Binary Search Tree) pesymistyczny koszt wymienionych wyżej operacji słownikowych jest proporcjonalny do wysokości drzewa. 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 n węzłach i wysokości \Theta(n). W drzewach AVL (Adelson-Velskij, Landis [AVL]) 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.

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.
Jako ćwiczenie pozostawiamy dowód faktu, że drzewo AVL o n węzłach ma wysokość O(\log n).

Pokażemy teraz, jak wykonywać wszystkie operacje słownikowe na drzewach AVL z kosztem co najwyżej proporcjonalnym do wysokości drzewa (czyli logarytmicznym). 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 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(p,q) węzła p z jego ojcem q oba węzły zamieniają się rolami ojciec-syn, przy zachowaniu własności BST:

grafika:Rot1.png

(symetryczny przypadek, w którym p jest prawym synem q, stanowi lustrzane odbicie powyższego).

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 jest zilustrowany poniżej), albo odwrotnie. Po rotacji p staje się korzeniem całego drzewa, przy zachowaniu własności BST:

grafika:Rot2.png

Nietrudno zauważyć, że 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 i usuwanie 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. Jeśli stwierdzamy, że wysokość aktualnie rozważanego poddrzewa nie zmieniła się w stosunku do sytuacji przed wykonaniem Insert, to kończymy operację, a 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).

grafika:InsertAVL.jpg

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.

Poniższa animacja ilustruje przykładową historię wstawiania do drzewa AVL.




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. Zauważmy, że 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. Jeśli stwierdzamy, że wysokość aktualnie rozważanego poddrzewa nie zmieniła się w stosunku do sytuacji przed wykonaniem Delete, kończymy operację, a 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 pomoca 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 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 "-").

grafika:DeleteAVL.jpg

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. Poniższa animacja ilustruje operację usuwania elementu z drzewa AVL.


Samoorganizujące się drzewa BST

Mechanizm równoważenia drzew AVL jest dość skomplikowany w implementacji i wymaga przechowywania w węzłach dodatkowych informacji. Wynalezione przez Sleatora i Tarjana [ST], opisane poniżej drzewa splay to 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. Chociaż możliwe jest utworzenie niezrównoważonego drzewa splay i pojedyncza operacja może mieć nawet koszt liniowy względem aktualnego rozmiaru drzewa, to koszt zamortyzowany operacji słownikowych w tej strukturze danych jest logarytmiczny.

Wszystkie operacje w drzewie splay są wykonywane z wykorzystaniem pomocniczej procedury splay(S,x), która przekształca drzewo S w taki sposób, że jego korzeniem staje się węzeł z kluczem x (albo - jeśli klucza x nie ma w S - węzeł z kluczem y takim, że w S nie ma żadnego klucza między \min(x,y) a \max(x,y)). Operacja Find(S,x) sprowadza się zatem do wywołania splay(S,x) i sprawdzenia, czy x jest w korzeniu.

W celu wykonania operacji Insert(S,x) wywołujemy najpierw splay(S,x), w wyniku czego w korzeniu znajduje się klucz y; bez straty ogólności możemy przyjąć, że y<x. Odcinamy prawe poddrzewo R węzła y, jego ojcem (a zarazem nowym korzeniem) zostaje węzeł z kluczem x, którego prawym poddrzewem czynimy R.

grafika:Insert_splay.png

Operację Delete(S,x) zaczynamy od wywołania splay(S,x), 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,x), a następnie przyłączamy R jako prawe poddrzewo korzenia.

grafika:Delete_splay.png

Sama procedura splay(S,x) jest zdefiniowana następująco: najpierw szukamy węzła v z kluczem x w S tak jak w zwykłym drzewie BST (jeśli klucza x 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:

1. Jeżeli v jest synem korzenia w, to wykonujemy ROT1(v, w).
2. Jeżeli v ma ojca w i dziadka u, przy czym oba węzły v i w są lewymi synami, albo oba prawymi, to wykonujemy ROT1(w,u), a następnie ROT1(v,w).

grafika:splay2.png.jpg

3. Jeżeli v ma ojca w i dziadka u, przy czym jeden z węzłów v, w jest lewym synem, a drugi prawym, to wykonujemy ROT1(v,w), a następnie ROT1(v,u) (czyli w sumie rotację podwójną ROT2(v,w,u)).

grafika:splay3.jpg

Oto przykład działania procedury splay:



W analizie kosztu zamortyzowanego operacji na drzewach splay posłużymy sie metodą księgowania, z każdym węzłem w drzewie związując pewną liczbę jednostek kredytu. Przez T oznaczmy drzewo o korzeniu x i zdefiniujmy \mu(x) = \lfloor\lg |T|\rfloor (czasem będziemy też używać oznaczenia \mu(T)). Będziemy zachowywali niezmiennik

"Liczba jednostek kredytu w węźle x jest zawsze równa \mu(x)." (***)

Prawdziwy jest
Lemat [Lemat 1]

Do wykonania operacji splay(S,x) z zachowaniem niezmiennika (***) potrzeba co najwyżej 3(\mu(S)-\mu(x))+1 jednostek kredytu.

Żmudny, techniczny dowód lematu pozostawiamy jako ćwiczenie. Z lematu wynika bezpośrednio, że dowolna operacja splay na drzewie rozmiaru n wymaga zużycia O(\lg n) jednostek kredytu, a ponieważ do wykonania operacji Insert i Delete z zachowaniem niezmiennika oprócz tych potrzebnych do wywołań splay potrzeba O(\lg n) dodatkowych jednostek kredytu (na korzeń), wnioskujemy, że koszt zamortyzowany operacji słownikowych na drzewach splay jest logarytmiczny.

B-drzewo - słownik na dysku

Drzewa BST, nawet w takich jak opisane powyżej 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.

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. 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, \ldots, p_l oraz l-1 kluczy k_1< k_2 <\ldots<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\le i\le j (przyjmując, że k_0 = -\infty oraz k_l = \infty). 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. Dokładna definicja B-drzewa rzędu m (m\ge 3) jest następująca:

(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 \lceil m/2\rceil do m synów. Węzeł mający l synów zawiera l-1 kluczy.
(4) Każdy liść zawiera od \lceil m/2\rceil-1 do m-1 kluczy.

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 n kluczy). Ponieważ, jak się zaraz przekonamy, koszt operacji słownikowych na B-drzewach jest co najwyżej proporcjonalny do wysokości drzewa, oznacza to na przykład, że dla m = 101 możemy znaleźć jeden spośród miliona kluczy w drzewie przy pomocy trzech odwołań do węzłów.

Oto przykładowe B-drzewo rzędu 3, zwane też 2-3 drzewem (1-2 klucze i 2-3 synów w węźle):

grafika:Btree_ex.png

Operacja Find w B-drzewie jest analogiczna jak w drzewach BST. Poszukiwanie klucza x rozpoczynamy od korzenia. W aktualnym węźle zawierającym klucze k_1< k_2 <\ldots<k_{l-1} szukamy klucza x (sekwencyjnie lub binarnie). Jeśli to poszukiwanie kończy się niepowodzeniem, to albo - jeśli aktualny węzeł jest liściem - klucza x w ogóle nie ma w drzewie, albo, mając wyznaczony indeks i o tej własności, że k_{i-1}<x<k_i (przy założeniu, że k_0 = -\infty oraz k_l = \infty), rekurencyjnie poszukujemy klucza x w poddrzewie o korzeniu wskazywanym przez p_i.

Operacja Insert(S,x) 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 wstawiamy x 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 będziemy musieli przywrócić warunek zrównoważenia.

Najpierw próbujemy wykonać przesunięcie kluczy: ta metoda daje sie 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.

Jeśli przepełniony węzeł nie ma niepełnego sąsiada, to wykonujemy rozbicie węzła. Listę kluczy dzielimy na trzy grupy: \lceil(m-1)/2\rceil najmniejszych kluczy, jeden klucz środkowy oraz \lfloor(m-1)/2\rfloor = \lceil m/2\rceil-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.



Operację Delete(S,x) również zaczynamy od odszukania węzła z kluczem do usunięcia. Poddrzewa rozdzielane przez klucz x oznaczmy przez p i q. Tak jak przy usuwaniu z BST, w miejsce x 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 \lceil m/2\rceil-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. 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. Niemożność wykonania przesunięcia kluczy oznacza, że brat węzła z niedoborem ma dokładnie \lceil m/2\rceil-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\lceil m/2\rceil-2 \le 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. 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.

Literatura:

[AVL] G. M. Adelson-Velskij, E. M. Landis, An algorithm for the organization of information, Soviet Math. Doklady 3, 1962, 1259-1263.
[BM] R. Bayer, E. M. McCreight, Organization and Maintenance of Large Ordered Indexes, Acta Informatica 1, 1972, 173-189.
[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 'Wprowadzenie do algorytmów', WNT, Warszawa 2004.
[ST] D.D. Sleator, R.E. Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM 32:3, 1985, 652-686.