Jose Sandoval Google
 Resume     Book     Software     Drawings     Home Search Web Search
AVL Trees

AVL Trees are binary search trees such that for every internal node v, the height of v's children can differ by at most 1. They also give running time of O(log n) for insertion, deletion and search. For more details, go here.

These things are amazing, and were found by accident some 30 years ago by a couple of researchers (Adelson-Velskii and Landis), the story goes, while trying to device a better data structure for a Chess engine they were working on. They came up with AVL Trees - Self adjusting binary search trees.

This code was part of an assignment in my Algorithms Design class a while back. I've only implemented the insert() method.

If you are looking for code to hand in as part of an assignment, don't use this one. The code may not work as you expect, plus, I already got a mark for it.

© Jose Sandoval 2004-2009