SA-5

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 (use double lines to indicate red child)

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.)