Red-Black tree height from CLRS

Question

The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is

$$h(n) \leq 2\log_2(n+1)$$

There's a subtle step I don't understand. The property 4 reported at the beginning of the chapter states:

If a node is red, then both its children are black.

And because of such property it is later stated

According to property 4, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least $h/2$.

I can intuitively agree, but as exercises I'd like to prove it, but I can't manage how to actually do it. Why is that property true? I'm not actually neither able to set up the problem, the only think I could think of was that I if I have $r + b = h$ nodes, where $r$ is the number of red nodes and $b$ is the number of black nodes I can have a total of

$$ k = \frac{h!}{r!b!} $$

And I'd like to prove from here that if $b < r$ than I have the contradiction, but I need something more that this probably. Any help?

Answer 1

I'd prove it this way (sorry for being too late, hope it'll be useful for other people).

Let $bh(x)$ be a fixed black height.

The minum height we can have is when we have only black nodes, hence $$bh(x) = h(x)$$ so $$bh(x) \ge \frac{h(x)}{2}$$ holds.

The maximum height we can have is when we alternate a black and a red node. In other words, for each black node there is a red node (at maximum), so we'll have: $$ 2\times bh(x) = h(x) $$ hence $$bh(x) \ge \frac{h(x)}{2}$$ holds.

$\square$

Update requested:

The maximum height of a tree rooted in the node $x$ is reached when we alternate a black and a red node because one of the properties of a RB tree states "A red node does not have a red child." So if we add a red node we shall violate this property, if we add a black node we shall increase the black height.

Answer 2

step 1 : At first let me say that , property 4 which states that children of a red node , should be black , comes from the definition of red-black tree , because 2 (or more) red nodes can't come after each other .
step 2 : For the statement that is a result of property 4 : let's consider a path from root to a leaf , which consists of 2K nodes, and the number of Red ones, is more than the number of black ones, so at least number of red nodes must be K+1 and therefore number of black nodes is K-1. From property 4 we shouldn't put 2 (or more ) red nodes consecutively , so between every 2 red nodes , we should put a black one and since we have (at least) K+1 red node and (at most) K-1 black nodes , after we put the Kth red node , we will run out of black nodes and we have to put the (K+1)th red node right after the Kth red node , so we get two red nodes placed consecutively (you can prove it by induction )and this is in contradiction with Red-Black tree definition. so "at least half the nodes on any simple path from the root to a leaf, not including the root, must be black"
step 3 : For the Height of the tree :
we know that the height of a tree , is the number of edges in the longest path from root to a leaf and from what we proved in step 2 , at least half of the nodes on this path can be black , so if we have the height of h , at least we have h/2 black nodes , which comes to say that the black-height is at least h/2 .
step 4 :
And for your solution , I guess you are being too general , in my idea you'd better consider number of red and black nodes , in an arbitrary path from root to a leaf rather than in the whole tree .
Hope it works as an idea not the whole solution :)