CSE 326, Spring 1997: Homework 5
Due 5/7/95
Please explain your solutions when necessary.
 (10 points)
In this problem we consider 23 trees, or Btrees 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.
 (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.