CS 302 Programming Project.
Due Thursday November 6, 2008.
-
Implement the search structure "Treap."
-
Write all your own code.
Do not use "off the shelf" code from any source.
However, you may look at available code to get ideas.
Be sure not to just copy it, however.
-
The items stored will be character strings of length 3, e.g., "Bob".
Input will be read from a text file or the keyboard.
-
Your program will read the file and insert items in the order they are
read. No duplicate item will be inserted.
-
Your program will be able to execute the usual operators for search
structures.
Lazy deletion is not allowed.
-
Write procedures which count the number of nodes in the tree,
compute the height of the tree, and output the items in sorted order.
-
Run appropriate tests for all your procedures.
-
Email your source program to the TA by midnight, Thursday, November 6.
Be sure to include the string "CS 302 hw4" in the subject field of
your submission.
-
I don't want anyone's program to resemble anyone else's program. Try to
be unique.
-
Test File 1.
Deletion File 1.
Second Insertion File 1. (To test for re-insertion of
an item that has been deleted)
Sample run using Test File 1, Deletion File 1,
and Second Insertion File 1. Your run will probably give different
answers about the height of the tree than this file, so don't be alarmed
about that issue.
Test file 2.
Test file 3.
Test file 4. (This is a "worst case" file.)
-
Subprograms I used.
(But, you don't have to do it the same way I did.)
Output of my program..
In order to see the binary tree structure in this file,
tilt your head 90 degrees to the left. For example, in the first tree,
Jan is the root, its left child is Bob, and its right child is Ron.
The right column gives the priority of each item. The number of spaces
before an item is the depth of that item in the treap.
Another run with the same input data.
Because priorities are assigned at random at execution time, the runs give
different output.
I will go over "treapDelete" in more detail in class.
