I'm reading the book Introduction to Algorithms. In the book, in the initial step of proving that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$, they prove that any subtree rooted at any node $x$ in a red-black tree has at least $2^{bh(x)} -1$ internal nodes. However I couldn't wrap my head around this proof.

They do an induction where this holds for the base case when $x$ is a leaf by $2^{bh(x)}-1 = 2^0 - 1 = 0$. However, when they do the induction, they say that a child of node $x$ has at least $2^{bh(x)-1}-1$ internal nodes (by the way isn't the correct way to put is to start with subtree rooted at a child of node $x$...?). This part confuses me a little bit, is it too trivial to say that it has $2^{bh(x)-1}-1$ nodes given that $bh(x)$ is the black-height (the number of black nodes on any simple path from a node not including itself), or is this related to the rules of the red-black tree which are:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
  • $\begingroup$ I think you only need to use property 5 (and the definition of black-height). $\endgroup$ – Yuval Filmus Nov 28 '20 at 19:21

It turns out trivial. I think I found the answer myself. First of all, $bh(x)$ gives us the black-height rooted from the node x. A subtree rooted from node x, in the worst case (in terms of the number of nodes it has) should not include any red nodes. Any node should be there in order to satisfy the $bh(x)$ number and nothing more. In that case we would boil down to a perfect subtree of the height $bh(x)$ and we now that a perfect binary tree has $2^{bh(x)}-1$ nodes. This is the least number of nodes it can have.

The subtlety in the question is that since we are considering the child of a node x that has $bh(x)$, it has at least $2^{bh(x)-1}-1$ nodes due to the possibility of losing 1 black-height by walking from x to its child.

PS: Even though what i wrote above seems sensible to me and maybe gives insight to the lemma even without the need of induction, after a little bit of careful reading, that claim is nothing but the just the induction hypothesis that holds for the leafs and propagates to the top of the three.


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.