UNC-CH COMP 410

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:

• insert: do a normal BST insert, and then splay the inserted node. If the node being inserted is already in the tree, then it is not added again, but it is splayed to the root. Either way, when done the root node has the inserted value in it.


• contains: search for the node with the indicated value; the last node accessed in this search is splayed. This means if the search is successful, then the found node is splayed and becomes the new root. If the value being searched for is not in the tree, then the last node accessed prior to reaching the NULL pointer is splayed and becomes the new root.


• findMin (Max): this is an access, so when the min (max) is found, that node is splayed to the root.


• remove: We do this in several steps.
  • do a "contains" on the node to be removed; this will splay it to the root if it is in the tree; if it is not in the tree, the "contains" splays the last accessed node to the root, and we are done... no node is deleted.
  • unhook the root node, leaving you with two subtrees: the left child L, and the right child R
  • do a "findMax" on L; this will splay the max node to the root, and will also leave that new root of L with no right child subtree (since the value there is larger than all the others in L).
  • make R the right child subtree of L.

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.