This is an optional assignment. If you choose to do it, your grade on the programs will be computed from your best 4 program grades, including this assignment. This assignment will have just one due date, the end of the term.
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.
Write an implementation of height-balanced binary search trees in a classical style, similar to what was done in class. Only implement
Then 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.
Hints
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.
You will want a function printtree(t,n) that prints tree t with the line showing the root of the tree indented n "units" (where a unit is some number of spaces) and other lines indented appropriate amounts from there. I will use two spaces for a unit. For example, if t is the tree
300
/ \
80 500
then printtree(t,6) would print
leaf: 80
node: 300
leaf: 500
where the middle line has been indented 6 units (12 spaces), and the
other lines have been indented 7 units.
You indent each subtree one more unit.
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 tree class will use a 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
};
Notice that the extractMin and extractMax operations are not part
of this class. They are implemented in the classical data type
because they are 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.
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.
Pay attention to the trees that you get. If your program is supposed to be balancing, but the trees are unbalanced, something is wrong. You might want to write a function, just for testing, that tells whether a tree is balanced by checking all of the nodes. If it detects an unbalanced tree, you might make your program print a warning.
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.)