COMP 410 (F'09). HW 5 (Prog assignment)

Handed out on Sept 30; Due back on Oct 21 in class

The operations that are to be supported are

• insert
• remove
• contains
• findMin
• findMax

1. Implement remove using the technique of lazy deletion. (Note that this will require you to modify the node structure used in the implementation provided in the text; you need an additional field indicating whether the data stored in a node has been deleted or not.)
2. Much of the code for insert is provided in the text (Figs 4.37-4.39, 4.41, and 4.43). You may use this code, addingk and modifying as needed. (You will need to add code to implement the remaining 2 forms of rotation, and modify the existing code to (i) account for the changes in the node structure, and (ii) exploit the fact that lazy deletion may have left unused nodes in the tree.
3. In implementing findMin and findMax, be sure to account for the possibility that the leftmost (respectively, rightmost) node in the tree may have been marked by lazy delete.

• You are not permitted to work in groups: other than the instructor and the TA, no-one may help you.
• Include a complete listing of all your code, input files, and output files.
• Your code must be appropriately commented -- if we don't understand your code with reasonable effort, you get no credit for it.
• Include a test plan detailing how you tested your program, and why you believe it is correct.
• Include a neatly typed (not handwritten) explanation of your proposed solution, and general comments on the structure and layout of your submission.

All of the above should be placed i an envelope with your name on the outside, and submitted at the beginning of the class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class. Late submissions will not be accepted without documented reasons.