CSE 5311 Fall 1999

**Quiz #4**

- 1.
- (6 points).
Draw two B Trees with degree t=2. The first tree should contain the
minimum possible number of keys for a tree of height 1, and the second tree
should contain the maximum possible number of keys for a tree of height 1.

- 2.
- (8 points).
Consider an augmented red-black tree that maintains, in each node of
the tree, the height of that node. Describe how to update this height
information efficiently when a rotation occurs.

- 3.
- (6 points). What are the maximum number of keys that can be stored in a B tree of degree t=50 and height=2 (the root plus two additional levels)?