Suppose that you are inserting a new key into a 2-3 tree. Under which one of the following scenarios must the height of the 2-3 tree increase by one?
When the number of keys equals one less than a power of two
When the number of nodes equals one less than a power of two
When the final node on the search path from the root is a 3-node
When every node on the search path from the root is a 3-node
Suppose that you left rotate the node containing E in the BST below. What is the level-order traversal of the resulting red-black BST?
R E X C M S Y A H P
R M X E H S Y C F P
R M X E P S Y C H A
R C X A E S Y M H P
Suppose that you insert N keys in ascending order into a red-black BST. What is the height of the resulting tree?
How many probes does a search in a B-tree of order M with N keys require in the worst case?