Minimal Size Maximal Size 3 15 2 14 1 13 12 11 10 9 8 7 6 5 4 3 2 1
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.
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.