CMPT 225: AVL Trees and Operations

An AVL Tree is a BST that satisfies the following height-balance condition:

For every node v, the heights of the left and right children of v differ by at most one.

(For this definition, we consider an empty tree to be of height -1.)

AVL trees are a kind of self-balancing search tree, meaning that the insertion and removal operations maintain the balance property.

In the following, for simplicity, we assume that keys are all distinct.

insert(k){
   // Inserts key k into T.
   // For simplicity, we assume, that k is new - i.e., is not already present in T.
   // Notice that the algorithm takes advantage of the fact it is 
   //  sufficient to re-balance at most one node.

   insert k using standard BST insert 
   if k is the only key in the tree (it has no parent), return 

   // Find the unbalanced node of greatest depth, if there is one
   v = parent of the new leaf containing k 
   while( v is not the root and is not unbalanced ){
      v = parent(v)
   }

   // Repair the balance property, if necessary
   if( v is unbalanced ){
      rebalance the sub-tree rooted at v using (one or two) rotations 
      // There are four cases, two "inside" and two "outside".
      // Notice that the final height of the sub-tree rooted at v is 
      // the same as its height before the insertion that caused the 
      // unbalance.
   }
}

remove(k){
   // Removes key k from T; 
   // For simplicity, we assume that k does appear in T.
   // Notice that the algorithm relies on two facts:
   //  - removal makes at most one node unbalanced;
   //  - re-balancing a node v may cause an ancestor of 
   //    v to become unbalanced.

   remove k from T using standard BST remove
   if T is empty, return 

   // Observe that, structurally, every AVL-tree removal 
   // amounts to the deletion of a leaf.
   v = parent of the deleted leaf
   for each node u = v..r on the path from v to the root r {
      if( u is unbalanced ){
         S = sub-tree rooted at u
         rebalance S with one or two rotations
         if S did not just get shorter, return 
      }
   }

---