CSE 326: Data Structures
Assignment #4
April 29, 1999
Due: Monday, May 10

(Note that the some web browsers do not display mathematical equations correctly. If you have problems, you should consult the postscript version of this homework.)

Splay Trees

For this assignment you will be implementing a Dictionary class using splay trees, and experimenting with it.

Splay Tree Implementation

Implement the procedures Rotate, Splay, Lookup, Insert, Concat, Delete, FindMin and FindMax as described in the handout and lecture from scratch. With the exception of Splay, these procedures are very short and easy, so don't be concerned about the number of procedures you have to implement. The procedures Lookup, Insert and Delete should all be public members of your Dictionary class. You are free to modify the interface and implementation of the private members, as long as they accomplish their task by the same algorithms given in the handout.

For the experiments you will be performing, the data type for the Key field will be int and the Info field will be unused (but should be available). In this case, Lookup should simply return a boolean that is true if and only if the key was found.

Your implementation of Splay should be iterative (non-recursive) and should not use an explicit stack. It will be convenient to have each tree node contain an extra field which contains a pointer to its parent in the tree.

Experiments

Your main program should consist of an empirical evaluation of the performance of your Dictionary ADT.

Generate at least three different long sequences of insertion, deletion and lookup operations. Each sequence should consist of at least 500,000 operations, starting from an empty tree, and should result in trees with at least 100,000 nodes (at maximum size). For each sequence of operations, compute the total number of rotations your implementation performs to execute all the operations, and the ratio between this number and mlogn, where m is the number of operations in the sequence and n is the maximum size the tree ever gets over the course of executing the sequence.

Electronic turnin

Turn in an electronic copy of your source code, along with your Makefile. You program must be able to be run by executing make and then splay-trees. You can do this by running the turnin program on orcas as:

turnin -v -c cse326 Makefile *.cpp *.h
or a whole directory with:
turnin -v -c cse326 hw4/

Feel free to turn in a README file as well. It is very important that you turn in all of your files at once. If you forget some files the first time then turn everything in again. The turnin program only keeps your last turn in. Do not turn in object files .o or your compiled main programs.

Paper turnin

The paper turnin should contain the following:

  1. A hardcopy of all your source code.
  2. A description of the sequences generated for the empirical evaluation and a brief discussion of the results.
  3. A separate test program and output that demonstrates that every splay tree operation does what it is supposed to. It might be helpful to have a Print method that prints out everything in the tree.

Extra Credit

For extra credit, you can do the following:


File translated from TEX by TTH, version 1.95.
On 29 Apr 1999, 21:13.