CMSC132 Summer 2018

Project:Polymorphic Binary Search Tree

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

• (85%) Tests
  • (15%) Public JUnit tests
  • (40%) Release JUnit tests
  • (30%) Secret JUnit tests
• (15%) Performance Report

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:

• 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 classes/interfaces.

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

• 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 NonEmptyTree.
• 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 the following:
  • 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 grade.
• 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.

Requirements

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

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:

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