CPSC 220 Fall 2005
HW 13: 2-3 Trees

Read L&C 16.2 and do the following:
  1. L&C Exercise 16.1

  2. L&C Exercise 16.2

  3. Show the 2-3 tree you get from inserting the values 1-15 in order into a 2-3 tree.

  4. A 2-3 tree of height h can hold a variable number of elements.
    1. What is the minimum number of elements that can be stored in a 2-3 tree of height two (that is, with three levels)? Explain your answer.
    2. Give a set of values and an insertion order that will produce a tree as in (a).
    3. What is the maximum number of elements that can be stored in a 2-3 tree of height two (that is, with three levels)? Explain your answer.
    4. Give a set of values and an insertion order that will produce a tree as in (c).