Assigned | Wednesday, March 16, 2005 |
Due | 11:59 pm on Tuesday, April 5, 2005 |
Correction: March 20 |
An error on Figure 1 has been
corrected: 18 and 28 should be children of 25, not of 33. |
Correction: March 24 |
An error in the formula for
generating random integers have been corrected: module (%), rather than division (/) should be used.. I.e., r = rand()%(n+1). |
Correction and Clarification: March 30 |
1. An error in sample output is
corrected,see Corrected Sample output 2. To make the life easier, in RBST,you can call "find" function to determine if the item to be inserted is already in the tree. 3. Number of comparisons: you should compare the following regular BST: number of comparisons done during insert operations; RBST: number of comparisons done during insert operations, including those done in split operations. in both, determining if a (sub)tree is empty, i.e., comparing with NULL, should be counted as one comparison. |
Correction and Clarification: March 31 |
One student pointed out that the
comparison given above is unfair to BST because RBST does insertion
after find, so it only counts comparisons for those which are not yet in the tree but regular BST counts all comparisons regardless if an item is already in. For a fair comparison, YOU SHOULD EXCLUDE comparisons for duplicate items for BST. One way to do this is to do a find first and only do insert if find fails (the same way as for RBST insertion). The Sample output is modified accordingly |
To insert a key X into a BST T with n keys, we use the insertion at root algorithm (to be given below) with probability 1/(n+1), and with probability 1-1/(n+1) we insert the key recursively into the right or left subtree, according to the respective values of the key and the root.The main idea behind insertion at root is to use the split operation: This operation creates two new BST's L and R from a key x and a given BST T, which is destroyed by the operation: The first BST L contains the keys of T that are smaller than X, and the second BST R contains the keys of T that are larger than X. Then we insert x into a new node, whose left and right children are L and R, respectively. An example is given in Figure 1 below.
algorithm to split a treeExplanation of algorithm insert_at_root.
void split( int x, bst T, bst S, bst G) /* assuming x is not in T */
{
if T is null, make S and G null
else if x is less than T->key
set G = T /* all keys at the root and in right subtree are greater than x */
split T's left subtree into S and G's left subtree
/* some keys in T's left subtree are less than x, other may be greater than x */
else /* x is greater than T->key */
set S = T
split T's right subtree into S's right subtree and G
}
Note that you must check command line arguments to ensure that they are valid, e.g. that the command file can be opened, and print an appropriate message if an error is found.
An example command line looks like
Proj3 5
/afs/umbc.edu/users/y/p/ypeng/pub/cs341s05/test/Proj3/test
Submit
all files required to build an executable named Proj1 by running make.
Also submit 341-Spring04-proj1_questions.txt
- with your answers to the questions.
Submit
the files using the procedure given to you in the class.
If your makefile is set up correctly, you
should be
able to execute the command make
submit.
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 5 test
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.