Ćwiczenia | Informatyka MIMUW

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.