CSE 326, Spring 1995: Homework 6
Due 5/10/95
 (10 points)
Consider the following alternatives to the ordinary splay tree operations
described in class. The operations are insert, delete, and find.

Instead of the complicated deletion operation which involves two splaying
operation, simply do a normal binary search tree delete. Give an
example where this form of deletion will result in O(n^2) time to do
n operations.

Suppose, instead of splaying on every find, we splay on every other find.
This seems
to have the potential of improving performance by removing lots of rotations.
Give an example where this
form of find will result in O(n^2) time to do n operations.
 (10 points)
A right zigzag consists of a left single rotation followed by
a right single rotation and a right zigzig consists of a right single rotation
followed by another.
In splay trees zigzag and zigzig operations
are done very often so it makes sense to hand optimize the code.

Design a right zigzag and zigzig algorithms which minimize the number of
pointer assignments. Assume you start with a pointer to the top node
in the structure to be zigzaged or zigziged.

compare the number of operations in your algorithm to algorithms which
do two single rotations.