CMSC 132 -- Project 5
Binary Search Trees
Project Due: Friday, 4/8/05 at 11:00 PM
This is a closed project. You are expected to do all of the work on this project without consulting with anyone other than the CMSC 132 instructors and TAs. Treat this project as though it were a take home exam. If you have any questions about whether or not a certain topic is okay to discuss with classmates or friends, please ask your instructor.
The goals of this project are:
Practice binary search trees
Practice polymorphism
Practice writing test cases
Practice recursion
To make sure that you are not "bypassing" some of the goals of the project, you must abide by the following restrictions in your project implementation. However you do NOT have to abide by these restrictions while writing your own test cases.
You may not use any form of looping construct (No loops at all!)
You may not use arrays
You may not use any classes from Java.util, or similar collections classes
You may not use instanceof
You may not add any non-private methods or fields
Much of the documentation for this project is contained in "JavaDoc" in the project files themselves. JavaDoc is a Java-specific documentation convention that can be used to generate automated html project descriptions. Please read the documentation in the .java files that we have provided, especially the interface Tree.java.
For this project you will implement a "polymorphic" binary search tree, which will be used by another class (SearchTreeMap), which represents a map. In addition to writing two Tree classes, you will also be responsible for writing and submitting your own test cases! The test cases you will write will be graded, and will account for 30% of your grade on this project. The grading of test cases will be based on how thorough your tests are (do they check for all possible cases) and how well they are organized. Try to write several test cases, each of which evaluates whether or not your project is performing correctly on a single task or in a single area.
We have written the SearchTreeMap class for you. It will wrap a Tree and allow the user to manipulate it exactly like a Map. Each node in the underlying binary search tree will contain a "Comparable" key value and a data value of type "Object". Since the intention is to use these trees as though they were maps, you will be implementing methods for your Tree classes like these:
public Tree insert(Comparable key, Object value) // insert the pair <key, value> and return the modified Tree
public Object search(Comparable key) // return the value associated with this key
public Tree delete(Comparable key) // remove the entry associated with this key and return the modified Tree
We say the binary search tree is polymorphic because there will be two types of Trees: EmptyTrees and NonEmptyTrees. An empty tree contains no fields. A non-empty tree has four fields:
Comparable key value
data Object
reference to left child (Tree)
reference to right child (Tree)
If a non-empty tree has no left or right child, then instead of having it's left/right reference refer to null, we will have them refer to an EmptyTree. So both the left and right references of a non-empty tree will always point to another tree -- it's just a question of whether or not that other tree is empty.
When you are implementing various methods, you will notice how convenient this polymorphism is -- you will simply call a method on the left/right child of the current node without having to distinguish whether or not the child is empty or non-empty.
If you think about it, all empty trees are alike! They have no data, so there is no way to distinguish one empty tree from another. For this reason, we will be employing the "Singleton Design Pattern" in our implementation of the empty tree class. This means that we will instantiate exactly one instance of the empty tree class. Anytime a non-empty tree has a missing left/right child, it will refer to this one copy of the empty tree.
The following modules have been written for you. DO NOT MODIFY THEM:
SearchTreeMap (wraps a Tree and treats it like a map).
Tree (interface for both empty and non-empty tree classes).
You will write three classes:
EmptyTree
NonEmptyTree
StudentTests
Skeleton versions of these three classes have been provided.
The TAs have been instructed not to help you debug your code unless you have written a test case that demonstrates that your project is malfunctioning. You should be writing and using your test cases WHILE you are implementing the project, not as an afterthought at the very end. Testing and software development go hand-in-hand.
There are no public tests! You are responsible for coming up with your own test cases for this project.
The release tests have useless names like Test0, Test1, etc. The release tests will give you feedback about how close you are to completing your project, but they will not give you any clues about what kind of test cases you should be writing.
You will write your own test cases and submit them with your project. We will grade your test cases based upon how thorough they are, how well organized they are, and whether or not you have used good programming style on them. How many and what kinds of tests you write are entirely up to you.
Your grade on this project will be calculated as follows: