AVL Trees - a comparison
© Copyright 2002 William A. McKee. All rights reserved.

In 1992, Brad Appleton made a wonderful contribution to the world of C++ teaching with his implementation of the AVL tree algorithm. And, since 1997, he has been offering it on his web site for all to download and study. He used advanced features of C++ such as template classes to make the code highly reusable. There is no faulting his motives or implementation. I only present this alternate implementation in order to give better insight into the nature of the AVL tree algorithm. To download my code, please click here.

Here are some differences in our code.

In my implementation, I did not try to collapse the distinction of "left" and "right" as in Brad's code. Rather, I preferred to keep the distinction so as to help orient the reader and avoid unnecessary syntax.

There is a difference between Brad's implementation and mine in the (re-)balancing algorithm. In Brad's code, he, after showing the advantages of using two separate rotate functions, uses the functions RotateTwice and RotateOnce instead of a single rotate function (actually two, one for rotating left and one for rotating right) and callng it twice in the RL/LR case and only once in the LL/RR case. Furthermore, after rotating, I recursively call the balancing routine again to see if the node (or it's replaced child) requires further balancing. My delete algorithm can leave the tree very out of balance and multiple rotations many be required to put things right.

Brad's code spends a lot of effort keeping track of when the height changes. In my code, I only test and maintain the height information in one place: the (re-)balancing routine. I feel this simplifies the code a great deal even if there is a slight performance penalty.

The other main difference is in the delete routine. I preferred to move the right child of a deleted node to the extreme right most node in the left child's sub-tree. Then, rebalance as many times as necessary to restore balance to the tree.

Also, I use a recursive search algorithm whereas Brad uses an iterative one.

A minor difference in style is that I prefer to return the root of the modified tree from the recursive routines rather than modifying a "root" pointer passed as an argument. This leads to tighter code and (I feel) better demonstrates the recursive nature of the algorithms. Please see the implementation of the Node template class in avltree.h for more details.

The main similarity is that we (re-)balance the sub-tree as the last step in the recursive "insert" and "delete" routines. This is to say that we clean up the tree "on the way up" as we return from each level of the recursion. This is a key point that should be emphasized.

All in all, the code does the same thing by only by looking at the problem from slightly different angles. I thank Brad for his efforts as they obviously help me to better understand the inner workings of the AVL tree algorithm.

To download my code, please click here.