Splay Tree with Interactive Test Driver

You are going to build on the BST code you wrote for the previous assignment.

Implement a splay tree (SPLT) by adding the splaying functionality to your basic BST. Use the same main class test driver you used before. You will have to make small changes, obviously (to make objects of type SPLT instead of BST), but it should accept and execute the same commands/operations (except we are leaving out "get", see "Misc. Notes" below).

There are no new commands or operations in the SPLT abstract interface. This is because your SPLT is a BST with splaying added to the appropriate access methods to provide balance. Splay is not an operation that can be called on a SPLT (like insert or remove are). Rather, the splay operation is internal and is invoked at appropriate times during execution of the external SPLT operations.

What to Hand-in

Hand in your code as per the instructions under Assignment 4 in Sakai.
Submit a single text file with the entire Java source... main class, random gen code, etc. as well as your SPLT classes. We should be able to cut and paste this single Java source into a Java IDE and have it compile and execute for our testing/grading. Remember to make all your classes without the "public" modifier.

There is some redundency here with the code for Assignment 3, but that's fine. We want each submission to be a self-contained complete Java program that does not require us to track down pieces/parts from other places.

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 will 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.

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.

Misc. Notes

We will drop the "get" operations for this assignment. You can leave it out of the driver, the command line processor, and take it out of the BST/SPLT code. We are not using it, and this way we don't have to worry about adding splay action to it.