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.