Informatyka MIMUW

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

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

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.

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

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.

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