CMSC132 Summer 2017

Project:Polymorphic Binary Search Tree

Due Date:July 17,2017 11:59 pm
Assignment Type: Closed (See Policy)

Overview

This project consists of implementing the methods of the EmptyTree, NonEmptyTree, PolymorphicBST, PlaceKeysValuesInArrayLists classes. The complete javadoc for the project can be found at javadoc documentation.

The second part of your project consists of doing a simple performance analysis and writing a short report.

Objectives

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.

Grading

Clarifications

Any clarifications or corrections associated with this project will be available at Clarifications.

Code Distribution

The project's code distribution is available by checking out the project named PolymorphicBST. The code distribution provides you with the following:

Binary Search Tree Specifications

Design

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 NonEmptyTree object.

Design and Implementation Restrictions

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

Requirements

Performance Report

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: