Lecture 14. 



Continuing with our treatment of AVL trees we saw a very general prescription for performing rebalancing in an AVL tree. We went through an informal analysis of the correctness and computational complexity of an insertion of a node into an AVL that requires rebalancing. We then looked at an example of deleting a node from an AVL tree. Unlike insertion where one rebalancing operation always suffices, deletion of a node may require
O( log n) rebalancing operations.

An applet that can be used to explore AVL trees (as well as other search structures) can be found here. 

Posted: Wed - February 7, 2007 at 11:11 AM          

©