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.
Minimal Size Maximal Size 3 15 2 14 1 13 12 11 10 9 8 7 6 5 4 3 2 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.
When performing a RotateLeft(T, x), assuming that y is the right child of x, the height of x needs to be decremented by one and the height of y needs to be incremented by one (this can be done in constant time). The heights of nodes in the subtrees of x and y do not change. However, the heights of the ancestors of x change, so the heights of all ancestors n of x need to be recomputed as max(height(LeftChild(n)), height(RightChild(n))) + 1, which will take O(lg n) time. A similar set of changes must be performed for a RotateRight(T, x) operation.

- 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)?
For a maximal tree, every node will contain 99 keys and will have 100 children. The total number of nodes is thus 1 + 100 + 10,000 = 10,101 and the total number of keys is 10,101 * 99 = 999,999.