UNC-CH COMP 410

Splay Tree Implementation

You will write code that implements, exercises, and analyzes splay trees. We will build this one chunk at a time. There are plenty of implementations of "tree" stuff out there. Please do not copy those. I want you to write your own code. The learning in this activity comes from actually powering through all the reasoning needed to get the pointers and recursive calls hooked up correctly.

BST first

You can get started by writing a class that implements a Binary Search Tree (BST). A Splay Tree (SPT) is a BST that has "splaying" operations to balance the height as it grows and changes. Keeping it balanced (as we have discussed in class) keeps the search operation for a tree of N nodes closer to O(log N) and away from O(N).

We will delay implementing the splaying operations until we have covered that topic in class. Conveniently, an SPT works by doing a normal insert into a BST and splaying afterwards. So we will need a properly functioning BST class before we can turn it into a SPT class.

So first write a class BSTnode. In this class will be the value field. Since we are using word data here, you can declare the value to be type String directly or you can write generics. Also this class will have links to the R and L subtrees (also BTnode's). You may also want or need a parent pointer, bookkeeping information (like child height counts if it were an AVL tree), etc. In this node class can go the methods to do insert, remove, contains, get and other functions. You would ask a node to insert a value, and that node would behave as the root of a tree.

In the approach just described, an entire "tree" would then be no different from a node. You may wish instead to design your code like in your text, where you write a separate class SPT to point to the root of an entire tree, as well as to contain information that is related to the whole tree (like what is its size, height, etc.). In this "tree" class you have a field "root" that points to a BTnode and off you go. This "tree" class would then contain special insert etc. methods that would invoke the insert etc. methods on the main root node.

Just get the basic structure going and grow the functionality as needed.

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.

You may also find this code useful. It shows how to do keyboard input in Java. You will be writing a "driver" class to build and exercise the tree (BST and then SPT) and it will take commands from the user at the keyboard. The driver class will contain public static void main and will get the ball rolling.

The driver will create a tree object, and then cause user commands to happen on the tree object. The user can do inserts (find, delete) in the tree by typing a word to insert (find, delete). The MyRandom code can be used to fill the tree automatically with a large number of words, more than you might wish to type.

Now the Splay operation

Once you have the Binary Search Tree working you can then concentrate on writing the splay operation and make a class SPTree (Splay Tree) by adding your splay to your Binary Search Tree. Write the splay operation, and then insert calls to it at the proper places in the appropriate binary search tree methods (insert, search, delete).

Duplicates on Insert

Here is what to do if a string is being inserted into your splay tree and that string is a duplicate... that is, the string is already in the tree. Just splay the found node to the root (just like would happen if you had done a search operation on the value instead of an insert). Do NOT add the string a second time. Let's make sure our splay trees contain only unique node values.

Alternate Splay Delete

You may wish to try this approach for the delete operation. It does not require that the binary search tree delete be written.

Of course, you may find it more satisfying and complete to write the full BSTree class, complete with BST delete, and then create your splay tree from it using inheritance on the BST. This is a good OO approach.

Tree Print method

Write a method to allow the tree contents to be printed to see its structure visibly. You may not wish to run this method on large trees, but it will be useful in debugging your code on small trees.

To print a tree, lets do something simple. Let's make print a recursive method, and make it traverse the tree using one of two traversal orders (your choice). Examples of each are shown below for a small binary search tree. Make your choice based on which approach produces a print form that helps you see the tree structure most clearly.

pre-order: This means the root will be the first thing printed, then the entire left child subtree (with its root first etc.) then the entire right subtree. Use indentation to show levels; this means when you print the root of a subtree, indent it a few spaces more than its parent node. Feel free to decorate your printing in any way you like to help the reader to see the tree structure.

reverse in-order: In this case, you do an in-order traversal, but you visit the right subtree before the left. Use indentation to show levels. This form will generate a tree that, if you tilt your head to the left, will look "tree like" and you may find it easier to see the structure for testing purposes.

example: reverse in-order

         weathervane
    stovepipe
         pattern
machine
         jackstand
    garage
         airplane

example: pre-order

machine
  garage
    airplane
    jackstand
  stovepipe
    pattern
    weathervane

Just a note... remember that since this splay tree is also a binary search tree, you get a sort "for free" by just doing a normal in-order traversal (left child first, then root, then right child).

Analysis

Write a method for your splay tree that will compute the height of the tree (this is the longest path from the root to a leaf). Remember that the height of a tree with only a root (one node) is 0. The height of a perfect binary tree with 3 nodes (a root and two childen) is 1; the height of a perfect binary tree with 7 nodes is 2; etc.

You may compute this recursively and don't worry about possible inefficiency in this method. The recursive method will be a form of post-order traversal, in that it will compute the height of the left child tree, then the height of the right child tree, then find the max of those two results; it then "handles the root" last by adding one to the max of the child heights to get the height of the tree itself.

Write it carefully, and test it on small trees to make sure you have correctly handled the special extreme cases such as a tree that is a root and no children (height 0), a null tree (height -1, or an error), and nodes with one child there and one child null.

Then run your program 10 times, each time generating a splay tree with 65,535 nodes containing random character string values; 65,535 is (2^16)-1. For each of the 10 runs, compute the final tree height. Report the 10 heights, and the average tree height over the 10 runs.

Compare this average to what you would expect the height to be if this were a full binary tree (or nearly so, like an AVL tree) with the same number of nodes. To do this, you need an accurate equation relating the number of nodes in a full binary tree to its height. Make this equation clear in your writeup.

Hand-in

You will turn is these items:

a document called "README" containing:

Heading: COMP 410, assn. 3, the date and your name
a list of your class names and a brief purpose for each class
any assumptions you made or information you want us to understand about your design/solution
the analysis results

your Java code (java source files)