CMSC 132 -- Project 5

Binary Search Trees

Project Due: Friday, 4/8/05 at 11:00 PM

Closed Policy

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:


Important Restrictions

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.


Further Documentation

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



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.

Using Trees as Maps

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:


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:

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.

Singleton Design Pattern

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.


What YOU Will Implement

The following modules have been written for you.  DO NOT MODIFY THEM:

You will write three classes:

Skeleton versions of these three classes have been provided.


Office Hours Help

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.


Test Cases

Public Tests(0)

There are no public tests!  You are responsible for coming up with your own test cases for this project.

Release Tests(11)

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.

Student Tests

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: