Section 6 - Implementing Removal

5A.6.1 Removal

Removal is treated exactly like insertion -- it is not harder and no easier. We developed a general approach with our development of the mythical remsert() algorithm, and it works just fine for removing a node. We copy the remove() method from the simple BST template, then make the appropriate adjustments. Dust off your FHsearch_tree::remove() and place it in a nearby window so you can see the basis of the AVL version.

Here is the result, followed by some discussion.

template <class Comparable>
bool FHavlTree<Comparable>::remove( const Comparable & x, FHs_treeNode<Comparable> * & root )
{
   if (root == NULL)
      return false;

   if (x < root->data)
   {
      if ( !remove(x, root->lftChild) )
         return false;

      // rebalance - shortened left branch so right may now be higher by 2
      if(heightOf(root->rtChild) - heightOf(root->lftChild) == 2)
         if(heightOf(root->rtChild->rtChild) < heightOf(root->rtChild->lftChild))
            doubleWithRightChild(root);
         else
            rotateWithRightChild(root);
   }
   else if (root->data < x)
   {
      if ( !remove(x, root->rtChild) )
         return false;

      // rebalance - shortened right branch so left may now be higher by 2
      if(heightOf(root->lftChild) - heightOf(root->rtChild) == 2)
         if(heightOf(root->lftChild->lftChild) < heightOf(root->lftChild->rtChild))
            doubleWithLeftChild(root);
         else
            rotateWithLeftChild(root);
   }

   // found the node
   else if (root->lftChild != NULL && root->rtChild !=NULL)
   {
      // first simply copy min right data into the node marked for deletion
      FHs_treeNode<Comparable> *minNode = findMin(root->rtChild);
      root->data = minNode->data;

      // now we do a real deletion:  the old min is still in the right sub-tree
      remove(minNode->data, root->rtChild);

      // rebalance - shortened right branch so left may now be higher by 2
      if(heightOf(root->lftChild) - heightOf(root->rtChild) == 2)
         if(heightOf(root->lftChild->lftChild) < heightOf(root->lftChild->rtChild))
            doubleWithLeftChild(root);
         else
            rotateWithLeftChild(root);
   }
   else
   {
      // no rebalancing needed at this external (1+ NULL children) node
      FHs_treeNode<Comparable> *nodeToRemove = root;
      root = (root->lftChild != NULL)? root->lftChild : root->rtChild;
      delete nodeToRemove;
      return true;

   }
   // successfully removed and rebalanced at this and lower levels; now adjust height
   root->setHeight( max(heightOf(root->lftChild), heightOf(root->rtChild)) + 1);
   return true;
}

A short glance at the precursor BST version reveals that we are mimicking it step-for-step.

Perfunctory Observation:

Some of the if statements have been converted to if/else if. That's because, in the earlier incarnation with BST structures, the if statements' bodies were simple return statements, making what came after a de facto else. Now, though, we need the else, because we cannot return instantly - we have a final pièce de résistance, namely the adjustment of the current root's height.

Deeper Observations:

Again, if we recurse, we rebalance, and only then. The difference between remove() and insert(), though, is that the place where the action happens can cause a shortening, not lengthening of the height. This difference is an easy one to accommodate: If we remove from the left child of k₃ , we have to check whether the right subtree suddenly is too tall. Therefore, the potentially too tall X subtree is not on the side of the removal, but on the opposite side: If we removed from the left, our potentially too-tall X would be on the right, and vice versa. This is reflected in the following code, which removes from the left, but checks to see if the right sub-tree is too tall:
```
   if ( !remove(x, root->lftChild) )
      return false;

   // rebalance - shortened left branch so right may now be higher by 2
   if(heightOf(root->rtChild) - heightOf(root->lftChild) == 2)
      // etc ...  
```

Continuing the same case (removal from the left sub-tree), we now look at the right sub-tree which we will say is, in fact, too long for our taste (the difference is == 2). We want to shorten it. If the right subtree is longer on its right, then we have right-right situation, and use single right rotation. If the right subtree is longer on its left, then we have a right-left situation, and use right double rotation:
```
   if(heightOf(root->rtChild->rtChild) < heightOf(root->rtChild->lftChild))
      doubleWithRightChild(root);
   else
      rotateWithRightChild(root);
```

What if they are equal? As you can see from the logic, if the two sub-trees of the right child have the same height, we are doing a single right rotation. Actually, it doesn't matter - either will fix it, but the single is faster. This situation doesn't come about in insertion, since an insertion creates a brand new imbalance and it always results in a unique subtree being suddenly taller. However, when we remove a node, we have to look a its sibling's subtree, and there may easily be two branches of that subtree which are equally too long. Again, it doesn't matter in this case, although you'll have to convince yourself of this fact with pencil and paper.

5A.6.2 Full Coding

We will not do the complete coding of AVL trees today. This has been a day for understanding the concepts and details of both the rotations and insert/delete algorithms that will be used in AVL trees. This is 90% of the work. What we have left is everything else - those things that have nothing to do with AVL and are exactly the same as basic BSTs. Because of that, ironically, we will have something more interesting to do.

If AVLs were different enough from BSTs we would simply duplicate the entire BST file and change the insert/delete logic (adding, of course the private rotation methods) and we'd be done. However, because of the great similarity, we want to avoid duplicating the template -- instead we will use inheritance to reuse the BST template, thus avoiding the need to redefine the other 20 or so functions (even if their definitions would be identical, requiring nothing more than a copy/paste). The idea is that if we have an improvement to, or find a bug in, the BST logic, we won't have to fix it in two places - just in the BST class. The AVL class will inherit the repairs automatically.

But that's for next time. See you then.