FHs_treeNode.java

package cs_1c;

public class FHs_treeNode<E extends Comparable< ? super E > >
{
   // use public access so the tree or other classes can access members 
   public FHs_treeNode<E> lftChild, rtChild;
   public E data;
   public FHs_treeNode<E> myRoot;  // needed to test for certain error

   public FHs_treeNode( E d, FHs_treeNode<E> lft, FHs_treeNode<E> rt )
   {
      lftChild = lft; 
      rtChild = rt;
      data = d;
   }
   
   public FHs_treeNode()
   {
      this(null, null, null);
   }
   
   // function stubs -- for use only with AVL Trees when we extend
   public int getHeight() { return 0; }
   boolean setHeight(int height) { return true; }
}

FHsearchTree.java

package cs_1c;
import java.util.*;

public class FHsearch_tree<E extends Comparable< ? super E > >
   implements Cloneable
{
   protected int mSize;
   protected FHs_treeNode<E> mRoot;
   
   public FHsearch_tree() { clear(); }
   public boolean empty() { return (mSize == 0); }
   public int size() { return mSize; }
   public void clear() { mSize = 0; mRoot = null; }
   public int showHeight() { return findHeight(mRoot, -1); }
   
   public E findMin() 
   {
      if (mRoot == null)
         throw new NoSuchElementException();
      return findMin(mRoot).data;
   }
   
   public E findMax() 
   {
      if (mRoot == null)
         throw new NoSuchElementException();
      return findMax(mRoot).data;
   }
   
   public E find( E x )
   {
      FHs_treeNode<E> resultNode;
      resultNode = find(mRoot, x);
      if (resultNode == null)
         throw new NoSuchElementException();
      return resultNode.data;
   }
   public boolean contains(E x)  { return find(mRoot, x) != null; }
   
   public boolean insert( E x )
   {
      int oldSize = mSize;
      mRoot = insert(mRoot, x);
      return (mSize != oldSize);
   }
   
   public boolean remove( E x )
   {
      int oldSize = mSize;
      mRoot = remove(mRoot, x);
      return (mSize != oldSize);
   }
   
   public < F extends Traverser<? super E > > 
   void traverse(F func)
   {
      traverse(func, mRoot);
   }
   
   public Object clone() throws CloneNotSupportedException
   {
      FHsearch_tree<E> newObject = (FHsearch_tree<E>)super.clone();
      newObject.clear();  // can't point to other's data

      newObject.mRoot = cloneSubtree(mRoot);
      newObject.mSize = mSize;
      
      return newObject;
   }
   
   // private helper methods ----------------------------------------
   protected FHs_treeNode<E> findMin( FHs_treeNode<E> root ) 
   {
      if (root == null)
         return null;
      if (root.lftChild == null)
         return root;
      return findMin(root.lftChild);
   }
   
   protected FHs_treeNode<E> findMax( FHs_treeNode<E> root ) 
   {
      if (root == null)
         return null;
      if (root.rtChild == null)
         return root;
      return findMax(root.rtChild);
   }
   
   protected FHs_treeNode<E> insert( FHs_treeNode<E> root, E x )
   {
      int compareResult;  // avoid multiple calls to compareTo()
      
      if (root == null)
      {
         mSize++;
         return new FHs_treeNode<E>(x, null, null);
      }
      
      compareResult = x.compareTo(root.data); 
      if ( compareResult < 0 )
         root.lftChild = insert(root.lftChild, x);
      else if ( compareResult > 0 )
         root.rtChild = insert(root.rtChild, x);

      return root;
   }

   protected FHs_treeNode<E> remove( FHs_treeNode<E> root, E x  )
   {
      int compareResult;  // avoid multiple calls to compareTo()
     
      if (root == null)
         return null;

      compareResult = x.compareTo(root.data); 
      if ( compareResult < 0 )
         root.lftChild = remove(root.lftChild, x);
      else if ( compareResult > 0 )
         root.rtChild = remove(root.rtChild, x);

      // found the node
      else if (root.lftChild != null && root.rtChild != null)
      {
         root.data = findMin(root.rtChild).data;
         root.rtChild = remove(root.rtChild, root.data);
      }
      else
      {
         root =
            (root.lftChild != null)? root.lftChild : root.rtChild;
         mSize--;
      }
      return root;
   }
   
   protected <F extends Traverser<? super E>> 
   void traverse(F func, FHs_treeNode<E> treeNode)
   {
      if (treeNode == null)
         return;

      traverse(func, treeNode.lftChild);
      func.visit(treeNode.data);
      traverse(func, treeNode.rtChild);
   }
   
   protected FHs_treeNode<E> find( FHs_treeNode<E> root, E x )
   {
      int compareResult;  // avoid multiple calls to compareTo()

      if (root == null)
         return null;

      compareResult = x.compareTo(root.data); 
      if (compareResult < 0)
         return find(root.lftChild, x);
      if (compareResult > 0)
         return find(root.rtChild, x);
      return root;   // found
   }
   
   protected FHs_treeNode<E> cloneSubtree(FHs_treeNode<E> root)
   {
      FHs_treeNode<E> newNode;
      if (root == null)
         return null;

      // does not set myRoot which must be done by caller
      newNode = new FHs_treeNode<E>
      (
         root.data, 
         cloneSubtree(root.lftChild), 
         cloneSubtree(root.rtChild)
      );
      return newNode;
   }
   
   protected int findHeight( FHs_treeNode<E> treeNode, int height ) 
   {
      int leftHeight, rightHeight;
      if (treeNode == null)
         return height;
      height++;
      leftHeight = findHeight(treeNode.lftChild, height);
      rightHeight = findHeight(treeNode.rtChild, height);
      return (leftHeight > rightHeight)? leftHeight : rightHeight;
   }
}

FHsplayTree.java

import cs_1c.FHs_treeNode;
import cs_1c.FHsearch_tree;

public class FHsplayTree<E extends Comparable<? super E>> extends
      FHsearch_tree<E> {
   public FHsplayTree() {
      super();
   }

   public E showRoot() {
      if (mRoot == null)
         return null;
      return mRoot.data;
   }

   @Override
   public boolean insert(E x) {
      if (mRoot == null) {
         mRoot = new FHs_treeNode<E>(x, null, null);
         mSize++;
         return true;
      }
      mRoot = splay(mRoot, x);
      FHs_treeNode<E> node;
      int comparison = x.compareTo(mRoot.data);
      if (comparison > 0) {
         node = new FHs_treeNode<E>(x, mRoot, mRoot.rtChild);
         mRoot.rtChild = null;
      } else if (comparison < 0) {
         node = new FHs_treeNode<E>(x, mRoot.lftChild, mRoot);
         mRoot.lftChild = null;
      } else
         return false;
      mRoot = node;
      mSize++;
      return true;
   }

   @Override
   public boolean remove(E x) {
      if (mRoot == null)
         return false;
      mRoot = splay(mRoot, x);
      if (x.compareTo(mRoot.data) != 0)
         return false;
      FHs_treeNode<E> newRoot;
      if (mRoot.lftChild != null) {
         newRoot = mRoot.lftChild;
         newRoot = splay(newRoot, x);
         newRoot.rtChild = mRoot.rtChild;
      } else {
         newRoot = mRoot.rtChild;
         newRoot = splay(newRoot, x);
         mRoot.rtChild = newRoot;
      }

      mRoot = newRoot;
      mSize--;
      return true;
   }

   /**
    * @param k2
    *           , node to rotate left
    * @return k1, replacement node
    */
   protected FHs_treeNode<E> rotateWithLeftChild(FHs_treeNode<E> k2) {
      FHs_treeNode<E> k1 = k2.lftChild;
      k2.lftChild = k1.rtChild;
      k1.rtChild = k2;
      return k1;
   }

   /**
    * @param k2
    *           , node to rotate right
    * @return k1, replacement node
    */
   protected FHs_treeNode<E> rotateWithRightChild(FHs_treeNode<E> k2) {
      FHs_treeNode<E> k1 = k2.rtChild;
      k2.rtChild = k1.lftChild;
      k1.lftChild = k2;
      return k1;
   }

   protected FHs_treeNode<E> find(FHs_treeNode<E> root, E x) {
      mRoot = splay(root, x);
      if (x.compareTo(mRoot.data) != 0) {
         return null;
      }
      return mRoot;
   }

   protected FHs_treeNode<E> splay(FHs_treeNode<E> root, E x) {
      FHs_treeNode<E> rightTree = null, leftTree = null, rightTreeMin = null, leftTreeMax = null;
      int comparison = 0;
      while (root != null) {
         comparison = x.compareTo(root.data);
         if (comparison < 0) {
            FHs_treeNode<E> left = root.lftChild;
            if (left == null)
               break;
            // zig-zig case
            if (x.compareTo(left.data) < 0)
               root = rotateWithLeftChild(root);
            FHs_treeNode<E> leftChild = root.lftChild;
            if (leftChild == null)
               break;
            if (rightTree != null)
               rightTreeMin = rightTreeMin.lftChild = root;
            else
               rightTree = rightTreeMin = root;
            // zig-zag/simplified zig-zig case
            root = leftChild;
         } else if (comparison > 0) {
            FHs_treeNode<E> right = root.rtChild;
            if (right == null)
               break;
            // zig-zig case
            if (x.compareTo(right.data) > 0)
               root = rotateWithRightChild(root);
            FHs_treeNode<E> rightChild = root.rtChild;
            if (rightChild == null)
               break;
            if (leftTree != null)
               leftTreeMax = leftTreeMax.rtChild = root;
            else
               leftTree = leftTreeMax = root;
            // zig-zag/simplified zig-zig case
            root = rightChild;
         } else
            break;
      }
      // reassembling
      if (leftTree != null) {
         leftTreeMax.rtChild = root.lftChild;
         root.lftChild = leftTree;
      }
      if (rightTree != null) {
         rightTreeMin.lftChild = root.rtChild;
         root.rtChild = rightTree;
      }
      return root;
   }
}

Main.java

import java.util.Random;
import cs_1c.*;

class PrintObject<E> implements Traverser<E> {
   public void visit(E x) {
      System.out.print(x + " ");
   }
};

// ------------------------------------------------------
public class Main {
   // ------- main --------------
   public static void main(String[] args) throws Exception {
      Random rand = new Random();
      // adjust nodeNumber and findNodeNumber for different test cases
      FHsplayTree<Integer> searchTree = new FHsplayTree<Integer>();
      PrintObject<Integer> intPrinter = new PrintObject<Integer>();

      System.out.println("\n---------test case 1-------------");
      int k;

      searchTree.traverse(intPrinter);

      System.out.println("Initial size: " + searchTree.size());
      for (k = 1; k <= 32; k++)
         searchTree.insert(k);
      System.out.println("New size: " + searchTree.size());

      System.out.println("\nTraversal");
      searchTree.traverse(intPrinter);
      System.out.println();

      for (k = -1; k < 10; k++) {
         // searchTree.contains(k); // alternative to find() - different error
         // return
         try {
            searchTree.find(k);
         } catch (Exception e) {
            System.out.println(" oops ");
         }
         System.out.println("splay " + k + " --> root: "
               + searchTree.showRoot() + " height: " + searchTree.showHeight());
      }

      System.out.println("\n-------------test case 2-------------");
      searchTree = new FHsplayTree<Integer>();
      // insert nodes
      System.out.println("--------inserting nodes----------");
      insertNode(rand, searchTree, 2, 32);
      System.out.println("\nTraversal");
      searchTree.traverse(intPrinter);
      System.out.println();
      // find nodes
      System.out.println("--------finding nodes----------");
      findNode(searchTree, 2, 15);
      searchTree.traverse(intPrinter);
      // remove nodes
      System.out.println();
      System.out.println("--------removing nodes----------");
      removeNode(searchTree, 2, 32);
      System.out.println("The left nodes are:");
      searchTree.traverse(intPrinter);

      System.out.println("\n-------------test case 3-------------");
      searchTree = new FHsplayTree<Integer>();
      // insert nodes
      System.out.println("--------inserting nodes----------");
      insertNode(rand, searchTree, 1, 20);
      System.out.println("\nTraversal");
      searchTree.traverse(intPrinter);
      System.out.println();
      // find nodes
      System.out.println("--------finding nodes----------");
      findNode(searchTree, 4, 22);
      searchTree.traverse(intPrinter);
      // remove nodes
      System.out.println();
      System.out.println("--------removing nodes----------");
      removeNode(searchTree, 5, 15);
      System.out.println("The left nodes are:");
      searchTree.traverse(intPrinter);

      System.out.println("\n-------------test case 4-------------");
      searchTree = new FHsplayTree<Integer>();
      // insert nodes
      System.out.println("--------inserting nodes----------");
      insertNode(rand, searchTree, 0, 0);
      System.out.println("\nTraversal");
      searchTree.traverse(intPrinter);
      System.out.println();
      // find nodes
      System.out.println("--------finding nodes----------");
      findNode(searchTree, 0, 1);
      searchTree.traverse(intPrinter);
      // remove nodes
      System.out.println();
      System.out.println("--------removing nodes----------");
      removeNode(searchTree, 0, 1);
      System.out.println("The left nodes are:");
      searchTree.traverse(intPrinter);

      System.out.println("\n-------------test case 5-------------");
      System.out.println("------------Insertion: --------------");
      searchTree = new FHsplayTree<Integer>();
      // insert nodes
      System.out.println("Added 5");
      searchTree.insert(5);
      System.out
            .println("No rotation required(no splaying required) - mRoot becomes :"
                  + searchTree.showRoot());

      System.out.println("Added 2");
      searchTree.insert(2);
      System.out
            .println("No rotation required(splaying 1 node) - mRoot becomes :"
                  + searchTree.showRoot());
      System.out.println("Height is: " + searchTree.showHeight());

      System.out.println("Added 10");
      searchTree.insert(10);
      System.out.println("Rotation required"
            + "(2 rotate with left child - 5) then insert - mRoot becomes :"
            + searchTree.showRoot());
      System.out.println("Height is: " + searchTree.showHeight());

      System.out.println("Added 8 last");
      searchTree.insert(8);
      System.out.println("No rotation required"
            + "(Only 1 zig-zag case, from 5 --> 10 --> 8).");
      System.out.println("Height is: " + searchTree.showHeight());
      System.out.println("Insert 8 on top of 10(mRoot 10 "
            + "becomes right child and new mRoot becomes "
            + searchTree.showRoot() + ")");
      System.out.println("Height is: " + searchTree.showHeight());

      System.out.println("-----------Traversal: -------------");
      searchTree.traverse(intPrinter);

      System.out.println("\n-----------Removal: ------------");
      System.out.println("Root : " + searchTree.showRoot());
      System.out.println("Removing 8");
      searchTree.remove(8);
      System.out.println("No rotation required(8 is already the root)");
      System.out.println("Root after removing 8(root)"
            + " - should be 5(its left child moves up by algorithm) : "
            + searchTree.showRoot());
      System.out.println("Height is: " + searchTree.showHeight());

      System.out.println("Remove 10");
      searchTree.remove(10);
      System.out.println("New root : " + searchTree.showRoot());
      System.out.println("The tree was originally: "
            + "root: 5, rtChild: 10, lftChild: 2");
      System.out.println("In splay(), 10 rotated with 5(zig-zig). "
            + "Now the root became root: "
            + "10, lftChild: 5, lft's lftChild: 2");
      System.out.println("10 was then removed to get the root : "
            + searchTree.showRoot());
      System.out.println("Height is: " + searchTree.showHeight());

      System.out.println("Remove 2");
      searchTree.remove(2);
      System.out.println("New root : " + searchTree.showRoot());
      System.out.println("The tree was root: 5, lftChild: 2");
      System.out
            .println("In splay(), 5 was moved to rightTreeMin(simplified zig)."
                  + "The root became root: 2, rtChild: 5");
      System.out.println("2 was then removed to get the root : "
            + searchTree.showRoot());
      System.out.println("Height is: " + searchTree.showHeight()
            + " (because only mRoot is left)");

      System.out.println("-----------Traversal: -------------");
      searchTree.traverse(intPrinter);

   }

   // create random number with range from min to max
   private static int randInt(Random rand, int min, int max) {
      int randomNum = rand.nextInt((max - min) + 1) + min;
      return randomNum;
   }

   // insert node into tree with data range from min to max
   private static void insertNode(Random rand, FHsplayTree<Integer> t, int min,
         int max) {
      System.out.println("Initial size: " + t.size());
      for (int k = 0; k < max - min + 1; k++) {
         int r = randInt(rand, min, max);
         t.insert(r);
      }
      System.out.println("New size: " + t.size());
   }

   // find node in tree with data range from min to max
   private static void findNode(FHsplayTree<Integer> t, int min, int max) {
      for (int k = min; k <= max; k++) {
         // searchTree.contains(k); // alternative to find() - different error
         // return
         try {
            t.find(k);
         } catch (Exception e) {
            System.out.println(" oops! " + k + " not in the tree.");
         }
         System.out.println("splay " + k + " --> root: " + t.showRoot()
               + " height: " + t.showHeight());
      }
   }

   // remove node from tree with data range from min to max
   private static void removeNode(FHsplayTree<Integer> t, int min, int max) {
      for (int k = min; k <= max; k++) {
         if (t.remove(k))
            System.out.println(k + " is successfully removed");
         else
            System.out.println("Number " + k + " does not exist in the tree.");

         System.out.println("splay " + k + " --> root: " + t.showRoot()
               + " height: " + t.showHeight());
      }
   }

}