What is the at most height of a red-black tree with n internal nodes?
2021
What is the at most height of a red-black tree with n internal nodes?
Answer: C. 2 log₂ (n + 1) — A red-black tree is a self-balancing binary search tree where each node is colored red or black. It maintains balance through a set of rules that ensure the…
- A.
n
- B.
log₂ n
- C.
2 log₂ (n + 1)
- D.
log₂ (2n + 1)
Attempted by 6 students.
Show answer & explanation
Correct answer: C
A red-black tree is a self-balancing binary search tree where each node is colored red or black. It maintains balance through a set of rules that ensure the tree height remains logarithmic.
Key properties of red-black trees include:
Every node is either red or black.
The root is black.
All leaves (NIL nodes) are black.
If a node is red, both its children are black.
Every path from a node to its descendant leaves contains the same number of black nodes.
These properties ensure that the longest path from root to leaf is no more than twice the shortest path. As a result, the height of a red-black tree with n internal nodes is bounded by 2 log₂(n+1).
This bound is derived from the fact that the minimum number of internal nodes in a red-black tree of height h is 2^(h/2) - 1. Solving for h gives the maximum height as 2 log₂(n+1).