SA-9, due May 26

Exercises

[based on a problem from Goodrich & Tamassia] Consider the sequence of keys

5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1

Draw the result of inserting entires with these keys (in the given order) into

  1. an initially empty 2-3-4 tree
  2. an initially empty red-black tree

You need not show all the steps along the way (though you might find it helpful for "debugging" if you do).

Submission Instructions

Turn in your written/drawn answers. (Feel free to draw on paper and submit a picture of sufficient quality.)