2115

Twierdzenie.

Wysokość drzewa AVL o n wierzchołkach nie przekracza 1.45 log n = 0(log n).

Dowód:

Jeśli BST ma n wierzchołków, to ma N = n + 1 liści zewnętrznych (pustych poddrzew, czyli odsyłaczy NIL).

Niech N(h) = najmniejsza możliwa liczba liści zewnętrznych w drzewie AVL o wysokości h.

N(0) = 2 N(1) = 3 N(2) = 5,

Fakt: N(h) = N(h-l)+N(h-2)

gdyż minimalne drzewo AVL o wysokości h powstaje z dołączenia do korzenia dwóch minimalnych drzew AVL, o wysokości (h-1) i (h-2), a liczba liści zewnętrznych w tak powstałym drzewie jest sumą liści zewnętrznych w obu poddrzewach.

Zatem:

N(h) = F(h+3), gdzie F(i) jest i-tą liczbą Fibonacciego.

Własność liczb Fibonacciego:

0 ^k'² < F(k) < 0 ^k-¹

gdzie 0 = (1 + V 5)/2 (złoty podział)

Z pierwszej nierówności:

0^h+1 < N(h) => h+1 < log ₀N(h)

= > h < 1.45 log(n+l)-l< 1.45 log n,

QED

Operacja wstawienia elementu do drzewa AVL: