CMSC 341 Project 2

Assigned March 6, 2013
Due 11:59pm March 31, 2013 April 2, 2013 DEADLINE EXTENDED DUE TO SNOW
Points 100

Objectives

Description

Often times a data structure supports almost all of the operations we need. When that's not the case, we can often augment the data strucutre by adding a data member or two and an additional operation or two.
In this project, you will augment the author's Binary Search Tree (BST) code to support these new operations. Method names below are merely suggestions.

  1. AnyType nthElement(int n) -- returns the n-th element (starting from 1) of the in-order traversal of the BST.
  2. int rank( AnyType x ) -- returns the "rank" of x. The rank of an element is its position (starting with 1) in an in-order traversal.
  3. AnyType median( ) -- returns the median (middle) element in the BST. If the BST contains an even number of elements, returns the smaller of the two medians.
  4. boolean isPerfect( ) -- returns true if the BST is a perfect binary tree.
  5. boolean isComplete( ) -- returns true if the BST is a complete binary tree. This method is for extra credit.
  6. String toString( int nrLevels ) -- generates the level-order output described in the sample output below.
Most of these operations could easily be implemented by performing an in-order traversal inside the BST and perhaps placing the results in an ArrayList. However, such a method is extremely inefficient. Instead, we are going to achieve faster performance by "augmenting" the BST nodes. You will add a new private integer data member ("tree size") to the BinaryNode which stores the size of the tree rooted at that node (including the root). You must develop your own algorithms for these operations, but obviously you will use the new tree size data member to guide your search. Think before you code and think recursively!

The command line for this project has two command line arguments. The first argument is the name of a data file which contains integers separated by whitespace. The second argument is the name of a command file.

Your program will read the integers from the data file and insert them into the BST. It will then read the command file and perform the requested operations and produce the specified output. The data file may contain duplicates. If so, do not insert the duplicate.

The Command File

Each line of the command file represents a single command. Blank lines may occur anywhere in the file and should be ignored. Lines that begin with the pound ('#') symbol are comments and should also be ignored. You may assume that valid commands are well-formed, but not all commands are valid. If you encounter an invalid command you should ignore that line in the file, print an appropriate error and continue to the next command. An appropriate message should be printed for any valid command that produces no results (i.e. finding the rank of a non-existent integer). The following commands will be found in the command file. Note that there is an opportunity for extra credit.

  1. PRINT <number of levels>
    Prints the specified number of levels of the BST according to a level-order traversal. See the sample output below for required formatting and data.
  2. RANK N
    Prints the rank of the integer N. In the tree used for the sample output the rank of 30 is 4 and the rank of 70 is 18. If N is not found in the tree, print an appropriate message.
  3. NTH N
    Prints the N-th integer as if an in-order traversal were performed. If there are less than N integers in the tree, an appropriate error message should be produced.
    In the tree used for the sample output the command NTH 6 prints the value 37.
  4. MEDIAN
    Prints the median value in the tree. In the tree used for the sample output the median value is 47.
  5. REMOVE N
    Removes the specified integer, N, from the tree. If N is not in the tree, print an appropriate error message.
  6. PERFECT This command prints an appropriate message indicating whether or not your BST is a perfect binary tree.
  7. COMPLETE
    This command is for extra credit. If implemented, this command prints an appropriate message indicating whether or not your BST is a complete binary tree. If not implemented, output a message to that effect.
A command file might look this:
# test the RANK funciton
RANK 33
RANK 12365

#find the 33rd element
NTH 33
PRINT 4
REMOVE 67890
MEDIAN

#is the tree perfect or complete?
PERFECT
COMPLETE

#end of command file

Your Tasks

  1. Checkout your Project 2 repository which will contain build.xml.
  2. Copy the /afs/umbc.edu/users/n/i/nicholas/pub/cs341s13/Proj2/BinarySearchTree.java to your local directory.
  3. Create your directory hierarchy suitable for Java and CVS.
  4. Augment the BinaryNode class by adding an integer to store the tree's size (including the root).
  5. Modify the author's BST code as necessary to maintain the tree's size.
  6. Write new BST methods to support the new operations.
  7. Write main( ) and helper functions in a separate file.
  8. Edit build.xml so that the usual ant commands run successfully.

Other Requirements, Notes and Hints

These items cover those topics not addressed elsewhere in the project description. (R) indicates a requirement, (H) indicates a hint, and (N) indicates a note.

  1. (R) Although we are only using the BST for integers, the BST must remain a generic class.
  2. (R) Duplicate values are not allowed. Attempts to insert a duplicate value should be ignored.
  3. (R) Attempts to remove non-existent values should be ignored.
  4. (R) From a coding perspective, the easiest way to avoid duplicate insertions or attempting to remove non-existent elements is to first call find( ). However, this technique is NOT permitted for two reasons.
    Calling find( ) before each insert/remove doubles the running time for these operations and is therefore inefficient.
    Recusively coding the insert/remove methods to handle these situations is a great learning experience.
  5. (R) Each command (and its arguments, if any) read from the file must be echoed as part of the output.
  6. (R) The level order print (PRINT command) outputs the value of each node, the size of the tree rooted at that node, and the value of the node's parent in that order, inside parenthesis, separated by commas. (node value, tree size, parent value). Since the root has no parent, print NULL for the root's parent value. For readability, separate the levels with a blank line and print no more than 6 node/size/parent values per line. If a level requires multiple lines, use consecutive lines (without a blank line between them).
  7. (R) Efficieny counts! Use the most efficient algorithm possible In particular, don't make multiple searches in the tree when one will do. (Yes, we know it doesn't matter from an asymptotic analysis point of view.)
  8. (H) Almost all of these operations should be written recursively, but not necessarily all of them.
  9. (N) Be sure to adhere to the defintions of "perfect binary tree" and "complete binary tree" as used in the text and the course notes. Other material on BSTs may use slightly different terminology.
  10. (N) As is customary, your BST class should not provide any methods for printing. However, the BST can provide a method that formats a string containing information that the user wishes to print. Overloading the toString( ) method is a common technique to achieve this kind of functionality.
  11. (N) The build.xml file provided with this project is new. It should allow you put your data files in your project directory just as Eclipse does (after you've editted it for this project of course).

Sample Output

This output is provided to show the format of the level-order print (5 levels).
This is the level-order print of the tree below.
Level 0:
(55, 21, NULL)

Level 1:
(40, 12, 55) (60, 8, 55)

Level 2:
(30, 6, 40) (45, 5, 40) (70, 7, 60)

Level 3:
(20, 3, 30) (35, 2, 30) (44, 2, 45) (47, 2, 45) (66, 3, 70) (80, 3, 70)

Level 4:
(3, 1, 20) (26, 1, 20) (37, 1, 35) (43, 1, 44) (48, 1, 47) (65, 1, 66)
(68, 1, 66) (77, 1, 80) (90, 1 ,80)

Extra Credit

For 10 points of extra credit implement a method to determine if your binary search tree is a complete binary tree. Your program should output an appropriate message in response to the COMPLETE command in the command file. If you choose not to implement the extra credit, output a message to that effect when the COMPLETE command is read.

Project Grading

Project grading is described in the Project Policy handout. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

See the course policy on late projects.

Project functionality testing will fall into the following categories. The list below does not necessarily include all test possibilities.

  1. Basic Tests
    A small tree with a odd number of integers inserted in random order with no duplciates and no deletion.
    A small tree with an even number of integers inserted in random order with no duplicates and no deletions.
  2. More Complex Tests
    A tree created by random insertions and deletions.
    Attempting to insert duplicate values.
    Attempting to remove non-existent values.
    A tree created from integers inserted in sorted order with or without deletions.
  3. Atypical Tests
    A tree with a single integer.
    An empty tree.
    One or more files which do not exist or cannot be opened.
    A command file with no valid commands.
  4. Strees Tests
    A very large tree built from a large number of random insertions.
    A very large tree built from a large number of random insertions and deletions.

Project code will be evaluated for the following

  1. Appropriate OO design and implementation.
  2. Appropriate use of recursion.
  3. Approrpiate decomposition of the main class into methods.
  4. Efficiency.

Files To Be Submitted

Submit any files which you have written or modified -- source code and build.xml

CVS Tools

Be sure to verify your projec submittal by using the cvs -n update command or the CVS utilities provided for that purpose. The repository location for this project is:
/afs/umbc.edu/users/n/i/nicholas/pub/cs341s13/Proj2