2
$\begingroup$

"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.

$\endgroup$

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.