Assignment 5 – Top-Down Splay Trees Using Inheritance

Make sure you have read and understand the Modules Information About Programming Assignments and Style Rules for Assignments before submitting this assignment.

Top Down Splaying With Ints

This week you will implement splay trees using top-down splaying, as presented in the modules. In a colorful twist, you will realize the generic by deriving from the base class FHsearch_tree. You can use our FHavlTree generic as a model for how to handle derived generic class syntax (but don’t work in that file, please!). Your job will be far easier than what was done in AVL trees, because:

  1. we don’t have to change the node type (so we can use the base FHs_treeNode without any modification or sub-classing),
  2. we don’t have to add any data members to the tree, and
  3. some of the methods that required overriding in AVL trees due to the height member (like cloneSubtree()) can be left un-overridden, as their base class implementations will work fine for the splay tree.

The Spec

Derive the generic class FHsplayTree from FHsearch_tree.

Override the following public methods:
  • public boolean insert( E x )
  • public boolean remove( E x )

Their meanings are identical to their base class counterparts. The implementation will use splay(), described below. Their algorithms are given in the modules. The private find() (seen below) also uses splay() and, like the base class counterpart, returns null if the item is not in the tree. The public version of find() does not require overriding because the base class version will automatically call the derived protected find() that you will define here. Similarly, contains() will work without being overridden for the same reason.

Add the following public method:
  • public E showRoot() – which returns (doesn’t really show) the m_root data, or null if there is nothing in the tree. This is useful for debugging and proving that the class really is splaying.
Add the following protected (or private) methods:
  • FHs_treeNode<E> splay( FHs_treeNode<E> root, E x ) – this method is analyzed in depth in the modules and a detailed algorithm is given there.
  • FHs_treeNode<E> rotateWithLeftChild( FHs_treeNode<E> k2 ) – this is (almost) identical with the version found in Make the trivial adjustments and you’ve got it.
  • FHs_treeNode<E> rotateWithRightChild( FHs_treeNode<E> k2 ) – this is (almost) identical with the version found in Make the trivial adjustments and you’ve got it.
  • FHs_treeNode<E> find( FHs_treeNode<E> root, E x ) – this is the private partner of the public find().
Implementation Requirements
  • Assume that the underlying data type, E, implements Comparable, as we have been doing for all search trees.
  • Do not use “header nodes”. In other words, do not use the “clever” solution you find in the text which has “header nodes” and “null nodes” that are used to shorten code. If you turn in code that uses header nodes or adds a null node to your private data, I won’t award any points for the submission – it is an example of code that is “too clever by a half”. Translate the algorithms presented in the modules directly and clearly, without short-cuts, so we can see the connection between your code and the algorithms and diagrams studied.
  • Do not provide public/private pairs or unnecessary methods. If a public method is not recursive, it doesn’t need a private version. And I will restate that you don’t need to rewrite base class methods if the are the same in this derived class. If the only difference is that they call a derived private method, then the base class version will be fine without being overridden.
  • When implementing the algorithm, the variables leftTree and rightTree are merely node references, not actual trees. It would be unnecessarily complicated to declare these as some sort of tree objects. They simply point to the root nodes of their respective growing trees which are augmented one node-at-a-time as the algorithm progresses (though the addition of new maxes or mins on each one).
Implementation Hints

The only trick that you will continue to use (we have been doing it all week now) is to let the private methods return a node type that the client can use to modify some node or link. For example, when calling splay() you can’t just call it – you have to capture the return, as in:

   someNode = splay(someNode, x);_x000D_

The point is, splay() will be modifying someNode and possibly replacing the node to which it points completely. So the client needs to point to the new object, and this is the only way to accomplish that.

Here is a short main that represents the 32-node Integer tree in the text. Once you have it running, compare the results with the diagrams in the text. In particular, make sure that the heights at the various stages are the same as indicated by the diagram in the text. (They can be off-by-one without penalty, as minor adjustments in implementation can result in heights which are +1 or -1 someone else’s implementation.)

// CIS 1C Assignment #5_x000D_
// Instructor Solution Client_x000D_
import cs_1c.*;_x000D_
class PrintObject<E> implements Traverser<E>_x000D_
   public void visit(E x)_x000D_
      System.out.print( x + " ");_x000D_
public class Foothill_x000D_
   // -------  main --------------_x000D_
   public static void main(String[] args) throws Exception_x000D_
      int k;_x000D_
      FHsplayTree<Integer> searchTree = new FHsplayTree<Integer>();_x000D_
      PrintObject<Integer> intPrinter = new PrintObject<Integer>();_x000D_
      System.out.println( "Initial size: " + searchTree.size() );_x000D_
      for (k = 1; k <= 32; k++)_x000D_
      System.out.println( "New size: " + searchTree.size() );_x000D_
      System.out.println( "nTraversal");_x000D_
      for (k = -1; k < 10; k++)_x000D_
         // searchTree.contains(k);  // alternative to find() - different error return_x000D_
         catch( Exception e )_x000D_
            System.out.println( " oops " );_x000D_
         System.out.println( "splay " + k + " --> root: " _x000D_
            + searchTree.showRoot() _x000D_
            + " height: " + searchTree.showHeight() );_x000D_