@DefaultAnnotationForParameters(value=edu.umd.cs.findbugs.annotations.NonNull.class) @DefaultAnnotationForMethods(value=edu.umd.cs.findbugs.annotations.NonNull.class)

Package cs132.searchTree

See:
Description

Interface Summary

Tree<K extends Comparable<K>,V>

This interface describes the interface for both empty and non-empty search trees.

Class Summary

EmptyTree<K extends Comparable<K>,V>	This class is used to represent the empty search tree: a search tree that contains no entries.
NonEmptyTree<K extends Comparable<K>,V>	This class represents a non-empty search tree.
PublicTests
SearchTreeMap<K extends Comparable<K>,V>	This class provides a partial implementation of the Map interface.
StudentTests

Package cs132.searchTree Description

This package uses a binary search tree to implement part of the Map interface. The binary search tree is to be implemented using polymorphism, with two different implementations of the TreeNode interface.

What you must implement

You must implement the methods of the EmptyTree and NonEmptyTree. You are provided with implementations of SearchTreeMap and Tree; do not change these.

Testing

It is a required and graded part of your project that you develop andd 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 on TreeNodes return references to TreeNodes. 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 InternalNode.

Design and Implementation Restrictions

This project is designed to help you develop your skills at:

• recursion
• polymorphism
• testing

As such, there are a number of design restrictions you must obey in your implementation of EmptyNode and InternalNode:

• 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.