AVL Trees Theory



Definition
            An AVL tree is a binary search tree whose left subtree and right subtree differ in height by no more than 1, and whose left and right subtrees are themselves AVL trees.

To maintain balance in a height balanced binary tree, each node will have to keep an additional piece of information that is needed to efficiently maintain balance in the tree after every insert and delete operation has been performed.  For an AVL tree, this additional piece of information is called the balance factor, and it indicates if the difference in height between the left and right subtrees is the same or, if not, which of the two subtrees has height one unit larger.  If a node has a balance factor rh (right high) it indicates that the height of the right subtree is 1 greater than the height of the left subtree.  Similarly the balance factor for a node could be lh (left high) oreh (equal height).

Example
            Consider the AVL tree depicted below.  The right subtree has height 1 and the left subtree, height 0.  The balance factor of the root is tilted toward the right (right high—rh) since the right subtree has height one larger than the left subtree.  Inserting the new node 21 into the tree will cause the right subtree to have height 2 and cause a violation of the definition of an AVL tree.  This violation of the AVL property is indicated at the root by showing that the balance factor is now doubly unbalanced to the right.  The other balance factors along the path of insertion will also be changed as indicated.


The AVL property of this tree is restored through a succession of rotations.  The root of this tree is doubly unbalanced to the right.  The child of this unbalanced node (node 12) is also rh, but its child (node 24) is lh. Before a rotation around the root can be performed, a rotation around node 24 is required so that the balance factors of both the child and grandchild of the unbalanced node – the root (node 4) – agree in direction (both rhin this case).
Now both nodes 12 and 21 have a balance factor of rh, and a left rotation can be performed about the root.  This rotation will restore AVL balance to the tree.

The left rotation about the root promotes the right child of the original root (node 12), and makes the old root (node 4) the left child of the new root – replacing the left subtree originally attached to node 12.  The former left subtree of node 12 is  now the right subtree of node 4.  In a left rotation, all of the keys in the left subtree of the right child  must be greater than the key of the root and less than the key of the parent.  When the root becomes the left child of the parent, the keys in this subtree remain in the left subtree of the new root and in the right subtree of the new left child.

Worst case height of an AVL tree with n Nodes

            We will examine this question by first considering the minimum number of nodes in an AVL tree of height h.  Consider an AVL tree of height h whose left subtree is of height one less than the height of its right subtree, and assume that this condition is recursively true also for all subtrees

Such an arrangement produces an AVL tree of height h with the minimum number of nodes. 

Let F(h) = the number of nodes in a (min-node) AVL tree of height h.
Then
            F(h) = F(h-1) + F(h-2) + 1       //the number of nodes in the two subtrees plus the root
Where
            F(1) = 2
            F(2) = 4

Add 1 to both sides of this equation.
            F(h) + 1 = F(h-1) +1  + F(h-2) + 1

Let f(h) = F(h) + 1
Then
            f(h) = f(h-1) + f(h-2)
Where
            f(1) = 3,  f(2) = 5

Except for the base case, this is the Fibonacci recurrence relation. 

Try the solution f(h) = ah.   Substitute this value into the recurrence relation and solve for a.

ah – ah-1 – ah-2 = 0

ah-2( a2 – a – 1) = 0

From the quadratic formula we obtain

            a = (1 + √5)/2  and    a = (1 - √5)/2

and

            f(h) = c1((1 + √5)/2)h + c2((1 - √5)/2)h

where
            (1 - √5)/2  » -0.618034  and will always contribute a term of absolute value less than 1 to
                                                   f(h) for any h.

 and using the initial conditions to evaluate c1 and c2, we obtain

            f(h) » ((Ö5 + 2)/Ö5)(( (1 + √5)/2)n

now, taking the log of both sides of this (approximate) equality, and dropping all but the largest terms, we obtain:

            h » 1.44 lg n     where n = éF(h)ù, the number of nodes in the sparsest AVL tree with n nodes.

Note how this result compares with other similar search length results for other binary trees:

            Worst case path length for an AVL tree with n nodes                --         1.44 lg n

            Worst case path length for a red-black tree with n nodes                       --         2 lg n

            Average case path length for a binary search tree with n nodes  --         1.39 lg n

In general the maximum path length from the root to any leaf for an AVL tree will be much closer to lg n (the best case result) for a randomly generated AVL tree.

Post a Comment

Previous Post Next Post