Implementing Splay Trees

Overview

You will write Java classes to implement and exercise Splay Trees. Write your own classes for nodes, link structures and manipulations, etc. Do not use any data structure classes from the Java libraries.

This is your own work; you may discuss ideas with your classmates in order to learn and get clear on concepts and Java language details. However, do not hand in code that is essentially a copy of something written by two or more people together.

Write at least 3 classes (you can write more as you wish or need):

class SPTNode
This is the class that is a node in the tree, and contains the data value stored at a tree node. It also has the left and right child subtrees, as well as any other information you might need to get things to work (like parent pointer, etc.). It will have the insert, delete, and find methods, as well as the splaying methods, and other methods.
class SPTDemo
This is the class containing the main method. In it you will create a splay tree and fill it with random string values using calls to insert. You will also take input from the keyboard (this is explained in detail below).
class MyRandom
This code generates random strings. You may use it as is. The methods are declared static, so you may call them as MyRandom.nextString() as shown in the sample keyboard input code.

Splaying

In class SPTNode you will have the methods insert, find, and delete. You also will have a bookkeeping method getSize to tell how many nodes are in the tree (use a static field for this). You will have 6 splaying methods: singleL, singleR, zigzagL, zigzagR, zigzigL, and zigzigR. Once you write all the R operations, the L operations will be easy adaptations (since they are symmetric).

The insert and find operations are the normal ones for binary search trees. When you do an insert you will then call the splay operations to move the inserted node to the root. Insert will also increment the node count of the tree (the static field). When you do a successful find on a node you will call the splay operations to move the found node to the root. In an unsuccessful find, there is no node to move. When you splay the tree on a node, you need to perform appropriate splay operations repeatedly until the node has moved to the root position of the entire tree.

For delete, do the normal non-lazy delete operations for binary search trees. Do not do any splaying on delete. Remember to decrement the tree node count. Also remember that a use may ask to delete a node that is not in the tree... just do nothing in this case, no need for error messages. Or you might consider making delete return a boolean: true is a node was found and removed, and false if there was no node to delete. Another idea is to have delete return the node removed; if there is no node to delete, it will return null. If you return the node deleted, remember to null out the child subtree pointers in that node (and the parent pointer if its there).

Building and testing a tree

The class SPTDemo will be an interactive driver for this exercise. In this class you will have your main method as well as any supporting methods you would like to create to accomplish the task of constructing and testing a splay tree.

First, create an empty splay tree that can hold elements of type String. As noted in class you may do this with explicit String declarations, or with Java generics, your choice.

Get some input from the user: ask how large a tree to generate. The user will type an integer (non-negative, but 0 is ok, don't forget to convert the input string to an integer) at the keyboard; let's call that number N. You will then use MyRandom to generate N random strings varying in length from 5 to 13 characters and insert these strings into your splay tree. Note that if the user types "0" your tree will remain empty.

Next go into a loop requesting keyboard input from the user. Ask the user to indicate which operation to perform on the tree (insert, find, delete, size, print, sort, quit). For insert, find, and delete operations the user will also need to be asked to type a string for use in the operation. Perform the requested operation and loop back. We will end this loop when the use indicates quit when an operation is requested. You may use this code as a model for doing keyboard input.

For the size operation simply print the result of calling the getSize() method.

To print a tree, lets do something simple. It is probably best to include print as a method is class SPTNode (this is somewhat analagous to having a toString() methods in classes for producing a visible representation). It will also not be wise to call print on a tree that has, say, 50,000 nodes as it will cause you to have to kill the execution of the program. But for small trees, using print will help you see how well your operations are working.

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.

For sort just do a normal in-order traversal (left child first, then root, then right child) and print a plain list of node values in ascending alphabetic order. Do not do indenting like in the print operation. Note that this is a recursive method with maybe 5 or 6 lines of code... nothing complicated. The tree provides the sorted structure inherently, and the in-order traversal reveals it.

Print examples

reverse in-order

         weathervane
    stovepipe
         pattern
machine
         jackstand
    garage
         airplane

pre-order

machine
  garage
    airplane
    jackstand
  stovepipe
    pattern
    weathervane