3
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – user8469759 Mar 26 '18 at 12:22
  • $\begingroup$ 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. $\endgroup$ – user8469759 Mar 26 '18 at 12:28

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.