| 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. |
 |
|
| Guestbook | ©
Jose Sandoval 2004-2009 jose@josesandoval.com |