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 $⟨F_h⟩$ zgadujemy, że $a_h=Fh+3-1$ (co łatwo sprawdzić przez indukcję) - dlatego $T_h$ noszą nazwę drzew Fibonacciego. Mamy zatem $a_h=\mathrm{\Theta }({\varphi }^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 uaktualniac 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 }^{\prime }(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 }^{\prime }(v)-\mu (v))+1$ jednostek kredytu. Mamy ${\mu }^{\prime }(v)=\mu (w)$ oraz ${\mu }^{\prime }(w)\le {\mu }^{\prime }(v)$.

Na utrzymanie niezmiennika (***) potrzeba
${\mu }^{\prime }(v)+{\mu }^{\prime }(w)-\mu (v)-\mu (w)={\mu }^{\prime }(w)-\mu (v)\le {\mu }^{\prime }(v)-\mu (v)\le 3({\mu }^{\prime }(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 }^{\prime }(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 }^{\prime }(v)=\mu (u)$. Na utrzymanie niezmiennika (***) potrzeba
$\mathrm{\Delta }\mu ={\mu }^{\prime }(v)+{\mu }^{\prime }(w)+{\mu }^{\prime }(u)-\mu (v)-\mu (w)-\mu (u)={\mu }^{\prime }(w)+{\mu }^{\prime }(u)-\mu (v)-\mu (w)=({\mu }^{\prime }(w)-\mu (v))+({\mu }^{\prime }(u)-\mu (w))\le 2({\mu }^{\prime }(v)-\mu (v))$
jednostek kredytu, co pozostawia ${\mu }^{\prime }(v)-\mu (v)$ jednostek na opłacenie wykonania dwóch rotacji. Może się jednak zdarzyć, że ${\mu }^{\prime }(v)=\mu (v)$. Pokażemy, że wtedy $\mathrm{\Delta }\mu <0$, więc utrzymujemy niezmiennik (***), odbierając jednostkę kredytu na opłacenie rotacji.

Przypuśćmy przeciwnie, że ${\mu }^{\prime }(v)=\mu (v)$, ale ${\mu }^{\prime }(v)+{\mu }^{\prime }(w)+{\mu }^{\prime }(u)\ge \mu (v)+\mu (w)+\mu (u)$. Mamy $\mu (u)={\mu }^{\prime }(v)=\mu (v)$, skąd $\mu (w)=\mu (v)=\mu (u)$, więc ${\mu }^{\prime }(v)+{\mu }^{\prime }(w)+{\mu }^{\prime }(u)\ge 3\mu (u)=3{\mu }^{\prime }(v)$, czyli ${\mu }^{\prime }(w)+{\mu }^{\prime }(u)\ge 2{\mu }^{\prime }(v)$. Ponieważ ${\mu }^{\prime }(w),{\mu }^{\prime }(u)\le {\mu }^{\prime }(v)$, to wnioskujemy, że również ${\mu }^{\prime }(w)={\mu }^{\prime }(v)={\mu }^{\prime }(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.