"Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that

A red-black tree with $n$ internal nodes has height at most $2\log(n+1)$,

i.e. $h \le 2\log(n+1)$.

Can equality part of the above, $h = 2\log(n+1)$, ever be satisfied? If not, what is the best known upper bound?

My attempts to assert that are telling me that cannot be the case.

Let's denote black height of a node $x$ as $bh(x)$.

Assume a red-black tree of $n$ internal nodes and height $h = 2\log(n+1)$. Let's consider $h_\min$, the shortest path to a leaf node. We know that

$$ h_\min \ge bh(root)$$

since path to $h_\min$ can be can either all black or have some additional red nodes; and

$$ bh(root) \ge \dfrac{h}{2} = \log(n+1) $$

since $\dfrac{1}{2}$ is the smallest fraction of black nodes in the longest path (height).

  1. In the proof of Lemma 13.1 we have that the number of internal nodes of a red-black tree is at least $ 2^{bh(root)}-1 $, so the size $n$ of our tree is $$ n \ge 2^{bh(root)}-1 \ge 2^{\log(n+1)} - 1 = n + 1 - 1 = n$$ I'm surprised that that lower bound on number of internal nodes actually gives the exact result. But maybe it's just my intuition that is wrong.

  2. The tree up to depth $h_\min$ is a full binary tree (that includes black leaf nil nodes). We want to count only internal nodes, so let's count the number of nodes $m$ at depth one smaller i.e. $h_{min} - 1$ $$ m = 2^{(h_\min - 1) + 1} - 1 = 2^{h_{min}} - 1 \ge 2^{\log(n+1)}-1 = n+1-1 = n $$ We also know that height of the whole tree is $$h=2\log(n+1)$$ which is twice what we've considered, so there must be some internal nodes at depths larger then $h_\min - 1$, i.e. $ n > m $ but that leads to a contradiction $$ m = n \land n > m \implies m > m $$ So that suggests that the original assumption, $h = 2\log(n+1)$, cannot be true.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.