This project consists of implementing the methods of the
The complete javadoc for the project can be found at
The second part of your project consists of doing a simple performance analysis
and writing a short report.
The objective of this project is to implement a polymorphic binary search
tree. This project is designed to help you develop your skills at recursion,
polymorphism and testing.
- (85%) Tests
- (5%) Public JUnit tests
- (30%) Release JUnit tests
- (50%) Secret JUnit tests
- (15%) Performance Report
Any clarifications or corrections associated with this project will be
available at Clarifications.
The project's code distribution is available by checking out the
project named PolymorphicBST. The code distribution provides you with
- A package named performanceReport - Includes an example of how to
generate timing information. It also includes a shell file (word doc) where
you will provide a report (additional information below).
- A package named tests
- A package named tree - Includes the tree
Binary Search Tree Specifications
Notice that the insert and delete methods on Tree objects return references to
Tree objects. In many cases, these functions may return a reference to the
this object. However, in some cases they can't. For example.
EmptyTree.getInstance.insert("a", "1") has to return an instance of an
Design and Implementation Restrictions
- You may not use any form of looping construct.
- You may not use any arrays.
- You may not explicitly check a Tree to see whether it is an EmptyTree or
- Your EmptyTree and NonEmptyTree implementations may not have any
comparisons against the null value.
- You should not need to do any casting for this project. If you are
casting, you are probably not using generic programming correctly.
- If you insert multiple values with the same key, only the value
associated with the most recent insertion will be saved.
- You may not use any classes from java.util except ArrayList, Set and HashSet.
- You may not add any public methods.
- You may not check whether a tree is empty by using comparisons similar to
- left == EmptyTree.getInstance()
- tree.size() == 0
- Other comparisons similar to the above
You are expected to use polymorphism (and exception handling, where
appropriate) to handle the differences between empty and nonempty trees.
Failure to do so will result in a large negative adjustment to your project
- You may not use Collections.sort for this project.
- You may not use instanceof.
- You may not use getClass().
- The delete method must use the approach described in the lecture slides.
You may not implement delete by creating a new tree and inserting all the
keys from the source tree except the one you want to delete.
- For the Subtree method you may not create an empty tree and traverse the
whole tree inserting only those entries within the specified range. If a
simple check will tell you that an entire subtree can be excluded, your
implementation should not traverse that subtree.
The above restrictions do not apply to your test cases; you may write
them however you wish.
- Verify that your project passes the submit server tests (https://submit.cs.umd.edu/).
- IMPORTANT → If you have a problem with your code
and need assistance during office hours, you need to have a student
test(s) that illustrates the problem you are experiencing.
- See Student Tests
for information regarding the implementation of student tests.
- See Style Guidelines for information
In addition to the above requirements, you must compare the efficiency of PolymorphicBST
and java.util.TreeMap classes for both sorted and unsorted inputs. You must then
write a report (to be left in the file performaceReport.docx) that consists of two parts:
Two tables showing speed comparison between polymorphic tree and Java's TreeMap.
Use TreeSpeed.java for information on how to obtain time information. Each table
should have two columns: data size (number of values used) and the time (in milliseconds).
Each table should have at least five entries. The first table will show results for trees
created with numbers in a sequence and the second table with trees created with random numbers.
Two or three lines explaining the table results.
When you add your report you need to refresh the project before submitting.
To refresh a project: right-click on the project and select Refresh.