Project Assignment
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. 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.
- Setting timers to record how long it takes you to search for the objects in each data structure
- Creating more integer ?les and seeing their effects
- Performing the same experiments on 100, 200, 300, ...N objects and graphing the results.