An AVL (Adelson-Velskii and Landis) tree is a binary search tree with a
balance condition.
The balance condition must be easy to maintain, and ensures that the depth of the tree is O(log N).
What does this all mean? The simplest idea is to require that the left and right subtrees have the same height.
Another balance condition would insist that every node must have left and right subtrees of the same height.
If the height of an empty subtree is defined to be -1, then only perfectly balanced trees of 2^k-1 nodes would satisfy the criterion.
Thus, although this guarantees trees of small depth, the balance condition is too rigid to be useful and needs to be relaxed.
An
AVL tree is identical to a binay search tree, except that fo every node in the tree,
the height of the left and right subtrees can differ by at most 1. (The height of an empty tree is defined to be -1.)
Height information is kept fo each node (in the node structure).
It can be shown that the height of an AVL tree is at most roughly
1.44log(N+2) - 1.328,
but in practice it is only slightly more than
log N.
The minimum number of nodes,
S(h), in an AVL tree of height
h is given by
S(h) = S(h -1) + S(h -2) +1. For
h = 0,
S(h) = 1. For
h = 1,
S(h) = 2.
The function
S(h) is closely related to the Fibonacci numbers,
from which the bound claimed above on the height of an AVL tree follows.
Thus, all the tree operations can be preformed in
O(log N) time, except possibly insertion.
When we do an insertion, we need to update all the balancing information for the nodes on
the nodes path back to the root, but the reason that insertion is potentially difficult is that
inserting a node could violate the AVL tree property.
If this is the case, then the property has to be restored before the insertion step is considered over.
It turns out that this can be always be done with a simple modification of the tree, known as a
rotation.
After an insertion, only nodes that are on the path fom the insertion point to the root might have their balance
altered because only those nodes have their subtrees altered.
Let us call the node that must be rebalanced
X.
Since any node has at most two children, and a
height imbalance requires that
X's two subtrees' height differ by two,
it is easy to see that a violation might occur in four cases:
- An insertion into the left subtree of the left child of X.
- An insertion into the right subtree of the left child of X.
- An insertion into the left subtree of the right child of X.
- An insertion into the right subtree of the right child of X.
Cases 1 and 4 are mirror image symmetries with respect to
X, as are cases 2 and 3.
The first case,in which the insertion occurs on the "outside", is fixed by a
single rotation of the tree.
cpp
/*
Rotate Binary tree node with left child.
Update heights, then set new root.
*/
void rotateWithLeftChild( AvlNode * & k2 )
{
AvlNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max( height( k2->left ), height( k2->right ) ) +1;
k1->height = max( height( k1->left ), k2->height ) +1;
k2 = k1;
}
is symmetric.
The second case, in which the insertion occurs on the "inside" is handled by the slightly more complex
double rotation.
cpp
/*
Double rotate binary tree: first left child
with its right child; then node k3 with new left child.
Update heights, then set new root.
*/
void doubleWithLeftChild( AvlNode * & k3 )
{
rotateWithRightChild( k3->left );
rotateWithLeftChild( k3 );
}
is symmetric.
Node declaration for AVL Trees
cpp
struct AvlNode
{
Comparable element; // could be an int
AvlNode *left;
AvlNode *right;
int height;
AvlNode( const Comparable & theElement, AvlNode *lt,
AvlNode *rt, int h = 0 )
: element( theElement ), left( lt ), right( rt ), height( h )
};
A quick function to compute height of an AVL node.
cpp
/*
Return the height of node t or -1 if NULL.
*/
int height( AvlNode *t ) const
{
return t == NULL ? -1 : t->height;
}
The basic insertion routine is easy to right, since it consists mostly of function calls.
cpp
/*
Internal method to insert into a subtree
x is the item to insert
t is the node that roots the subtree
Set the new root of the subtree
*/
void insert( const Comparable & x, AvlNode * & t )
{
if( t == NULL )
t = new AvlNode( x, NULL, NULL );
else if( x < t->element )
{
insert( x, t->left );
if( height( t->left ) - height( t->right ) == 2 )
if( x < t->left->element )
rotateWithRightChild( t );
else
doubleWithLeftChild( t );
}
else if( t->element < x )
{
insert( x, t->right );
if( height( t->right ) - height( t->left ) == 2 )
if( x < t->left->element )
rotateWithRightChild( t );
else
doubleWithLeftChild( t );
}
else
; // Duplicate; do nothing
t->height = max( height( t->left ), height( t->right ) ) + 1;
}
This is just some of the code and it is not a complete project.
The rest of the code should be trivial from this point.
I hope that I have been detailed in my explination of what an
AVL tree is and how to implement some basic functions of one.
If you have any questions/comments/concerns please leave them.
Thanks,
mac0sWizard
AVL tree Tutorial, description of AVL Tree with some basic functions
20 Feb, 2008 - 09:42 PM
|