Program 1 – AS/AK/ITEC 2620 3.0, Section M

Purpose

1. To demonstrate the cost to implement a sorted data set for various data structures.
2. To learn how to develop and use linked data structures.

The Sorted Interface

The sorted interface has the following methods for a data set of ints.
public void clear ();
This method will delete all items in the data set.

public int delete (int value);
This method will attempt to delete the item in the data set with the given value.  If the item exists, the method will return the number of items that it had to examine to find the given item.  If the item does not exist, the method will return 0.

public int find (int value);
This method will attempt to find the item in the data set with the given value.  If the item exists, the method will return the number of items that it had to examine to find the given item.  If the item does not exist, the method will return 0.

public int insert (int value);
This method will insert a new item into the data set with the given value.  The method will return the number of items that it had to examine to find the location at which the new item should be inserted.  Note: you may assume that no duplicate values will ever be inserted into the data set.

public void printAll ();
This method will print all items in the data set in ascending order.

The source for the interface is given here.

The Linked Data Structures

For this program, you must implement the Sorted interface in three classes.  These classes will represented a linked list and two binary search trees.  The two binary search trees will only differ in how the delete() method is implemented (see below).  Thus, these two binary search tree classes are best implemented as subclasses of a base class that implements the other four methods.

The Basic Node

To implement the linked data structures, you must use the following Node class (or a subclass derived from it).  This class holds three fields -- an int value and two links.
 

The Linked List

Implement the Sorted interface using the above Node class (or a subclass derived from it).  Your linked list must have the smallest item in the data set as its first element.

The Base Binary Search Tree

Implement the Sorted interface using the above Node class (or a subclass derived from it).  This class should be abstract with the delete method implemented as abstract.

The delete() Method

When deleting a Node from a binary search tree, there are four cases:
  1. The Node is a leaf -- just delete the Node, and have the parent point to null.
  2. The Node has no left child -- delete the Node, and have the parent point to the right child of the deleted Node.
  3. The Node has no right child -- delete the Node, and have the parent point to the left child of the deleted Node.
  4. The Node has two children.  The two types of BSTs will implement this part differently.

A Slow Binary Search Tree

This class should be a subclass of the above superclass.  For the case when the deleted Node has two children, the delete() method for this class will delete the Node, have the parent point to the left child of the deleted Node, and then the right child of the deleted Node will be re-inserted onto the BST.

For example: if 3 is deleted from the following tree,

     3
    / \
   /   \
  1     5
   \   /
   2   4

then the resulting tree will be

     1
      \
       2
        \
         5
        /
       4

A Fast Binary Search Tree

This class should be a subclass of the above superclass.  For the case when the deleted Node has two children, the delete() method for this class will delete the Node, have the parent point to the largest value in the left sub-tree of the deleted Node -- i.e. this value will replace the deleted Node in the BST.

For example: if 3 is deleted from the following tree,

     3
    / \
   /   \
  1     5
   \   /
   2   4

then the resulting tree will be

     2
    / \
   /   \
  1     5
       /
       4

Examples

In order to test your classes, the following test driver (which calls a static driver class) and sample input and output are provided.  As you can see from the source, the test driver assumes that your classes are named "LinkedList", "BSTSlow", and "BSTFast"; and that their default constructors will create new instances of empty data structures.  Thus, if your classes are implemented correctly, the following two commands should create the sample output:
javac TestDriver.java
java TestDriver input1_1.txt
Hint: you may modify the test drivers to test one class at a time.

Submission

To increase the ease of submission and marking, you will submit only one file.  After developing your classes in four separate files, cut and paste them into the following template.  As you can see in this template, only the main driver file is public, and the four required classes have no modifiers.  To test this file, place it in a directory with the StaticDriver, Node, and Sorted .class files.  Note: if you create any additional classes (e.g. a subclass of Node), they must also be included *in* the submitted file.

Submit this file by following the standard on-line instructions.  Specifically, from your AML account, you should type

submit 2620 a1 Program1.java
Note: depending on the stability of the submit program, you may have to do this from your home directory.

Submission Reminder

Remember, you may resubmit as often as you like before the duedate -- each submission will over-write the previous submission.  You are stronly encouraged to submit partially working programs well in advance of the duedate.  Over a four week period, an inability to submit anything will limit any consideration for difficulties you may encounter near the duedate.

Marking

The program will be marked out of 20 -- 5 for style and 15 for program execution.  Note: execution will be marked in approximately the given order, and an improperly implemented clear() method may hamper the evaluation of some parts.
Style Execution