CPSC 220 Fall 2005
HW 13, Part 2: 2-3 Trees Now That You Know What You're Doing

Read L&C 16.2 and do the following:
  1. L&C Exercise 16.1 (we did this in class)

  2. L&C Exercise 16.2

  3. Show the 2-3 tree you get from inserting the values 1-15 in low-hi order (1,15,2,14,3,13,etc).

  4. As we discussed in class, a 2-3 tree of height two has a minimum of 7 and a maximum of 26 elements. Give a set of values and an insertion order that will produce such a tree with 26 elements.

  5. In class we discussed the relationship between red/black trees and 2-3-4 trees. Draw a red/black tree corresponding to the (very ugly) 2-3-4 tree below. Is there more than one possibility? Explain.
                   (10  20  30)
                   /   /  \    \
                  /   /    \    \
               (3 8) 15  (21 23) (35 40 35)