0
$\begingroup$

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:

error

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.