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.
START RIGHT AWAY. DO NOT WAIT.
Write an implementation of height-balanced binary search trees as an abstract data type. Only implement
Implement the abstract data type as a class. However, the class can be designed as a wrapper of a classical implementation. See below.
Hints: Check what you write for these common errors.
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 a 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.
node: 300
leaf: 80
leaf: 500
Tree
20
/ \
10 55
/ \ \
4 17 75
/
12
would be as follows.
node: 20
node: 10
leaf: 4
node: 17
leaf: 12
null
node: 55
null
leaf: 75
This way, you can see the tree in the indentation. Be sure
to include the null subtrees at nodes with just one child,
since otherwise it is impossible to know whether the single child
is a left child or a right child.
You will want a function printtree(t,n) that prints tree t with its first line indented n "units" (where a unit is some number of spaces) and remaining 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
node: 300
leaf: 80
leaf: 500
where the entire thing has been indented 6 units (12 spaces).
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 MakeEmpty();
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);
}
Be careful. If you use exactly the same name in the class as you use
in the tree data structure, you might need to put :: in front of
it to ensure that the compiler understands that you mean the one from
outside the class, not the one inside the class. For example, if
both insert operations have name Insert, you write
void Set::Insert(int x)
{
::Insert(t,x);
}
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.
Look for memory leaks. Be sure to delete memory that is no longer needed. However, be wary of deleting memory that you still need. A good idea is to enclose all of your deletes in ifdefs. For example, if you are going to delete a node pointed to by pointer r, write
# ifdef DO_DELETIONS
delete r;
# endif
Normally, you write
#define DO_DELETIONSat the top of the program. That way, the delete instructions are compiled. If your program is not working, however, and you suspect you might be creating dangling pointers, comment out that line, as
//#define DO_DELETIONSand compile again. If the problem goes away, you know what the source of the problem is.