Lecture 13. 



AVL trees are recognized as the first published balanced tree structure. Quoted below from the Wikipedia article on the AVL tree is this tidbit of historical background.
 
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." 
 
Today we looked at an argument to show that the height of an n node AVL tree is O( log n). We then looked at an example of restructuring the tree to retain balance after an insertion.  

Posted: Mon - February 5, 2007 at 11:50 AM          

©