CS 302 Programming Project.
Due Thursday April 12, 2007.
If you turn the assignment in by midnight, Tuesday April 10, 2007, you will get extra credit.

• 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, Tuesday, April 10, for extra credit, or by midnight, Thursday, April 12, for normal credit. Be sure to include the string "CS 302 hw8" 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.