# Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it?

Possible errors:

1. It first prove the case $$\text{height(x)=0},$$ then it says "For inductive steps, consider a node $$x$$ that has positive height".

From my understanding of inductive proof, the base case should be able to trigger the inductive statement. I mean: the "first domino" should trigger the next one, so the statement should be something like non-negative height.

2. It says "each child has a black-height of either $$\text{bh}(x)$$ or $$\text{bh}(x)-1$$", but when applying, only the latter is used: $$(2^{\text{bh}(x)-1}-1)+(2^{\text{bh}(x)-1}-1)+1=2^{\text{bh}(x)}-1$$.

## Paragraph from the book: ## 1 Answer

The proof seems correct to me.

1) The base case proves the claim when the height of the subtree rooted at $$x$$ is $$0$$. The inductive step proves the claim for every subtree rooted at $$x$$ of positive height $$h$$ assuming that the claim is true for all subtrees of heights from $$0$$ to $$h-1$$. So the inductive step for $$h=1$$ is able to prove the claim for all subtrees of height $$1$$ using the fact that the claim is true for the base case, i.e., for all subtrees of height $$0$$. This is a standard proof by structural induction.

2) Each subtree $$T_u$$ rooted in a child $$u$$ of $$x$$ has a black-height $$bh(u)$$ of either $$bh(x)$$ or $$bh(x)-1$$ but, in any case, the height of $$T_u$$ is smaller than the height of the subtree $$T_x$$ rooted in $$x$$. This means that the induction hypothesis can be applied, showing that the number of internal nodes is at least:

• $$2^{bh(x)}-1$$ if $$bh(u)=bh(x)$$; or
• $$2^{bh(x)-1}-1$$ if $$bh(u)=bh(x)-1$$.

In any case the number of internal nodes of $$T_u$$ is at least the smaller of the above two quantities, i.e., $$\min\{ 2^{bh(x)}-1, 2^{bh(x)-1}-1 \} = 2^{bh(x)-1}-1$$. This means that the number of internal nodes in $$T_x$$ is at least:

$$2 \cdot ( 2^{bh(x)-1}-1 ) + 1 = 2^{bh(x)}-1.$$