Assignment

Note: Running time is one of the most important considerations in the implementation of a data structure. Programs that produce the desired output but exceed the required running times are considered wrong implementations and will receive substantial deductions during grading.

Your assignment is to implement the Experimental BST described above. You may start with a binary search tree class from the textbook or given by your instructor, if you prefer. You may also design your own. Each option has advantages and disadvantages. A primary objective of this programming assignment is to have you use recursion. So, one component of grading will evaluate how elegantly you employ recursion to implement this data structure. (Yes, you are being graded on aesthetics!)

Since you will choose the design of the class definitions, no header files will be distributed with this project. Instead, the requirements are:

- The name of the class must be ExpBST.
- The header file must be named ExpBST.h (case sensitive).
- A client program that includes ExpBST.h should compile correctly without including any other header files.
- Your ExpBST class must have the member functions with the specified signatures indicated below.
- The implementation of your member functions and any supporting functions must be placed in a single file named ExpBST.cpp.
- No STL classes may be used in this programming project.

In order to implement ExpBST efficiently, your data structure must be able to determine the size and height of a subtree in constant time. You must have data members for the height and size of a subtree in the class representing the root of a subtree of a ExpBST. The height and size data members must be updated whenever the height or size of that subtree changes. The update must not affect the asymptotic running time of insert, delete and search. These must still run in time proportional to the height of the tree.

To keep things simple for this project, we will just store int values in ExpBST. Although, well-written code should allow you to easily change the type of data stored in the data structure.

Here are the member functions you must implement in your ExpBST class. (You will need to implement others for your own coding needs.)

1. A default constructor with the signature
2. ExpBST::ExpBST() ;

We would usually use the next constructor to create an ExpBST object. However, a class without a default constructor can be problematic, so we will include a default constructor.

3. A constructor with the signature

4. ExpBST::ExpBST(int depth, intminHeight, float factor) ;

Here depth specifies the maximum depth taken by the truncated inorder walk when we take apart an ExpBST during the rebalancing operation. Recall that the root has depth 0, the children of the root have depth 1. The parameter minHeightindicates the height of the shortest tree that will be considered for rebalancing. For example, if minHeight is 5, then we will not rebalance subtrees of height 4, 3, 2, 1 or 0. Finally, factor is the multiple of log m we use to define when a subtree is unbalanced. For example, if factor is 2.0 then a subtree with m nodes and height greater than 2.0 log m is unbalanced. Note that factor is allowed to have fractional values.

For simplicity, you may store these values in static data members. This does mean that a program can only have ExpBST trees of the same type. Otherwise, these values would have to be associated with the root of the tree, and the root would have to be distinguished from other nodes in the tree.

5. Your ExpBST class must also have the following functions that return the values passed to the constructor above.

6. intgetMaxRebalanceDepth() const ;

7. intgetMinRebalanceHeight() const ;

8. float getRebalanceFactor() const ;

9. A copy constructor with the signature

10. ExpBST::ExpBST(constExpBST& other) ;

The copy constructor must make a deep copy and create a new object that has its own allocated memory.

11. A destructor with the signature

12. ExpBST::~ExpBST() ;

The destructor must completely free all memory allocated for the object. (Use valgrind on GL to check for memory leaks.)

13. An overloaded assignment operator with the signature:

14. constExpBST&ExpBST::operator=(constExpBST&rhs) ;

The assignment operator must deallocate memory used by the host object and then make deep copy of rhs.

15. An insert() function that adds an item to ExpBST that has the following signature:

16. void ExpBST::insert (int key) ;

The insert() function must run in time proportional to the height of the ExpBST. Your ExpBST implementation must not allow duplicates. If the insert() function is invoked with a key value that already stored in the ExpBST, your insert()function should do nothing, except that it may rebalance the tree if an imbalance is detected.

17. A remove() member function that finds and removes an item with the given key value. The remove() function should return a boolean value that indicates whether the key was found. Your remove() function should not abort or throw an exception when the key is not stored in the BST. The remove() member function must have the following signature:

18. bool ExpBST::remove(int key) ;

For full credit, your remove() method must run in time proportional to the height of the tree.

19. A find() function that reports whether the given key is stored in the tree. The signature of the find() method should be:

20. bool ExpBST::find(int key) ;

For full credit, your find() method must run in time proportional to the height of the tree.

21. A member function rebalance() that rebalances a subtree of the ExpBST as described above. The running time of rebalance() must be constant. Note that a proper implementation would require you the keep track of the size and height of the subtree. Read the description above.

22. Your ExpBST class must have the following functions report on statistics of the ExpBST tree related to the rebalance operation:

23. intExpBST::getNumRebalance() const ;

24. intExpBST::getFailedRebalance() const ;

25. intExpBST::getExceedsHeight() const ;

26. void ExpBST::resetStats() ;

The function getNumRebalance() must return the total number of calls to rebalance() since the beginning of the program or since the last call to resetStats() whichever one is later. Similarly, getFailedRebalance() must return the total number of calls to rebalance() that did not result in a shorter subtree, and getExceedsHeight() must return the total number of calls to rebalance() that resulted in a subtree that is still "too tall" as defined by the factor parameter given to the constructor. Finally, resetStats() will reset these 3 counts to zero.

As before, for the sake of simplicity, you may store these three counts in static data members, even though this may not be the most correct object-oriented design.

27. A member function inorder() that performs an inorder walk of the ExpBST and at each node, prints out the key followed by a : followed by the height of the node followed by another : followed by the size of the subtree rooted at that node. Furthermore, inorder() should print an open parenthesis before visiting the left subtree and a close parenthesis after visiting the right subtree. Nothing should be printed when inorder() is called on an empty tree, not even parentheses. This function will be used for grading, so make sure that it works correctly. The function must have the following signature:

28. void ExpBST::inorder() ;

Fig. 1: an unbalanced binary search tree.

Here, the 41:5:22 indicates that the node with key 41 has height 5 and that there are 22 nodes in the tree. The output before 41:5:22 is produced by visiting the left subtree. Everything after 41:5:22 is produced by visiting the right subtree.

29. A function locate() that returns whether there is a node in a position of the ExpBST and stores the key in the reference parameter. The position is given by a constant C string, where a character 'L' indicates left and a character 'R' indicates right. The locate() function must have the signature

30. bool ExpBST::locate(const char *position, int& key) ;

For example in the BST above:

- A call to locate("LRL",key) should return true and store 26 in key.

- A call to locate("RRLR",key) should return true and store 75 in key.

- A call to locate("RLR",key) should return false and not make any changes to key since there is not a node in that position. Note: locate() must not abort and must not throw an exception in this situation.

- A call to locate("",key) should return true and store 41 in key, since the empty string indicates the root of tree.

The grading programs will use locate() to check if your BST is balanced and that the keys are stored correctly. So, make sure locate() is correct. (This is not a difficult function to implement.)

31. Your ExpBST class must have the following functions to report on attributes of the ExpBST tree:

32. bool ExpBST::empty() const ; // tree has no nodes

33. intExpBST::height() const ; // height of tree

34. intExpBST::size() const ; // number of nodes in tree

Since the height and size of each subtree is stored at each node, these functions must run in O(1) time.

Your code must run without segmentation fault and without memory leaks. For grading purposes, memory leaks are considered as bad as segmentation faults. This is because many segmentation faults are caused by poorly written destructors. A program with an empty destructor might avoid some segmentation faults but will leak memory horribly. Thus, not implementing a destructor or not deleting unused memory must incur a penalty that is equivalent to a segmentation fault.

Implementation Notes

Here we list some recommendations and point out some traps and pitfalls.

- Here is the recommended incremental development stages for this project:

1. Pick an implementation of binary search trees and understand it well. (If you can't explain how insertion into an empty tree works correctly, then you do not understand it well.)

2. Modify the BST implementation to keep track of the height and size at each node. Do some timing runs to make sure that your modifications take only O(1) time to update each node.

3. Write the locate() function. Do not put this off until the end because it is used for grading and you will receive a bad grade if you do not have a working locate() function. Plus it is recursive, so you will have some practice writing a recursive function that works with binary search trees.

4. Write the truncated inorder walk that constructs the array of singleton nodes and subtrees. Use gdb to examine this array and to make sure that the array constructed is as you expect. Make sure that you are not copying entire subtrees in this step.

5. Instead of using a function that determines the shortest subtree, just pick a singleton node near the middle of the array as the new root. Do this recursively and you should be able to put the binary search tree back together.

6. Write the recursive function that finds the best singleton node to be the new root of a subtree when you rebalance.

At each stage of this process, you should have code for a BST class that does insert, remove and find without seg faulting or leaking memory. You should test your code after each stage so you know that any bugs that crop up was likely caused by the most recent changes. If valgrind reports memory read or write errors, fix these right away even if there are no memory leaks. These errors mean you have messed up memory some how. If you do not fix them right away, the bugs will manifest themselves in horrible ways later.

If you show up for office hours on the day the project is due with a few hundred lines of code that has not been debugged incrementally, it is unlikely that anyone will be able to help you effectively.

- Remember that we are defining the height of a leaf node to be 0. (The leaf node here is a node that contains actual data, not the null pointers at the bottom of a BST.)

- There are many places where the height and size of a node needs to be updated including, for example, in the rebalance procedure.

- When you insert a key that is already in the binary search tree, you are supposed to do nothing. (This is one of the standard alternatives.) This means you have to be careful about how you update the sizes of the subtrees, because when you insert a duplicate, the size does not change! (and you won't find out that it is a duplicate until you've found its 'clone').

- Remember that we are checking whether a node is unbalanced (actually whether the subtree rooted at that node is unbalanced) when we return from the recursion.

- Your rebalance() operation should be done in two phases (both are recursive). In the first phase, you determine which singleton node should be the root of the new subtree. You do so by trying every singleton node as the root and recursively determining the optimum height of the left subtree and the optimum height of the right subtree. This will also let you determine the optimum height of the subtree (which you will need for recursion).

During this first phase, you DO NOT reconstruct the subtree. You cannot reconstruct the subtree because you do not yet know which singleton node should be the root. The problem isn't reconstructing the subtree at the top level. The problem is that you don't want the recursive calls to construct the subtree when the choice of the top level root isn't optimal.

Once you have figured out which singleton node should be the root, you can go ahead and reconstruct the subtree by picking that node to be the root and recursively reconstructing the left subtree and the right subtree. Note that reconstructing the left subtree or the right subtree will again require you to select the optimum root for each subtree.

Thus, you need two functions (both are recursive). One function called shortestBST() that tells you which singleton node should be the root and what the height of the shortest BST would be. The second function recursively constructs the binary search tree. Note that the second function needs to call shortestBST() as well.

What to Submit

Before submitting, remove all extraneous output from your program. (Just comment them out.) Your typescript file should have only a few hundred lines of output, not 195 megabytes of text. (Yes, that's the record.) We will not look at the typescript file beyond the first 1000 lines.

You must submit the following files to the proj3 directory.

- ExpBST.h
- ExpBST.cpp
- Driver.cpp

The Driver.cpp program should include tests showing the parts of your project that work correctly. All of your implementation should be placed in ExpBST.h and ExpBST.cpp. Do not submit other files.

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using this Unix command command.

cpExpBST.h ExpBST.cpp Driver.cpp ~/cs341proj/proj3/

Your code should compile with the test programs using these Unix commands on GL:

g++ -I . ../../00Proj3/p3test1.cpp ExpBST.cpp -o t1.out
g++ -I . ../../00Proj3/p3test2.cpp ExpBST.cpp -o t2.out
g++ -I . ../../00Proj3/p3test3.cpp ExpBST.cpp -o t3.out
g++ -I . ../../00Proj3/p3test4.cpp ExpBST.cpp -o t4.out
g++ -I . ../../00Proj3/p3test5.cpp ExpBST.cpp -o t5.out
g++ -I . ../../00Proj3/p3test6.cpp ExpBST.cpp -o t6.out
g++ -I . ../../00Proj3/p3test7.cpp ExpBST.cpp -o t7.out
g++ -I . ../../00Proj3/p3test8.cpp ExpBST.cpp -o t8.out
g++ -I . ../../00Proj3/p3test9.cpp ExpBST.cpp -o t9.out

Use the Unix script command to record yourself compiling these programs. Then, use p3test8.cpp and p3test9.cpp to perform some timing runs:

time ./p3test8.out 100000 3 5 2.0
time ./p3test8.out 200000 3 5 2.0
time ./p3test8.out 400000 3 5 2.0
time ./p3test9.out 100000 3 5 2.0
time ./p3test9.out 200000 3 5 2.0
time ./p3test9.out 400000 3 5 2.0

Finally, run p3test8.cpp and p3test9.cpp using the values of depth, minimum height and factor that you recommend in the tuning exercise.
Finally, remember to exit from script.

Attachment:- Project-Rrequired-Materials.zip