Section 6 - Splay Algorithms and Closing Tree Remarks

5B.6.1 splay()

Here is an algorithm that reflects everything we just said.

Algorithm for void splay( Node * & root, const Object & x )

That's it. The coding is barely longer than the algorithm, so you see it is very clean, and represents the pictures on the earlier pages.

5B.6.2 insert()

We discussed insertion. Here is the algorithm.

Algorithm for bool insert( const Object & x )

You can perform the assignment of the child nodes during the new node's construction making this a very small method.

5B.6.3 remove()

To remove a node, splay its value, bringing it to the root. Once there, splay the left subtree for x (which we know is not there). Because x is larger than everything in the left subtree, this will bring the max, y, to the root of that subtree. y becomes the new root, and you can attach the old right subtree as y's right child.

Algorithm for bool remove( const Object & x )

Don't really use != or any other operator for comparison. Rather, use only < for all comparisons to reduce the implicit requirements on the data class.

This completes our discussion of splay trees - you'll do the rest yourself in the assignment. Before leaving the module, let's wrap up with a few general remarks on trees.

5B.6.4 Other Aspects of Trees

5B.6.4.1 Unwinding Recursion

In most cases, it is not hard to take the recursion out of code, and AVL or BSTs are no exception. Recursion is good for the design process because it encapsulates the solution very elegantly. As we have seen, though, it sometimes has disastrous effects on running time and resource management. That's why recursion is sometimes used for first phase design, and once debugged, is replaced by non-recursive code.

Because most binary tree designs result in O(logN) running times, recursion normally does not offer an obstacle, and the clarity it affords makes up for the time saved by unwinding it -- i.e., turning it into a loop. Still, it is worth unwinding if you can do so without incurring major impact on the code. Splay trees work without recursion and so can BST or AVL trees.

In the FHthreadedBST example which I have touched upon in a previous section, I took the opportunity, while under the hood, to take out recursion in all but the remove() method. In the code below, I have a non-recursive insert() which is also part of the threaded tree template. The thread-related code has nothing to do with the new algorithm, and you can use the same form to unwind recursion in all of your previous insert() algorithms.

template <class Comparable>
bool FHthreadedBST<Comparable>::insert(const Comparable &x)
{
   if (mRoot == NULL)
   {
      mRoot = new FHthreadedNode<Comparable>(x, NULL, NULL, true, true, 0);
      mSize++;
      return true;
   }

   FHthreadedNode<Comparable> *newNode, *parent;
   parent = mRoot;
   while(true) 
   {
      if (x < parent->data)
      {
         if( !(parent->lftThread) )
            parent = parent->lftChild;
         else
         {
            // place as new left child
            newNode = new FHthreadedNode<Comparable>
               (x, parent->lftChild, parent, true, true, 0);
            parent->lftChild = newNode;
            parent->lftThread = false;
            break;
         }
      }
      else if (parent->data < x)
      {
         if( !(parent->rtThread) )
            parent = parent->rtChild;
         else
         {
            // place as new left child
            newNode = new FHthreadedNode<Comparable>
               (x, parent, parent->rtChild, true, true, 0);
            parent->rtChild = newNode;
            parent->rtThread = false;
            break;
         }
      }
      else 
         return false; // duplicate;
   }

   mSize++;
   return true;
}

5B.6.4.2 Adding Members

Threaded trees represent a special case of a more general idea. You can often speed up an algorithm or avoid recursion by adding new members to your underlying node class. Naturally, this adds space to the data structure. Therefore, this becomes a resource allocation decision: Is the speed improvement worth the space? If memory is not an issue because of the special nature of your application, the answer may well be yes. In threaded trees, we add two thread bools to the node class. In AVL trees we add a height member.

Another example is the addition of a parent pointer in the node class. We did this in general trees, but dropped it with BSTs. However, parent pointers have a definite use, especially if we want to avoid recursion, and some binary tree implementations use them, including some AVL trees. In bottom-up splay trees (which we skipped in favor of the more advanced top-down splay trees), a parent node would be very useful since we have to process ... well, from the bottom, up!

5B.6.4.3 Lazy Deletion

We discussed this in a previous lesson, and most of you have actually "lived" lazy deletion intensely in the last assignment. After experiencing the challenge of remove() in AVL trees, we can see the potential for some improvement in this operation.

5B.6.4.4 Red-Black Trees

If you go on to do upper division work, you will have the opportunity to take courses that explore tree algorithms even more thoroughly. One tree species you will encounter is the Red-Black tree. Red-Black trees provide a slightly relaxed balancing condition, so the tree can be a little more imbalanced than AVL trees. The benefit is that the insertion and removal algorithms are faster. The drawback is that look-up (i.e., a find()) is a little slower. However, since a look-up is O(logN) in both cases, the slight constant increase in this operation is usually unnoticeable, while the find() and remove() speed improvements are clearly felt.

Well, this is a lot of tree information. I hope that most of you can take the time to experiment with and improve all of my code. Reading it does not confer understanding. No matter how much you might think you understand, it is not until you are forced to write and debug code that you really gain mastery. I've given you the opportunity to experience lazy deletion and top-down splay trees first hand, but you really should make a go at AVL trees and general trees as time permits.

Enjoy your assignment and I'll see you next week.