For this project, you will perform a series of searches for 1000+ objects stored in a Binary
Search Tree, an AVL Tree, and a Splay Tree. For each search, you will record how many objects
you had to visit to complete the search. You will analyze your results from the different data
structures.
Implement
– You should have your 1000+ objects stored in a vector (I recommend you start with your
Project 2 code). Add at least three more dummy objects to the vector. That way, you only
need integer indexes to determine which objects you are searching for, and you will have at
least three objects in the vector that will not be in the tree structures.
– Say you have N objects in your vector. You will need to create three les of integers: a sorted
list in range [0, N-1]; a random ordering of the same integers; and a list of integers [0, N/5]
that repeat each integer ve times in a row (i.e. 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 etc.)
– Store the objects (excluding the dummy objects you added to the vector) in a Binary Search
Tree, an AVL Tree, and a Splay Tree. I recommend that you start with the textbook code
(http://users.cs.u.edu/~weiss/dsaa_c++4/code/ ). Note that you will need to overload the <,
>, ==, and << operators to compare two objects of your class. You should copy the entire
class from the textbook (don’t cherry pick parts or your program will have memory leaks). Any
code that is not original must be cited in your writeup (including textbook code).
– Modify the code so that a search of the tree also stores the depth of the last node visited. I
recommend that you pass the address of an integer to the contains method and modify it
inside the method(s).
– Read in from each of the three les, an integer at a time, searching for the object at that
integer index in the vector. Search the BST, the AVL tree, and the Splay tree. Store the depths
of each search.
– Analyze the data. Plot graphs of the depths for the 1000+ searches in each of the three tree
structures. Look at maximums, minimums, averages, and patterns, compare and contrast the
different tree structures for each data le, and draw conclusions about when you would use
each tree structure. Discuss complexities and their effects. All of this will go in your writeup.
– You must submit your .cpp le(s), your data le(s) (including the three integer les), and your
writeup. Please submit your writeup in PDF format.