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

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)