CMSC 341 Fall 2005
Project 3

Assigned Wednesday, Thursday Oct 20, 2005
Due 11:59pm Thursday Nov 3, 2005
Updates

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 three new operations.

  1. NthElement(int n) -- returns the n-th element (starting from 1) of the in-order traversal of the BST.
  2. Rank( Object x ) -- returns the "rank" of object x. The rank of an object is its position (starting with 1) in an in-order traversal.
  3. 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.
These operations could easily be implemented by performing an in-order traversal inside the BST and perhaps placing the results in a vector. 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 recursively! Also think before you code. Be able to answer these questions before writing any code. Let X be the root of an augmented BST. Let R be the parameter to Nth( ).
  1. How can you express the rank of X in terms of the sizes of its subtrees?
  2. How can you express the rank of X's right child in terms of the rank of X?
  3. How can you express the rank of X's left child in terms of the rank of X?
  4. In which direction should you search if R is less the rank X? larger than the rank of X?

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. These elements will be inserted into the tree. 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, don't insert the duplicate.

Mr. Frey's public directory for this project is /afs/umbc.edu/users/d/e/dennis/CMSC341/Proj3

The Command File

Each line of the command file represents a single command. As usual, you may assume that valid commands are well-formed, but not all commands are valid. If you encounter an invalid command you should ignore the rest of 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.
  1. PRINT <number of levels>
    Prints the specified number of levels of the BST according to a     level-order traversal
  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.
  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, an appropriate error message should be produced.
A command file might look this RANK 33 RANK 12365 NTH 33 PRINT 4 REMOVE 67890 MEDIAN

Your Tasks

  1. Copy the author's binary search tree code (BinarySearchTree.C and BinarySearchTree.H) from Mr. Frey's directory to your directory.
  2. Augment the BinaryNode class by adding an integer to store the tree's size (including the root).
  3. Modify the author's BST code as necessary to maintain the tree's size.
  4. Write new BST methods to support the new operations.
  5. Write main( ) and helper functions.
  6. Copy the file 341-Fall05-p3_questions.txt from Mr. Frey's public directory which contains the questions for this project. Edit and submit the file before the project deadline.
  7. Create a makefile for this project.

Miscellaneous Project Requirements

These items cover those topics not addressed elsewhere in the project description. In particular, these are obviously not all of the project requirements.
  1. Although we are only using the BST for integers, the BST must remain a template.
  2. Your code must handle the attempted insertion of a duplicate value and the attempted removal of a non-existent value.
  3. Each command (and its arguments, if any) read from the file must be echoed as part of the output.
  4. No new friendships.
  5. No new data members (other than tree size) in the BinarySearchTree or the BinaryNode
  6. The name of your executable must be Proj3
  7. Your executable must be created by simply typing make
  8. The level order print (PRINT command) prints 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 (witout a blank line between them).
  9. Efficieny counts! Use the most efficient algorithm you can think of. 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.)

Level Order Travesal

A level order traversal uses a queue to store nodes to be printed. The pseudo-code is given below. You may use the author's queue code (Queue.C and Queue.H from Mr. Frey's public directory, but do not submit them), the STL queue, or write your own. instantiate a Q enqueue information about the root while the Q is not empty dequeue the next node's information print the information about the node enqueue information about the node's children (if any)

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. (55, 21, NULL) (40, 12, 55) (60, 8, 55) (30, 6, 40) (45, 5, 40) (70, 7, 60) (20, 3, 30) (35, 2, 30) (44, 2, 45) (47, 2, 45) (66, 3, 70) (80, 3, 70) (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)

Project Questions

Copy the file 341-Fall05-p3_questions.txt found in Mr. Frey's public directory for this project to your directory. Edit it to answer the questions. Be sure to submit this file.

Files To Be Submitted

Submit any files which you have written or modified -- source code and makefile.
DO NOT submit any unchanged code provided by the author (e.g. the author's Queue code). The grading scripts will remove Queue.C and Queue.H from your submittal directory.

Be sure to submit the answers to the project questions in plain text format.

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to execute the command make submit.

Submission Tools
There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example:  submitmake cs341 Proj3 <parameter list>

Submission Tools
There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example:  submitmake cs341 Proj3 <parameter list>

Submission Tools
There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example:  submitmake cs341 Proj3 <parameter list>

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the
executable in place.

submitrun <class> <project>

Example:  submitrun cs341 Proj3

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.