# 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? 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? Feb 11 '17 at 15:05
• Can you give bounds on their length in function of the black-height? Feb 11 '17 at 15:08
• Aren't they both lower bounded by the black-height respect to the root? Feb 11 '17 at 15:09
• Yes, they are. Can you also find an upper bound on the longest one? Feb 11 '17 at 15:10

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.

• It's never too late. Oct 27 '21 at 8:53
• I think you want to clarify a bit on the maximum height and why that's combination is the one that attains the maximum (and eventually why it's the unique one), for given $n$ nodes in the tree. Oct 27 '21 at 12:07
• Hi @user8469759, I updated my answer. I am just a student so I don't know if I might be wrong, I hope not :-) Oct 30 '21 at 18:50
• it's good to discuss. I think the answer is ok overall. I think you wrote twice the same inequality, not sure this was meant. Oct 31 '21 at 15:50
• Yes I wrote it twice to show that from the minimum to the highest height, $bh(x) \geq h(x)/2$ always Nov 1 '21 at 12:55

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 :)

• 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". 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. Mar 26 '18 at 12:28