Consider a B-tree of height h and minimum degree t ≥ 2 containing n keys, n ≥ 1. Which is correct?

1. Ah ≥ log_t((n + 1)/2)
2. Bh ≤ log_t((n + 1)/2)
3. Ch ≥ log_t((n − 1)/2)
4. Dh ≤ log_t((n − 1)/2)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. h ≤ log_t((n + 1)/2)

Explanation

Every node except the root has at least t − 1 keys and t children, so n ≥ 2tʰ − 1, giving h ≤ log_t((n + 1)/2) (CLRS Theorem 18.1).