# Red-Black tree height from CLRS

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?

• By definition of Red-Black Tree, along two root-leaf simple paths there will be the same number of blacks. Furthermore, there can never be two reds in a row along any path. What is the longest and what is the shortest possible path? – quicksort Feb 11 '17 at 15:01
• I'm not sure I know how to answer to that. I would just say that is the the shortest path root-leaf is the one with minimum height , and longest one is the one with maximum height. But both of them have the same number of black nodes. Is this the answer you were expecting me to give? – user8469759 Feb 11 '17 at 15:05
• Can you give bounds on their length in function of the black-height? – quicksort Feb 11 '17 at 15:08
• Aren't they both lower bounded by the black-height respect to the root? – user8469759 Feb 11 '17 at 15:09
• Yes, they are. Can you also find an upper bound on the longest one? – quicksort Feb 11 '17 at 15:10

• Hi, sorry for the late reply. I don't think I was being too general, I was trying to be formal. Say I my back height is $b$, with numbers of red node $r$ than we must have $r + b \leq 2b$, which is clear but I was I trying to prove rigorously that if $r + b > 2b + 1$ than I have a contradiction, I guess I can actually prove that by induction now that I think about it, but back then I was more thinking of "let's enumerate everything and let's find out where I have a contradiction". – user8469759 Mar 26 '18 at 12:22
• indeed if $b = 1$, namely only the root the next node can be both red or black, It can be black because the black height is bounded, it must be red or it doesn't have any child, therefore $r + b = r + 1 \leq 2$. If we assume this hold for a certain height $b$ then we have $r + b \leq 2b$, let's consider a RB tree of black height $b+1$. In this case I would enumerate all possible cases of the two subtrees. – user8469759 Mar 26 '18 at 12:28