To be written in c++

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.)

A default constructor with the signature

 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.

A constructor with the signature

 ExpBST::ExpBST(int depth, int minHeight, 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.

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

 int getMaxRebalanceDepth() const ; int getMinRebalanceHeight() const ; float getRebalanceFactor() const ; 

A copy constructor with the signature

 ExpBST::ExpBST(const ExpBST& other) ; 

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

A destructor with the signature

 ExpBST::~ExpBST() ; 

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

An overloaded assignment operator with the signature:

 const ExpBST& ExpBST::operator=(const ExpBST& rhs) ; 

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

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

 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.

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:

 bool ExpBST::remove(int key) ; 

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

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

 bool ExpBST::find(int key) ; 

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

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.

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

 int ExpBST::getNumRebalance() const ; int ExpBST::getFailedRebalance() const ; int ExpBST::getExceedsHeight() const ; 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.

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:

 void ExpBST::inorder() ; 

For example, calling inorder() on the following BST should produce the string:

(((((3:0:1)7:2:4((9:0:1)11:1:2))14:3:8((15:1:2(17:0:1))20:2:3))22:4:13(((24:0:1)26:1:2)30:2:4(37:0:1)))41:5:22((((50:0:1)54:1:3(59:0:1))60:2:4)64:3:8((71:1:2(75:0:1))79:2:3)))

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.

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

 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.)

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

 bool ExpBST::empty() const ; // tree has no nodes int ExpBST::height() const ; // height of tree int ExpBST::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.