« poprzedni punkt   następny punkt »


5. Koszty operacji  na drzewach AVL.
 

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 »