ASD Ćwiczenia 8

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)\leq \mu '(v)$.

Na utrzymanie niezmiennika (***) potrzeba
$\mu '(v)+\mu '(w)-\mu (v)-\mu (w)=\mu '(w)-\mu (v)\leq \mu '(v)-\mu (v)\leq 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 $\leq 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))\leq 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)\geq \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)\geq 3\mu (u)=3\mu '(v)$, czyli $\mu '(w)+\mu '(u)\geq 2\mu '(v)$. Ponieważ $\mu '(w),\mu '(u)\leq \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\leq b$; mamy $\lfloor \lg(a+b+1)\rfloor \geq \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.