AVL-Template class for C++

Yet another implementation of a balanced AVL tree. I find it’s C++ implementation quite tricky and it took me a while to get it done without any obvious flaws.

Wikipedia states on “AVL trees”:

The AVL tree is named after its two inventors, G.M. Adelson-Velsky and E.M. Landis, who published it in their 1962 paper “An algorithm for the organization of information.”

[…]

While AVL trees are theoretically quite sound, they are not commonly implemented due to their high implementation complexity to keep it balanced, making development less effective when compared to self-correcting tree structures, such as splay trees or heaps. They do, however, perform better than e.g. Red-black trees. They are widely used in academic settings as an instructional data structure.

So if you want to use a self-balancing binary tree structure for your programms and decide to use AVL trees, you may be comfortable with this implementation which can save you the pain of the actual implementation.

• AVL tree implementation (C++)