CS 302 Programming Project. Implement the ADT Treap.
Due Friday April 8, 2016.

• There are new requirements that are in place for the remainder for this class for programming assignments:
  • You must properly document your code with comments, Here is an example file.
  • You must submit a 1 page document which will be a write up for your program. Here is a sample file, yours does not have to look exaclty like this, you just need to explain how the program works, what is the input/output, how it reads data (filestreams, redirection ,...), etc.
• Implement the search structure "Treap." Not circular linked list queue.
• Do not insert duplicates. No error message is necessary if insertion of a duplicate item is requested: simply do nothing.
• 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".
• Assume that the first character is an upper case letter, and that the other two are lower case letters. No case checking is required.
• Input will be read from a text file. (Not a keyboard).
• Keyboard can be used for commands, but not data input.
• 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.
  The height of a tree with one node is zero.
• Run appropriate tests for all your procedures.
• Email your source program to the TA, Mr. Bamjan, by midnight, Friday, April 8. Be sure to include the string "CS 302 hw6" 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.