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

Udowodnij Lemat 1.

Rozwiązanie

..................

Zadanie

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.