« poprzedni punkt | następny punkt » |
Niech Dh będzie drzewem AVL o wysokości h, które zawiera najmniejszą możliwą liczbę wierzchołków wśród wszystkich wyważonych drzew binarnych poszukiwań. Niech Nh oznacza liczbę wierzchołków w drzewie Dh.
Przykład 5.1
Gdy h=0, to drzewo, które można narysować ma jeden wierzchołek. Zatem N0 = 1. Gdy h=1, można zbudować tylko drzewa o 3 lub o 2 wierzchołkach, zatem N1=2. Na rysunku 8.10 przedstawiono przykładowe drzewa D0-D3. Usunięcie dowolnego wierzchołka w tych drzewach zaburza własność wyważenia, albo powoduje zmniejszenie wysokości. J
Ogólnie, drzewo Dh można przedstawić jako połączenie drzewa Dh-1 o wysokości h-1 z drzewem Dh-2 o wysokości h-2, jak pokazano na rysunku 8.11. Drzewa tego typu nazywa się drzewami Fibonacciego.
Wynika stąd natychmiast, że liczba wierzchołków w drzewie Dh jest sumą liczb wierzchołków jego lewego i prawego poddrzewa zwiększoną o 1 (korzeń drzewa). Mamy zatem
N0 = 1, N1 = 2, Nh = Nh-1 + Nh-2 +1. (*)
Lemat 5.1 Dla dowolnego h ³ 0, minimalną liczbę wierzchołków w wyważonym drzewie binarnych poszukiwań można oszacować przez Nh ³ 2 h/2.
Dowód lematu 5.1 przeprowadzimy przez indukcję ze względu na h. Dla h=0, h=1 nierówność jest spełniona, jak pokazuje przykład 5.1. Załóżmy, że nierówność Ni ³ 2 i/2 jest spełniona dla wszystkich liczb naturalnych i mniejszych niż pewna ustalona liczba h i o szacujmy wartość Nh korzystając z rekurencyjnej definicji (*). Mamy
Nh = Nh-1 + Nh-2 +1 ³ 2 (h-1)/2 + 2 (h-2)/2 + 1 = 2 h/2( 1/2 + Ö2/2 )+1.
Ponieważ (1+ Ö2)/2 ³ 1, więc ostatecznie Nh ³ 2 h/2. J
Jako natychmiastowy wniosek z lematu 5.1 otrzymujemy:
Lemat 5.2 Koszt operacji member, insert i delete dla dowolnego drzewa AVL o n wierzchołkach są rzędu O(lg n).
Rzeczywiście, skoro minimalna liczba wierzchołków w drzewie o wysokości h wynosi Nh, zatem, jeśli n jest liczbą wierzchołków w dowolnym AVL o wysokości h, to n ³ Nh. Z lematu 5.2 mamy więc n ³ 2 h/2. Po zlogarytmowaniu otrzymamy h £ 2lg n. Czyli w dowolnym drzewie AVL, wysokość jest nie większa niż podwojony logarytm z liczby wierzchołków drzewa. Koszt operacji member, insert, delete jest proporcjonalny do wysokości drzewa, w którym te operacje są wykonywane. Stąd oszacowanie złożoności algorytmów dla tych operacji O(lg n).
Pytanie 5: Ile można zbudować różnych drzew AVL o etykietach 1,2,3,4,5,6,7 i wysokości 3?
« poprzedni punkt | następny punkt » |