Data Structures, Algorithms, & Applications in Java
Chapter 16, Exercise 15

We shall develop AVLtree as a derived class of the binary search tree class BinarySearchTree. The shortest and simplest codes result from the use of recursion. However, since our primary motivation to use AVL trees is run time efficiency, we shall develop the codes as iterative ones. The codes we develop follow the development in the text very closely. A faster implementation can be obtained by using a head node as the parent of the root and a tail node in place of the null pointer. The use of a parent pointer field in each node will also speed the code.

First we develop a class AVLElement for the elements in the binary search tree tree. This class is a top-level nested class of AVLtree. The code is given below. 
// top-level nested class
static class AVLElement
{
   // data members
   Object element;        // element in node
   int bf;                // balance factor of node

   // constructors
   AVLElement(int theBalanceFactor, Object theElement)
   {
      bf = theBalanceFactor;
      element = theElement;
   }

   AVLElement(Object theElement)
      {element = theElement;}

   /** @return equivalent string suitable for output */
   public String toString()
      {return element.toString();}
}


The code to search for an element invokes the search method for the super class and then extracts the element from the object returned by the super class's search method. 
/** @return element whose key is theKey
  * @return null if there is no element with key theKey */
public Object get(Object theKey)
{
   Object theElement = super.get(theKey);
   if (theElement == null)
      // no matching element
      return null;
   else
      return ((AVLElement) theElement).element;
}


To assist in the development of the code for the insert operation, we first develop methods to adjust balance factors and to perform the different types of rotations needed to restore balance. The method fixBF is used to change the balance factors of nodes on the path form a node q to (but not including) the newly inserted node r. The balance factors of all these nodes were 0 prior to the insertion. theKey is the key of the newly inserted element. It is used to construct the path to the newly inserted node. 
/** set balance factors on path from q to r */
static void fixBF(BinaryTreeNode q, BinaryTreeNode r, Comparable theKey)
{// Balance factors from q to r were originally 0.
 // They need to be changed to +1 or -1.
 // Use theKey to find path from q to r.

   while (q != r)
      if (theKey.compareTo(((Data) q.element).key) < 0)
      {// height of left subtree has increased
         ((AVLElement) ((Data) q.element).element).bf = 1;
         q = q.leftChild;
      }
      else
      {// height of right subtree has increased
         ((AVLElement) ((Data) q.element).element).bf = -1;
         q = q.rightChild;
      }
}


The methods to perform the four different types of rotations are given below. They do the pointer and balance factor changes required by Figures 16.4 (LL rotation), 16.5 (LR rotation), and the corresponding figures for RR and RL rotations (see solution to Exercise 12). 
/** LL rotation around a, pa is parent of a and b is left child of a */
void llRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
   // restructure subtree at A
   a.leftChild = b.rightChild;
   b.rightChild = a;
   if (pa != null)
      // a is not the root
      if (a == pa.leftChild)
         pa.leftChild = b;
      else
         pa.rightChild = b;
   else
      root = b;

   // set balance factors
   ((AVLElement) ((Data) a.element).element).bf = 0;
   ((AVLElement) ((Data) b.element).element).bf = 0;
}

/** RR rotation around a, pa is parent of a and b is right child of a */
void rrRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
   // restructure subtree at a
   a.rightChild = b.leftChild;
   b.leftChild = a;
   if (pa != null)
      // a is not the root
      if (a == pa.leftChild)
         pa.leftChild = b;
      else
         pa.rightChild = b;
   else
      root = b;

   // set balance factors
   ((AVLElement) ((Data) a.element).element).bf = 0;
   ((AVLElement) ((Data) b.element).element).bf = 0;
}

/** LR rotation around a, pa is parent of a and b is left child of a */
void lrRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
   BinaryTreeNode c = b.rightChild;

   // restructure subtree at a
   a.leftChild = c.rightChild;
   b.rightChild = c.leftChild;
   c.leftChild = b;
   c.rightChild = a;
   if (pa != null)
      // a is not the root
      if (a == pa.leftChild)
         pa.leftChild = c;
      else 
         pa.rightChild = c;
   else 
      root = c;

   // set balance factors
   int bfOfC = ((AVLElement) ((Data) c.element).element).bf;
   if (bfOfC == 1)
   {   
      ((AVLElement) ((Data) a.element).element).bf = -1;
      ((AVLElement) ((Data) b.element).element).bf = 0;
   }
   else
      if (bfOfC == -1)
      {
         ((AVLElement) ((Data) a.element).element).bf = 0;
         ((AVLElement) ((Data) b.element).element).bf = 1;
      }
      else
      {// bfOfC = 0
         ((AVLElement) ((Data) a.element).element).bf = 0;
         ((AVLElement) ((Data) b.element).element).bf = 0;
      }
   ((AVLElement) ((Data) c.element).element).bf = 0;
}

/** RL rotation around a, pa is parent of a and b is right child of a */
void rlRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
   BinaryTreeNode c = b.leftChild;

   // restructure subtree at a
   a.rightChild = c.leftChild;
   b.leftChild = c.rightChild;
   c.leftChild = a;
   c.rightChild = b;
   if (pa != null)
      // a is not the root
      if (a == pa.leftChild)
         pa.leftChild = c;
      else 
         pa.rightChild = c;
   else 
      root = c;

   // set balance factors
   int bfOfC = ((AVLElement) ((Data) c.element).element).bf;
   if (bfOfC == 1)
   {   
      ((AVLElement) ((Data) a.element).element).bf = 0;
      ((AVLElement) ((Data) b.element).element).bf = -1;
   }
   else
      if (bfOfC == -1)
      {
         ((AVLElement) ((Data) a.element).element).bf = 1;
         ((AVLElement) ((Data) b.element).element).bf = 0;
      }
      else
      {// bfOfC = 0
         ((AVLElement) ((Data) a.element).element).bf = 0;
         ((AVLElement) ((Data) b.element).element).bf = 0;
      }
   ((AVLElement) ((Data) c.element).element).bf = 0;
}


The code for the insert operation is given below. The first part of the code searches for the place to insert the new element using a process identical to that used to insert an element into an unbalanced search tree. In this part, we also keep track of the most recently seen node whose current balance factor is +1 or -1. Following the insertion, this node is the candidate node for the A = a node around which a rotation (if necessary) is to be performed. The nature of the imbalance (if any) at A is determined, and the appropriate rotation performed. 
/** insert an element with the specified key
  * overwrite old element if there is already an
  * element with the given key 
  * @return old element (if any) with key = theKey */
public Object put(Object theKey, Object theElement)
{
   BinaryTreeNode p = root,     // search pointer
                  pp = null,    // parent of p
                  a = null,     // node with bf != 0
                  pa = null;    // parent of a

   // find place to insert theElement
   // also record most recent node with bf != 0
   // in a and its parent in pa
   Comparable elementKey = (Comparable) theKey;
   while (p != null)
   {// examine p.element.key
      Data pData = (Data) p.element;
      if (((AVLElement) pData.element).bf != 0)
      {// new candidate for a node
         a = p;
         pa = pp;
      }
      pp = p;
      // move p to a child
      if (elementKey.compareTo(pData.key) < 0)
         p = p.leftChild;
      else if (elementKey.compareTo(pData.key) > 0)
              p = p.rightChild;
           else
           {// overwrite element with same key
              Object elementToReturn = ((AVLElement) pData.element).element;
              ((AVLElement) pData.element).element = theElement;
              return elementToReturn;
           }
   }

   // get a node for theElement and attach to pp
   AVLElement q = new AVLElement(0, theElement);
   BinaryTreeNode r = new BinaryTreeNode
                          (new Data(elementKey, q));
   if (root != null)
      // the tree is not empty
      if (elementKey.compareTo(((Data) pp.element).key) < 0)
         pp.leftChild = r;
      else
         pp.rightChild = r;
   else
   {// insertion into empty tree
      root = r;
      return null;
   }

   // see if we must rebalance or simply change balance factors
   if (a != null)
   {// possible rebalancing needed
      Data aData = (Data) a.element;
      if (((AVLElement) aData.element).bf < 0)
         // bf = -1 before insertion
         if (elementKey.compareTo(aData.key) < 0)
         {// insertion in left subtree
            // height of left subtree has increased by 1
            // new bf of a is 0, no rebalancing
            ((AVLElement) aData.element).bf = 0;
            // fix bf on path from a to r
            fixBF(a.leftChild, r, elementKey);
         }
         else
         {// insertion in right subtree
            // bf of a is -2, rebalance
            BinaryTreeNode b = a.rightChild;
            if (elementKey.compareTo(((Data) b.element).key) > 0)
            {// RR case
               fixBF(b.rightChild, r, elementKey);
               rrRotate(pa, a, b);
            }
            else
            {// RL case
               fixBF(b.leftChild, r, elementKey);
               rlRotate(pa, a, b);
            }
         }
      else // bf = +1 before insertion
         if (elementKey.compareTo(aData.key) > 0)
         {// insertion in right subtree
            // height of right subtree has increased by 1
            // new bf of a is 0, no rebalancing
            ((AVLElement) aData.element).bf = 0;
            // fix bf on path from a to r
            fixBF(a.rightChild, r, elementKey);
         }
         else
         {// insertion in left subtree
            // bf of a is +2, rebalance
            BinaryTreeNode b = a.leftChild;
            if (elementKey.compareTo(((Data) b.element).key) < 0)
            {// LL case
               fixBF(b.leftChild, r, elementKey);
               llRotate(pa, a, b);
            }
            else
            {// LR case
               fixBF(b.rightChild, r, elementKey);
               lrRotate(pa, a, b);
            }
         }
   }
   else // a is null, no rebalancing
      fixBF(root, r, elementKey);

   return null;
}


The code to delete an element has two parts. The first part is very similar to the code used to delete an element from an unbalanced binary search tree. That code is augmented by code to save the path from the root to the parent of the physically deleted node. This path is saved on a stack because we will be traversing this path backwards during the resturcturing phase.

The rebalancing code follows the discussion in the text very closely. It also makes use of the fact that the following pairs of rotations are indentical LL and R1, LR and R-1, RR and L-1, and RL and L1. It also uses the fact that LL and R0 and RR and L0 rotations differ only in the final balance factors. See the solution to Exercise 14 for the figures for L0, L1, and L-1 rotations. The L0 and R0 cases would run a bit faster if we remove the code to set the balance factors of a and b from llRotate and rrRotate and insert code at the appropriate places in put and remove to do this. 
/** @return matching element and remove it
  * @return null if no matching element */
public Object remove(Object theKey)
{
   Comparable searchKey = (Comparable) theKey;

   // define a stack to hold path taken from root
   // to physically deleted node
   ArrayStack stack = new ArrayStack();

   // p will eventually to point to node with key theKey
   BinaryTreeNode p = root; // search pointer
   while (p != null && !theKey.equals(((Data) p.element).key))
   {// move to a child of p
      stack.push(p);
      if (searchKey.compareTo(((Data) p.element).key) < 0)
         p = p.leftChild;
      else
         p = p.rightChild;
   }

   if (p == null)
      // no element with key theKey
      return null;

   // save element that will be removed
   Object theElement = ((AVLElement) ((Data) p.element).element).element;

   // restructure tree
   // handle case when p has two children
   if (p.leftChild != null && p.rightChild != null)
   {// p has two children, convert to 0 or 1 child case
      // find largest element in left subtree of p
      stack.push(p);
      BinaryTreeNode s = p.leftChild;
      while (s.rightChild != null)
      {// move to larger element
         stack.push(s);
         s = s.rightChild;
      }

      // move largest from s to p
      ((Data) p.element).key = ((Data) s.element).key;
      ((AVLElement) ((Data) p.element).element).element =
             ((AVLElement) ((Data) s.element).element).element;
      p = s;
   }

   // p has at most one child
   // save child pointer in c
   BinaryTreeNode c;
   if (p.leftChild != null)
      c = p.leftChild;
   else
      c = p.rightChild;

   // delete p
   if (p == root)
      root = c;
   else
      // is p a left or right child?
      if (p == ((BinaryTreeNode) stack.peek()).leftChild)
         ((BinaryTreeNode) stack.peek()).leftChild = c;
      else
         ((BinaryTreeNode) stack.peek()).rightChild = c;

   Comparable pKey = ((Data) p.element).key;
             // pKey may not equal theKey

   // rebalance tree and correct balance factors
   // use stack to retrace path to root
   // set q to parent of deleted node
   BinaryTreeNode q;
   try {q = (BinaryTreeNode) stack.pop();}
   catch (Exception e)
      {return theElement;}  // root was deleted

   while (q != null)
   {
      Data qData = (Data) q.element;
      AVLElement qAVL = (AVLElement) qData.element;
      if (pKey.compareTo(qData.key) <= 0)
      {// node p was deleted from the left subtree of q
         // height of left subtree reduced by 1
         qAVL.bf--;
         if (qAVL.bf == -1)
            // height of q is unchanged, nothing more to do
            return theElement;
         if (qAVL.bf == -2)
         {// q is unbalanced, classify unbalance and rotate
            BinaryTreeNode b = q.rightChild,
                           pa;  // q is a node
                                // pa is parent of a
            try {pa = (BinaryTreeNode) stack.pop();}
            catch (Exception e)
               {pa = null;}     // stack empty
            AVLElement bAVL = (AVLElement) ((Data) b.element).element;
            switch (bAVL.bf)
            {
               case 0:           // L0 imbalance
                  rrRotate(pa, q, b);
                  bAVL.bf = 1;
                  qAVL.bf = -1;  // q is a node
                  return theElement;
               case 1:           // L1 imbalance
                  rlRotate(pa, q, b);
                  break;         // must continue on path to root
               case -1:          // L-1 imbalance
                  rrRotate(pa, q, b);
            }
            q = pa;
         }
         else
            // qAVL.bf is 0
            try {q = (BinaryTreeNode) stack.pop();}
            catch (Exception e)
               {q = null;}     // stack empty
      }
      else
      {// pKey > qData.key
         // deleted from right subtree of q
         // height of right subtree reduced by 1
         qAVL.bf++;
         if (qAVL.bf == 1)
            // height of q is unchanged, nothing more to do
            return theElement;
         if (qAVL.bf == 2)
         {// q is unbalanced
            // classify imbalance and rotate
            BinaryTreeNode b = q.leftChild,
                           pa;  // q is a node
                                // pa is parent of a
            try {pa = (BinaryTreeNode) stack.pop();}
            catch (Exception e)
               {pa = null;}     // stack empty
            AVLElement bAVL = (AVLElement) ((Data) b.element).element;
            switch (bAVL.bf)
            {
               case 0:                // R0 imbalance
                  llRotate(pa, q, b);
                  bAVL.bf = -1;
                  qAVL.bf = 1;        // q is a node
                  return theElement;
               case 1:                // R1 imbalance
                  llRotate(pa, q, b);
                  break;              // must continue on path to root
               case -1:               // R-1 imbalance
                  lrRotate(pa, q, b);
            }
            q = pa;
         }
         else
            // qAVL.bf is 0
            try {q = (BinaryTreeNode) stack.pop();}
            catch (Exception e)
               {q = null;}     // stack empty
      }   
   }     

   return theElement;
}


The elements can be output in ascending order by performing an inorder traversal. The method for this is inherited from the super class BinarySearchTree.

The complexity of get, put, and remove is O(h), where h is the height of the input tree. Since the tree is an AVL tree, its height is O(log n). The ascend operation performs an inorder traversal which takes O(n) time.

All codes, test data, and output can be found in the files AVLtree.*.