CMSC 341 Spring 2004
Project 3
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 discussed
several techniques for constructing height-balanced BST. In this project, you will
explore 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-balanced
if 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.
In this project you are asked to write a program that first constructs a BST
T by successively inserting a given number of randomly generated
non-negative integers into an initially empty tree; then weight-balance T
according to the procedure outlined above.
Your program should also prints both the original T and its
weight-balanced version, using a level-order traversal, to a given level.
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 the
questions. Don't forget to submit the edited file; it is 10% of this
project'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.
The following output is for format reference only.
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
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 due
date will not be accepted. Do not submit any files after that time.