   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.   