First solution due:
Second solution due:
This assignment has you implement an abstract data type and a tester for that abstract data type. Follow a refinement plan such as the one at the end of the assignment.
DO NOT ATTEMPT TO WRITE ALL OF THE PROGRAM BEFORE DOING ANY TESTING.
START RIGHT AWAY. DO NOT WAIT.
Write an implementation of height-balanced binary search trees in a "classical" style, similar to what was done in lectures. (Note: The phrase classical style refers to the style without using classes, since that is an older style. It is still preferred sometimes for its simplicity.) Only implement
After implementing the classical data type, implement the abstract data type as a class. The class can be designed as a wrapper of the classical implementation. See below.
Hints: Check for these common errors.
Write a program that reads four numbers a, b, c, and d from the user, where it is required that a < b and c < d. The program should then do the following.
Insert the numbers a, b, a+1, b-1, a+2, b-2, ... into an initially empty tree, until all integers from a to b have been inserted. For example, if a = 1 and b = 10, then the order of the insertions is 1, 10, 2, 9, 3, 8, 4, 7, 5, 6.
Print the tree. Check that the tree is balanced.
For each of a, a+1, ..., b, whether the number is in the tree. For example, if a = 1 and b = 10, check that each of the numbers from 1 to 10 is in the tree. If any are not, print a complaint.
Remove the numbers c, d, c+1, d-1, c+2, d-2, ..., in that order, from the tree.
Hints
Be sure that the application does what is requested. Do not try to be fancy and do something else.
Run some tests. Do not stick only with very small tests. Put some stress on your program. Look at the results. Are they right? Are the trees balanced?
A reasonable way to print a tree is to use indentation to show the structure of the tree. Tree
300
/ \
80 500
would be printed as follows.
leaf: 80
node: 300
leaf: 500
Tree
20
/ \
10 55
/ \ \
4 17 75
/
12
would be as follows.
leaf: 4
node: 10
leaf: 12
node: 17
null
node: 20
null
node: 55
leaf: 75
This way, you can see the structure of the tree in the indentation.
Notice the null trees, showing empty subtrees. If both of the subtrees
of a node are null, the node is shown as a leaf, and its null subtrees
are not shown. This is done to conserve space, because there are usually
many leaves.
The functions.txt file contains a function PrintTree(t,n) that prints tree t with its root indented n units.
Often, a class is created by writing a classical implementation of an abstract data type (without classes or any attempts to hide data), and then writing a class that acts as an object-oriented interface to that classical data type. That is what you should do here. Your Set class will use the binary search tree type that is implemented in the way discussed in class. Since a tree represents a set of numbers, call the class Set. The set is supposed to hide the way that it implements sets.
A set object will hold a binary search tree. Here is what your set class will look like.
class Set {
private:
Tree t;
public:
Set(); // Initially, a set is empty.
~Set(); // Destructor: recovers memory.
void Insert(int x);
void Remove(int x);
bool Member(int x);
bool IsEmpty();
void PrintTree(); // For testing only
bool Balanced(); // For testing only
};
Notice that the extractMin operation is not part
of this class. It is implemented in the classical data type
because it is needed to do deletions.
The class implementation uses the classical data structure to do the job. For example, if you have an insert operation in your binary search tree data structure, then your Insert operation for class Set will look like this.
void Set::Insert(int x)
{
::insert(t,x);
}
Function ::insert is the insert function that is not part of the class.
Here is a suggested plan for implementing this program.
Implement the tree classical data structure with just the lookup and insert operations, without rebalancing. Write the first few steps of the tester, but make them refer directly to the classical data structure. Do not use the class yet. Test your program.
Modify the classical data structure implementation of the insert operation so that it rebalances. This will involve implementing the rotation operations. Test the program again. Call the Balanced function to check that the tree is balanced. If there are problems, fix them. Be careful when writing the rotation operations to avoid mistakes. Bugs in rotations are difficult to find by debugging alone.
One way to deal with this is to comment out all but one of the rotation operations, and instead implement it as a "stub" that has no effect. For example, your implementation of a function called DoubleRotateRightwards might look like this when it is a stub.
void DoubleRotateRightwards(Tree& t)
{}
That way, you can introduce and test one rotation operation at a time.
When testing the rotations, put a print in each rotation that says that it is being performed. Make sure your tests do all of the rotations. If they don't, try some other tests.
Add the ExtractMin function, without rebalancing. Write a tester to call it on a few inputs. Check your results.
Now make ExtractMin rebalance. Test it with the same tester. You should get different results for the trees.
Add the remove function. It uses ExtractMin. Be sure that it rebalances. Add the rest of the test to the program, still using the classical data structure directly.
Now write the Set class. Modify your tester to use the set class instead of using the classical data structure directly. Test your program.
Pay attention to the trees that you get. If your program is supposed to be balancing, but the trees are unbalanced, something is wrong.
Pay attention to your tests. Don't presume that, just because your program passes a few very small tests that it will work on larger trees. Also don't presume that a test has produced the correct answer without looking at the answer to see whether it is correct.
Look for memory leaks. Be sure to delete memory that is no longer needed. However, be wary of deleting memory that you still need.
The final program MUST be written as a separate application and abstract data type. The abstract data type can be put into one module (holding the class Set and the binary search tree implementation) or in two modules (one holding the class Set and another holding the binary search tree implementation). The testing application must be in a separate file.
The application MUST only include the header file of the set class. It must not include the implemenation (.cc or .cpp) file. Use a linker to link the parts together. (Of course, the application can also include other header files, such as iostream.h.)