ASD Ćwiczenia 8

From Studia Informatyczne

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:

grafika:Fib_tree.png

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.