COS 226 PROBLEM SET 4

2. Draw the binary search tree that results when you insert the keys G R A D E I N F L A T I O N in that order into an initially empty tree, using the root insertion method.

3. Draw the 2-3-4 tree that results when you insert the keys G R A D E I N F L A T I O N in that order into an initially empty tree.

4. Draw the red-black tree that results when you insert the keys G R A D E I N F L A T I O N in that order into an initially empty tree.

5. Draw the splay tree that results when you insert the keys G R A D E I N F L A T I O N in that order into an initially empty tree.

Due: in precept on March 2 or 3.

Do your work on this page (use the back if you must)