Red-black trees are one of many search tree schemes that are “balanced” in…
2017
Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic-set operations take ________ time in the worst case.
- A.
O(1)
- B.
O(lg n)
- C.
O(n)
- D.
O(n lg n)
Attempted by 220 students.
Show answer & explanation
Correct answer: B
Answer: O(lg n)
Explanation: Basic dynamic-set operations (search, insert, delete) take time proportional to the height of the tree. The red-black tree invariants guarantee that the height grows logarithmically with the number of nodes, so each operation is O(log n) in the worst case.
Key properties: every path from the root to a leaf has the same number of black nodes (call this black-height bh), and no path has two consecutive red nodes.
Node count bound: a subtree with black-height bh has at least 2^{bh} - 1 internal nodes, so n ≥ 2^{bh} - 1 which implies bh ≤ log2(n+1).
Height bound: because red nodes cannot be consecutive, any root-to-leaf path has at most twice the number of nodes as its black-height, so height h ≤ 2·bh ≤ 2·log2(n+1) = O(log n).
Conclusion: following a root-to-leaf path takes O(log n) time, and insert/delete fixups use only O(1) work per rotation with at most O(log n) rotations, so overall each basic dynamic-set operation is O(log n) in the worst case.