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.
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).
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.
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.
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.
weathervane stovepipe pattern machine jackstand garage airplane
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).
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.