CMSC 341 Spring 2004
Project 3

Objectives

Description

1. find the median of T;
2. create a new BST T' with a single node, the root, whose value is the found median of T;
3. retrieve and insert elements of all nodes of T, except the median, into T';     /* T' thus has a weight-balanced root */
4. replace T by T';
5. call this procedure to balance the left and right subtrees of T.

1. Command Line. Your program will accept three command line arguments:
   • S: the seed for the system's random number generator;
   • N: the total number of distinct integers to be inserted into the tree (e.g., its weight); and
   • L: the level up to which the two trees are to be printed.
2. Random numbers. The random numbers shall be generated in the same way as in Project 2, except that they must be integers between 0 and 9999, inclusive. To guarantee the tree to have the given weight N, you need to properly handle duplicate integers that may be generated by the system's random number generator. For this purpose you need to modify the insert method in author's code since it does nothing when attempting to insert a duplicate element. Instead, your modified insert method should return "failure" when attempting to insert an element which is already in the tree.
3. Median. There are two medians when N is even. In this project you should always use the smaller of the two. (An outline of algorithm findMedian is given in the Hints section below.)
4. Weight-balancing. For efficiency reason, you should use pre-order traversal when retrieve and insert values in step 3 of the weightBalance procedure
5. Print tree. You should print the tree in level-order, up to the level L. If the tree's height is less than L, then print the entire tree. After printing a tree, also print its height and its median.
         Tree nodes must be printed as ordered triples of values in the format ( x, y, z ), where x is the value found in the node's parent, y is the value found in the node being printed (print the value of ITEM_NOT_FOUND for the value of the root's "parent"), and z is the weight of the tree rooted at that node.  Your level-order tree print must start with a new line with each level, and print 4 nodes per line if there are more than 4 nodes at a given level.
         The format for printing trees is shown in the sample output below.

Your Tasks

• Read and understand the author's code for his BST implementation.
• Write a makefile for this project. As in projects 1 and 2, any unmodified code supplied by the author should be referenced within the makefile.
• Write a program that contains main( ) as the driver of your project.
• Copy the author's BST code to your local directory from Mr. Frey's directory
              /afs/umbc.edu/users/d/e/dennis/pub/CMSC341.
  Then modify the author's code as necessary
  

  1. You may add any private data or methods which you feel are necessary.
  2. You may remove any of the author's code you feel is not needed for this project.
  3. Your BST must remain a class template, even though we are only building BSTs of integers for this project.
  4. You may add public methods for the following operations. The signatures of these methods are left to your discretion. Be sure to follow good OO design principles.
     
     • find and return the median of a given BST.
     • find and return the height of a given BST.
     • weight-balancing a given BST.
• Answer the questions posed in 341-Springl04-proj3_questions.txt. Copy the file
  /afs/umbc.edu/users/y/p/ypeng/pub/CMSC341/Proj3/341-Spring04-p3_questions.txt
  to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it is 10% of this project's grade.

Program Requirements

1. Your code must follow all project guidelines established for this course. See the project organization and project policies web pages.  You are not required to modify the author's code to follow these guidelines.
2. You are free to name your main program file, but your executable must be named Proj3
3. Your code must handle (try/throw/catch) any exceptions thrown by the author's code or by your own classes.
4. Your code must be able to handle trees of any size.

Sample Output

bash-2.03$./Proj3 1024 100 4
Before balancing the level order output is: 

Level 0:
	(-1,5283,100)
Level 1:
	(5283,2086,46)	(5283,8027,53)
Level 2: 
	(2086,1067,17)	(2086,4646,28)	(8027,7673,28)	(8027,9552,24)
Level 3:
	(1067,400,7)	(1067,1287,9)	(4646,2150,19)	(4646,5226,8)
	(7673,5436,24)	(7673,7999,3)	(9552,9182,18)	(9552,9925,5)
Level 4:
	(400,1,2)	(400,666,4)	(1287,1197,1)	(1287,1803,7)
	(2150,2217,18)	(5226,4916,5)	(5226,5237,2)	(5436,5352,2)
	(5436,7565,21)	(7999,7829,2)	(9182,8727,15)	(9182,9336,2)
	(9925,9699,4)

Median: 5436
Height of the tree: 12

After balancing the level order output is: 

Level 0:
	(-1,5436,100)

Level 1:
	(5436,2794,49)	(5436,7999,50)
Level 2:
	(2794,1323,24)	(2794,4286,24)	(7999,6674,24)	(7999,8862,25)
Level 3:
	(1323,776,11)	(1323,2086,12)	(4286,3436,11)	(4286,5126,12)
	(6674,6049,11)	(6674,7118,12)	(8862,8420,12)	(8862,9518,12)
Level 4:
	(776,400,5)	(776,1197,5)	(2086,1743,5)	(2086,2465,6)
	(3436,2960,5)	(3436,3968,5)	(5126,4891,5)	(5126,5242,6)
	(6049,5692,5)	(6049,6235,5)	(7118,6883,5)	(7118,7568,6)
	(8420,8126,5)	(8420,8563,6)	(9518,9072,5)	(9518,9624,6)

Median: 5436
Height of the tree: 6

Files To Be Submitted

• Program file that contains your main( );
• Your makefile -- which must be named makefile or Makefile;
• Your modified versions of the author's BST code.

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.

Hints

• Test your code with small trees first, using non-random data.
• Some methods are better implemented as recursive functions, others as iterative functions. Choose your implementation carefully.
• Calculating the height of the tree is easier by considering the height of an empty tree to be -1.
• Since weights of all subtrees are included in the level-order tree print, it is more efficient to store the weight with each node than to calculate it by calling a method when needed. If you choose to store the weight at each node, weights of all nodes visited by your insert method should be incremented by 1 if the insert operation succeeds (i.e., an distinct integer is inserted).
• It is easier to implement method findMedian by an iterative procedure, similar to findMin and findMax in the author's code. The difference is that the other two methods move through the tree always along one direction (left for findMin and right for findMax) but findMedian travels the tree along a zigzag path. There are a number of ways to implement this method, one of which is an outlined below. Here the "position" of a node refers to where that node stands if all nodes are put in the ascending order of their values (e.g., the node with the smallest value has position 1, and the second smallest position 2, etc.). The position of a node can also be thought as the nuumber of nodes in the tree with values less than or equal to the value found at that node. In particular, the node that contains the median of the tree (or the smaller of the two medians when there are even number of nodes in a tree) has position (weight+1)/2.
  

      m = (t->weight+1)/2;      /* position of median, t points to the root of the tree */
      pos = t->left->weight + 1;
                                /* position of the root */
      n = t;                    /* n is the node currently been visiting */
      while (!pos == m){
         if (pos > m)          /* median is in the left subtree of n */
            {n = n->left;  
             pos = pos - n->right->weight - 1;}     /* pos moves down */
         else 
            {n = n->right;     /* median is in the right subtree of n */
             pos = pos + n->left->weight + 1;};     /* pos moves up */
      }

Submit Tools

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

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> [command-line args]

Example:  submitrun cs341 Proj3 12345 20 4

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

Grading and Academic Integrity

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.