CSE 326, Spring 1997: Homework 5

Due 5/7/95

Please explain your solutions when necessary.
  1. (10 points) In this problem we consider 2-3 trees, or B-trees of order 3.
  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.