CSE 326, Spring 1995: Homework 6

Due 5/10/95

1. (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.
2. (10 points) A right zig-zag consists of a left single rotation followed by a right single rotation and a right zig-zig consists of a right single rotation followed by another. In splay trees zig-zag and zig-zig operations are done very often so it makes sense to hand optimize the code.
   • Design a right zig-zag and zig-zig algorithms which minimize the number of pointer assignments. Assume you start with a pointer to the top node in the structure to be zig-zaged or zig-ziged.
   • compare the number of operations in your algorithm to algorithms which do two single rotations.