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:

(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:

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).

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 "-").

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 $.

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.

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) $.

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) $).

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

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):

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 $ q $ czynimy skrajnie prawym poddrzewem $ p $. 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.

Ćwiczenia

Zadanie 1

Udowodnij, że wysokość drzewa AVL jest logarytmiczna względem jego rozmiaru.

Rozwiązanie

Pokażemy, że drzewo AVL o wysokości $ h $ musi mieć rozmiar wykładniczy względem $ h $, konstruując drzewo AVL $ T_h $ o wysokości $ h $ i najmniejszym możliwym rozmiarze. Jego definicja jest rekurencyjna:

Oznaczmy rozmiar drzewa $ T_h $ przez $ a_h $. Mamy
$ a_0 = 1 $, $ a_1 = 2 $, $ a_{h+1} = a_h+a_{h-1}+1 $ dla $ h>0 $. Porównując kilka pierwszych wyrazów tego ciągu z początkowymi wyrazami ciągu Fibonacciego $ \langle F_h\rangle $ zgadujemy, że $ a_h = F_{h+3}-1 $ (co łatwo sprawdzić przez indukcję) - dlatego $ T_h $ noszą nazwę drzew Fibonacciego. Mamy zatem $ a_h = \Theta(\phi^h) $.

Zadanie 2

Oblicz, ile jest różnych drzew Fibonacciego o wysokości $ h $.

Rozwiązanie

Jeśli szukaną wielkość oznaczymy przez $ b_h $, to z faktu, że niższe poddrzewo może być zarówno lewe jak i prawe, wynika równanie rekurencyjne: $ b_0 = 1 $, $ b_1 = 2 $, $ b_{h+1} = 2b_h b_{h-1} $. Podstawiając $ c_h = \lg b_h $, mamy $ c_0 = 0 $, $ c_1 = 1 $, $ c_{h+1} = c_h + c_{h-1}+1 $. Zgadujemy, a następnie sprawdzamy przez indukcję, że $ c_h = F_{h+2}-1 $, zatem $ b_h = 2^{F_{h+2}-1} $.

Zadanie 3

Napisz pseudokod operacji Insert i Delete w drzewach AVL.

Zadanie 4

Chcemy, żeby nasz słownik udostępniał dodatkową operację Select(S,k), zwracającą k-ty najmniejszy element w S. Jak zmodyfikować drzewa AVL, żeby pozwalały wykonywac operację Select w czasie logarytmicznym?

Rozwiązanie

W każdym węźle przechowujemy atrybut 'rozmiar poddrzewa'. Taki atrybut można łatwo uaktualniać podczas rotacji i pozwala on na zlokalizowanie k-tego elementu przy pomocy jednego zejścia od korzenia w dół drzewa.

Zadanie 5

Udowodnij Lemat 1.

Rozwiązanie

Niech $ \mu(r) $ i $ \mu'(r) $ oznaczają wartość funkcji $ \mu $ dla węzła $ r $, odpowiednio, przed i po operacji splay. Dalej, niech $ v $, $ w $ i $ u $ oznaczają węzły jak w definicji operacji splay. Rozważamy trzy przypadki, odpowiadające trzem podpunktom w tej definicji.

(1) Węzeł $ u $ nie istnieje, bo $ v $ jest synem korzenia $ w $.
Do wykonania mamy tylko ROT1$ (v, w) $, a do zużycia $ 3(\mu'(v)-\mu(v))+1 $ jednostek kredytu. Mamy $ \mu'(v) = \mu(w) $ oraz $ \mu'(w) \le \mu'(v) $.

Na utrzymanie niezmiennika (***) potrzeba
$ \mu'(v)+\mu'(w)-\mu(v)-\mu(w) = \mu'(w)-\mu(v) \le \mu'(v)-\mu(v) \le 3(\mu'(v)-\mu(v) $
jednostek kredytu. Pozostałą 1 jednostkę przeznaczamy na opłacenie wykonania rotacji.
(2) Oba węzły $ v $ i $ w $ są lewymi synami (albo oba prawymi).

Wykonujemy ROT1$ (w,u) $, a następnie ROT1$ (v,w) $. Pokażemy, że do wykonania tych dwóch rotacji i utrzymania niezmiennika (***) wystarczy $ \le 3(\mu'(v)-\mu(v) $ jednostek kredytu (podobnie jak w przypadku (3)). Sumując to oszacowanie po wszystkich operacjach wykonywanych w ramach procedury splay, dostajemy sumę teleskopową jak w tezie lematu.
Mamy $ \mu'(v) = \mu(u) $. Na utrzymanie niezmiennika (***) potrzeba

$ \Delta\mu = \mu'(v)+\mu'(w)+\mu'(u)-\mu(v)-\mu(w)-\mu(u) = \mu'(w)+\mu'(u)-\mu(v)-\mu(w) = (\mu'(w)-\mu(v)) + (\mu'(u)-\mu(w)) \le 2(\mu'(v)-\mu(v)) $
jednostek kredytu, co pozostawia $ \mu'(v)-\mu(v) $ jednostek na opłacenie wykonania dwóch rotacji. Może się jednak zdarzyć, że $ \mu'(v)=\mu(v) $. Pokażemy, że wtedy $ \Delta\mu < 0 $, więc utrzymujemy niezmiennik (***), odbierając jednostkę kredytu na opłacenie rotacji.

Przypuśćmy przeciwnie, że $ \mu'(v)=\mu(v) $, ale $ \mu'(v)+\mu'(w)+\mu'(u)\ge\mu(v)+\mu(w)+\mu(u) $. Mamy $ \mu(u) = \mu'(v) = \mu(v) $, skąd $ \mu(w) = \mu(v) = \mu(u) $, więc $ \mu'(v)+\mu'(w)+\mu'(u)\ge 3\mu(u) = 3\mu'(v) $, czyli $ \mu'(w)+\mu'(u)\ge 2\mu'(v) $. Ponieważ $ \mu'(w), \mu'(u)\le\mu'(v) $, to wnioskujemy, że również $ \mu'(w) = \mu'(v) = \mu'(u) $. To jednak jest niemożliwe: niech bowiem $ a $ oznacza rozmiar poddrzewa o korzeniu $ v $ przed operacją, zaś $ b $ - rozmiar poddrzewa o korzeniu $ u $ po operacji. Mielibyśmy wówczas równość $ \lfloor \lg a\rfloor = \lfloor \lg (a+b+1)\rfloor = \lfloor \lg b\rfloor $. Załóżmy dla ustalenia uwagi, że $ a\le b $; mamy $ \lfloor \lg (a+b+1)\rfloor\ge\lfloor \lg (2a)\rfloor = 1+\lfloor \lg a\rfloor > \lfloor \lg a\rfloor $, sprzeczność.
(3) Węzeł $ v $ jest lewym synem, a $ w $ prawym, albo odwrotnie. Dowód analogiczny jak w przypadku (2).

Zadanie 6

Opisane tu operacje Insert i Delete dla B-drzew są dwuprzebiegowe: najpierw schodzimy od korzenia do liścia, a następnie wracamy w górę drzewa przywracając warunki równowagi. Zaprojektuj wymagające z grubsza o połowę odwołań do dysku mniej jednoprzebiegowe algorytmy wstawiania i usuwania kluczy z B-drzewa, w których przywracanie równowagi odbywa się od razu podczas marszu w dół drzewa.

Rozwiązanie

Podstawowy pomysł polega na zadbaniu o to, by przy wstawianiu ojciec aktualnego węzła nigdy nie był całkowicie wypełniony, a przy usuwaniu - miał przynajmniej o jeden klucz więcej niż dozwolone minimum. Szczegóły można znaleźć w książce [CLRS], podrozdz. 18.2 i 18.3.

Zadanie 7

Chcemy rozszerzyć nasz zestaw operacji słownikowych o dwie dodatkowe:
Join(S1,S2) łączy dwa słowniki w jeden, przy założeniu, że wszystkie klucze w S1 są mniejsze niż wszystkie klucze w S2;
Split(S,x) dzieli słownik S na dwa słowniki: pierwszy złożony z elementów mniejszych bądź równych x i drugi zlożony z elementów większych od x.
Jak zrealizować te operacje
(a) dla B-drzew;
(b) dla drzew AVL
z kosztem proporcjonalnym do wysokości przetwarzanych drzew?

Rozwiązanie

(a) Join w B-drzewach można zrealizować następująco: Niech h1 i h2 oznaczają wysokości obu drzew; dla ustalenia uwagi załóżmy, że $ h1 > h2 $. Schodzimy w S1 do węzła o wysokości $ h2+1 $, dołączamy S2 jako jego skrajnie prawego syna i poprawiamy zrównoważenie jak przy wstawianiu.

W celu wykonania Split schodzimy do węzła z kluczem $x$, po czym wracamy do korzenia, wykonując Join osobno dla drzew po lewej i po prawej stronie ścieżki. Koszt Join jest w zasadzie proporcjonalny do różnicy wysokości łączonych drzew, więc łączny koszt wyjdzie proporcjonalny do wysokości $S$.
(b) W przypadku AVL idea jest podobna jak poprzednio, ale pojawia się trochę problemów technicznych; szczegółowe rozwiązanie można znaleźć na przykład w książce D. Knutha "Sztuka programowania", WNT 2002, podrozdz. 6.2.3, str. 509.