| Assigned | Monday, March 8, 2004 | Due | 11:59 pm on Sunday, March 21, 2004 |
| Updates: 10 March 04 | A common implementation of a level-order traversal requires the use a queue. The author's implementation of an array-based queue is available for your use from Mr. Frey's directory A sample output is provided below |
| Updates: 12 March 04 | Due date for Project 3 has been extended to Sunday, March 28. |
| Updates: 16 March 04 | A sentence at the end of "Files To Be Submitted" section concerning Stack.C, string.C and bector.C is deleted. These are either not needed for this project or are part of standard library (cstdlib). |
| Updates: 17 March 04 | A error in the sample output is corrected. The tree heights were 1 greater than it should be. |
Objectives
The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code. You will also be asked to implement a technique that balances a BST with respect to the numbers of nodes in the left and right subtrees of each node. You will be modifying the author's BST code and implementing several new BST related methods.Description
An arbitrary BST is seldom balanced, the left and right subtrees of a node may have different heights or contain different numbers of nodes. In the class we have discussedseveral techniques for constructing height-balanced BST. In this project, you willexplore balancing BST based on the weights of its subtrees. Here we define the weight of a BST to be the number of nodes in that tree. A node in a BST is weight-balancedif the weights of its left and right subtrees differ by no more than 1.A weight-balanced BST is one in which every node is weight-balanced. An important property of weight-balanced BST is that the value at any node v is a median of the values at all nodes in the subtree rooted at v.The following straightforward but inefficient recursive procedure can be used to achieve weight-balance of a given BST T:
weightBalance(T)
- find the median of T;
- create a new BST T' with a single node, the root, whose value is the found median of T;
- retrieve and insert elements of all nodes of T, except the median, into T'; /* T' thus has a weight-balanced root */
- replace T by T';
- call this procedure to balance the left and right subtrees of T.
Here are some specifics concerning this assignment.
- 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.
- 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.
- 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.)
- Weight-balancing. For efficiency reason, you should use pre-order traversal when retrieve and insert values in step 3 of the weightBalance procedure
- 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- You may add any private data or methods which you feel are necessary.
- You may remove any of the author's code you feel is not needed for this project.
- Your BST must remain a class template, even though we are only building BSTs of integers for this project.
- 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 thequestions. Don't forget to submit the edited file; it is 10% of thisproject's grade.
Program Requirements
- 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.
- You are free to name your main program file, but your executable must be named Proj3
- Your code must handle (try/throw/catch) any exceptions thrown by the author's code or by your own classes.
- Your code must be able to handle trees of any size.
Sample Output
The following output is for format reference only.bash-2.03$./Proj3 1024 100 4Before 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: 5436Height of the tree: 12After 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: 5436Height of the tree: 6
Files To Be Submitted
Submit any files which you have written -- source code and makefile. Your files MUST be named as listed below.- 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
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 . 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
Your project will be tested using a variety of command lines, some of which will be invalid.Your project will also be tested using a variety of command files which will test various conditions which your code should handle.
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 duedate will not be accepted. Do not submit any files after that time.
