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.
  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.