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