CSE 326, Spring 1997: Homework 5

Due 5/7/95

1. (10 points) In this problem we consider 2-3 trees, or B-trees of order 3.
   • Show the result of inserting 3,1,4,5,9,2,6,8,7,0, in that order, into an initially empty tree. Show the result after each insertion.
   • Show the result of deleting 0 and then 9.
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.