UNC-CH COMP 410

Binary Search Tree Implementation

Part 2: Splay Tree with Interactive Test Driver

You are going to build on the BST code you wrote for part 1. Implement a splay tree (SPLT) by adding the splaying functionality to your basic BST. Use the same main class test driver you used for Part 1. You will have to make small changes, obviously ( to make objects of type Splay tree instead of BST), but it should accept and execute the same commands/operations. This is because your SPLT is a BST with splaying added to the appropriate access methods.

What to Hand-in

Hand in your code as per the instructions under Assignment 4 Part 2 in the WorkBase.
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.

There is some redundency here with the code for part 1, 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.

Details

1. For this main driver, implement the random fill operation. It was optional in part 1, but we will need it for the analysis in part 3 so implement it now in part 2. The user command is "f" and the driver should then ask the user for a positive integer indicating how many random strings to generate and put into the tree. Write your random code to generate strings with random lengths between 6 and 10 characters (the code I gave you is parameterized to do this).


2. While it is not likely that the random generator will create duplicates, we are ignoring duplicates in insert. In the case you do get duplicates, do not count that duplicate as one of the strings being generated. For example, if the user asks for 100 random strings to be inserted, and you get 2 duplicates generated, the tree should not end up with only 98 nodes in it -- it should end up with 100 nodes containing 100 unique values.