Lecture 10/30/97

o Balance Conditions
o quiz


BALANCED TREES

The idea of balance: Maintain a structural invariant of the tree so that
the depth of the tree is bounded by O(log n).  Requiring perfect balance
is neither necessary desirable.  (Maintaining perfect balance would
require massive work to restructure the tree in the event of an
insertion.)

There are many forms of balanced trees: Height balanced trees, Red-Black
trees, weight balanced trees, etc.  You should understand the basic
idea of height balanced trees.

The idea of height balance: The height of the left and right subtrees
from any node differ by at most 1.

If an AVL tree has height h, what's the minimum number of nodes that it
can have?  Define the minimal size AVL tree of height h to be T(h).

    T(0)   =     o

    T(1)   =     o
                /
               o

    T(2)   =     o
                / \
               o   o
              /
             o

                   o
    T(3)    =     / \
                 /   \
                o     o
               / \   /
              o   o o
             /
            o

Let S(h) be the number of nodes in T(h).
This satisfies the following recurrence:

    S(h) = 1 + S(h-1) + S(h-2)

S(0) = 1
S(1) = 2
S(2) = 4
S(3) = 7
S(4) = 12
...

Let's rewrite the recurrence as:

    (S(h)+1) = (S(h-1)+1) + (S(h-2)+1)

If we define F(h) = S(h)+1, then the recurrence for F is:

    F(h) = F(h-1) + F(h-2)

This is the recurrence for the Fibonacci numbers, which are:
      1 1 2 3 5 8 13 ...

Everybody knows that the fibonacci numbers grow as

   F(h) = Theta (Phi ^ h)

Where Phi = (1+sqrt(5))/2 = 1.618... 

This exponential growth means that in an AVL tree of n nodes, the height
is at O(log n).

MAINTAINING HEIGHT BALANCE

We keep extra information ("balance bits") in each node that tells which
of the three balance conditions hold: left higher, right higher, left
and right equal.

Whenever an update (like an insertion of deletion) occurs, an algorithm
is applied to the tree to rebalance it.  This algorithm uses the balance
bits on the nodes along the path from the root to the change, and
applies ROTATIONS to rebalance the tree, and update the balance bits.
It turns out that under insertion or deletion it is possible to
rebalance the tree in O(log n) time.

There are some examples of this in the book.  You are not required to
remember all the details of this.  You are required to understand the
basic principles as described in these notes.

Rotations are described in detail in the next lecture.