Binary search trees - Data Structures and Problem Solving Using Java - page 708

An AVL tree of height H has at least F H + 3 - 1 nodes, where F i is the i th Fibonacci
number (see Section 7.3.4).

Theorem 19.3

Proof

Let S H be the size of the smallest AVL tree of height H . Clearly, S 0 = 1 and S 1 = 2 .
Figure 19.22 shows that the smallest AVL tree of height H must have subtrees of
height H - 1 and H - 2 . The reason is that at least one subtree has height H - 1 and
the balance condition implies that subtree heights can differ by at most 1 . These
subtrees must themselves have the fewest number of nodes for their heights, so
S H = S H - 1 + S H - 2 + 1 . The proof can be completed by using an induction
argument.

From Exercise 7.8, , where . Conse-
quently, an AVL tree of height H has at least (roughly) nodes.
Hence its depth is at most logarithmic. The height of an AVL tree satisfies

F i ≈ φ

i

⁄ 5 φ = ( 15 + ) ⁄ 2 ≈ 1.618

φ

H 3 +

⁄ 5

H 1.44 < log N 2 ( + ) - 1.328

(19.1)

so the worst-case height is at most roughly 44 percent more than the mini-
mum possible for binary trees.

The depth of an average node in a randomly constructed AVL tree tends
to be very close to log N . The exact answer has not yet been established ana-
lytically. We do not even know whether the form is log N + C or
, for some that would be approximately 0.01. Simula-
tions have been unable to demonstrate convincingly that one form is more
plausible than the other.

The depth of a typi-
cal node in an AVL
tree is very close to
the optimal log N .

( 1 + ε ) log N + C ε

A consequence of these arguments is that all searching operations in an
AVL tree have logarithmic worst-case bounds. The difficulty is that opera-
tions that change the tree, such as insert and remove , are not quite as simple
as before. The reason is that an insertion (or deletion) can destroy the bal-
ance of several nodes in the tree, as shown in Figure 19.21. The balance
must then be restored before the operation can be considered complete. The
insertion algorithm is described here, and the deletion algorithm is left for
Exercise 19.9.

An update in an
AVL tree could
destroy the bal-
ance. It must then
be rebalanced
before the opera-
tion can be consid-
ered complete.

A key observation is that after an insertion, only nodes that are on the
path from the insertion point to the root might have their balances altered
because only those nodes have their subtrees altered. This result applies to
almost all the balanced search tree algorithms. As we follow the path up to
the root and update the balancing information, we may find a node whose
new balance violates the AVL condition. In this section we show how to
rebalance the tree at the first (i.e., the deepest) such node and prove that this
rebalancing guarantees that the entire tree satisfies the AVL property.

Only nodes on the
path from the root
to the insertion
point can have their
balances altered.