Objective

The objective of this project to implement a polymorphic binary search tree.  This project is designed to help you develop your skills at recursion, polymorphism and testing.  This homework is considered a closed homework.  Make sure you read the open/closed policy before continuing working on this project. 

Overview

For this project you must implement the methods of the EmptyTree and NonEmptyTree classes. You are provided with implementations of SearchTreeMap and Tree; do not change these.  Complete documentation for this project can be found at javadoc documentation

Your project will be graded as follows:

• Tests (75 %)

  • Public JUnit tests  (3 %)

  • Release JUnit tests (30 %)

  • Secret JUnit tests ( 42 %)

• Student Tests (20 %)

• Style (5 %)

Testing

It is a required and graded part of your project that you develop and submit test cases that test your code. You only get the one test case in the class PublicTests, and the release tests all have unhelpful names such as testOne and testTwo. The TA's have been instructed that they should not help you debug your code unless you have written test case on which your code misbehaves.

Using a code coverage tool, such as Clover, is one helpful tool to access whether your tests test all parts of your implementation.

In addition to the release tests, there are additional secret test cases. Don't assume that just because your implementation passes the release tests, it is correct.

Design

The SearchTree class implements some of the functionality of the Map interface (although not all). A SearchTree object is just a wrapper around a TreeNode, which is actually used to implement search trees.

Note that the insert and delete methods return references to Tree objects. In many cases, these functions may return a reference to the this object.

Design and Implementation Restrictions

There are a number of design restrictions you must obey in your implementation of EmptyTree and NonEmptyTree classes:

• You may not use any form of looping construct
• You may not use any classes from java.util or any arrays
• You may not use instanceof
• You may not add any additional non-private methods or variables.

These restrictions do not apply to your test cases; you may write them however you wish.

Submission

Submit your project using the submit project option associated with Eclipse. 

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects.  We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Program

Web Accessibility