Splay Tree ADT (SPLT)

What to Do

What to Hand-in

Hand in your code as per the instructions under Assignment 4 in Sakai.

Submit your ZIPPED eclipse project entitled Assignment4 (see below about zipping instructions and name of zip). Your program must be within a package entitled SPLT_A4.


For uniformity, and to aid timely grading, you must write your program with these specific structures.

Interface SPLT_Interface

 * COMP 410
 * Make your class and its methods public!
 * Before zipping: PLEASE REMOVE THE RunTests.java, 410LocalChecks.jar, 
 * (see powerpoint for instructions)
 * Submission directions: Zip your eclipse project folder 
 * (e.g. Assignment2) for this assignment and upload it to Sakai.
 * Please name your zip file youronyen_assignment2.zip 
 * That folder should contain src and bin folders with 
 * your code/classes.
 * Your SPLT implementation will implement this BST interface.

package SPLT_A4;

  Interface: The SPLT will provide this collection of operations:

    in: a string (the element to be stored into the tree)
    return: void, if you need to update size when delegating, consider using a boolean as I mention in BST_Node
    effect: if the string is already in the tree, then there is no change to
              the tree state (save for splaying), and return
            if the string is not already in the tree, then a new tree cell/node
              is created, the string put into it as data, the new node is linked
              into the tree at the proper place; size is incremented by 1,
              and return
    in: a string (the element to be taken out of the tree)
    return: void
    effect: see description on "when to splay"
    in: a string (the element to be searched for)
    return: boolean, return true if the string being looked for is in the tree;
            return false otherwise
            this means return false if tree size is 0
    effect: no change to the state of the tree (save for splaying found node or what would be its parent)

    in: none
    return: string, the element value from the tree that is smallest
    effect: no tree state change (save for splaying)
    error: is tree size is 0, return null

    in: none
    return: string, the element value from the tree that is largest
    effect: no tree state change (save for splaying)
    error: is tree size is 0, return null

    in: nothing
    return: number of elements stored in the tree
    effect: no change to tree state

    in: nothing
    return: boolean, true if the tree has no elements in it, true if size is 0
            return false otherwise
    effect: no change to tree state

    in: none
    return: integer, the length of the longest path in the tree from root to a leaf
    effect: no change in tree state
    error: return -1 is tree is empty (size is 0, root is null)

    in: none
    return: a tree cell/node, the one that is the root of the entire tree
            means return a null if the tree is empty
    effect: no change to tree state


// ADT operations

public interface SPLT_Interface {
  public void insert(String s);
  public void remove(String s);
  public String findMin();
  public String findMax();
  public boolean empty();
  public boolean contains(String s);
  public int size();
  public int height();
  public BST_Node getRoot();

Class BST_Node

package SPLT_A4;

public class BST_Node {
  String data;
  BST_Node left;
  BST_Node right;
  BST_Node par; //parent...not necessarily required, but can be useful in splay tree
  boolean justMade; //could be helpful if you change some of the return types on your BST_Node insert.
            //I personally use it to indicate to my SPLT insert whether or not we increment size.
  BST_Node(String data){ 
  BST_Node(String data, BST_Node left,BST_Node right,BST_Node par){ //feel free to modify this constructor to suit your needs

  // --- used for testing  ----------------------------------------------
  // leave these 3 methods in, as is (meaning also make sure they do in fact return data,left,right respectively)

  public String getData(){ return data; }
  public BST_Node getLeft(){ return left; }
  public BST_Node getRight(){ return right; }

  // --- end used for testing -------------------------------------------

  // --- Some example methods that could be helpful ------------------------------------------
  // add the meat of correct implementation logic to them if you wish

  // you MAY change the signatures if you wish...names too (we will not grade on delegation for this assignment)
  // make them take more or different parameters
  // have them return different types
  // you may use recursive or iterative implementations

  public BST_Node containsNode(String s){ return false; } //note: I personally find it easiest to make this return a Node,(that being the node splayed to root), you are however free to do what you wish.
  public BST_Node insertNode(String s){ return false; } //Really same logic as above note
  public boolean removeNode(String s){ return false; } //I personal do not use the removeNode internal method in my impl since it is rather easily done in SPLT, feel free to try to delegate this out, however we do not "remove" like we do in BST
  public BST_Node findMin(){ return left; } 
  public BST_Node findMax(){ return right; }
  public int getHeight(){ return 0; }

  private void splay(BST_Node toSplay) { return false; } //you could have this return or take in whatever you want..so long as it will do the job internally. As a caller of SPLT functions, I should really have no idea if you are "splaying or not"
                        //I of course, will be checking with tests and by eye to make sure you are indeed splaying
                        //Pro tip: Making individual methods for rotateLeft and rotateRight might be a good idea!

  // --- end example methods --------------------------------------


  // --------------------------------------------------------------------
  // you may add any other methods you want to get the job done
  // --------------------------------------------------------------------

Class SPLT

package SPLT_A4;

public class SPLT implements SPLT_Interface{
  private BST_Node root;
  private int size;
  public SPLT() {
    this.size = 0;
  public BST_Node getRoot() { //please keep this in here! I need your root node to test your tree!
    return root;


Class SPLT_Playground

package SPLT_A4;

public class SPLT_Playground {
  public static void main(String[] args){
  public static void genTest(){
    SPLT tree= new SPLT();
    System.out.println("size is "+tree.size());

    static void printLevelOrder(SPLT tree){ 
    //will print your current tree in Level-Order...Requires a correct height method
      int h=tree.getRoot().getHeight();
      for(int i=0;i<=h;i++){
        System.out.print("Level "+i+":");
        printGivenLevel(tree.getRoot(), i);
    static void printGivenLevel(BST_Node root,int level){
      if(level==0)System.out.print(root.data+" ");
      else if(level>0){
   static void printInOrder(BST_Node root){
      System.out.print(root.getData()+" ");

Class RunTests

package SPLT_A4;
import gradingTools.comp410s17.assignment4.testcases.Assignment4Suite;

public class RunTests {
  public static void main(String[] args){ //runs Assignment 4 oracle tests

When to Splay

Splaying is a balancing operations that is done when nodes are accessed in the tree. The basic splay operation causes a node to move to the root position by doing rotations that preserve the BST relations amoung the node values. We move a node to the root position on the assumption that more accesses to that node are likely in the near future; that node will be near the root when those subsequent accesses happen.

First, write an internal method "splay" for your SPLT. It may take an argument that is a tree cell (the node to be moved to the root). When done, the tree will have that cell as its new root, and the other cells will all still be in proper BST arrangement. It may be useful to separate out a couple of methods for rotateLeft and rotateRight operations.

One you have the splay method, you call it at these points:

Test Data

Use the Splay Tree animation (see the link under the "Examples" tab) to show you what trees result after various combinations of insert, remove, contains, etc. operations. Slow the animation way down to see how the operations do tree rotations.

We, as before, will release a JAR file of Junit tests that you can also use to check your work. This release will be about half-way through the assignment time frame, so do not wait to get started. Write your code and test it as you see fit, and use the JAR file as a further check once we release it.

Supporting Code Examples

Random strings

You may find this code useful. It is a class that generates random strings of characters from "a" to "z". It will generate strings that are 5 to 25 characters in length by default if you call MyRandom.nextString() with no arguments. If you wish to control the string lengths better, then you can call it with arguments. Calling MyRandom.nextString(3,11) for example will generate string that vary in length from 3 to 11 characters. The nextString methods are declared static so you can call them as shown with the class name qualifier and don't need to instantiate an object in your code.