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:
- Every node is either red or black.
- The root is black.
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.