1
$\begingroup$

I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them.

One of the properties of the Red-Black tree is that every red vertex must have two black children, meaning one cannot have two consecutive red vertices.

Can someone explain to me why this is an essential property? What are the benefits of having such a property?

$\endgroup$
  • 1
    $\begingroup$ What research have you done? We expect you to do a significant amount of research/self-study before asking. If the answer is explained in Wikipedia at the obvious place (or in standard textbooks), you probably haven't done enough research before asking. In this case, the Wikipedia article on red-black trees already has the answer: "These constraints enforce a critical property of red–black trees: [...]. The result is that the tree is roughly height-balanced [...] allows red–black trees to be efficient in the worst case". $\endgroup$ – D.W. Feb 21 '15 at 23:46
  • $\begingroup$ Check the main theorems and proofs about red-black trees -- the answer lies there. $\endgroup$ – Raphael Feb 22 '15 at 10:42
2
$\begingroup$

If you check the proof height-balancedness of red-black trees, you'll see that we essentially analyse the black-height $h_b$ of the tree which, by another important invariant, is the number of black nodes from the root to any leaf.

The property you cite then gives us the right half of

$\qquad\displaystyle h_b(T) \leq h(T) \leq 2h_b(T)$,

which allows us to carry over bounds on black-height to usual height.

$\endgroup$
1
$\begingroup$

The properties of a red black tree allow insertion, deletion and search in $O(log(n))$. I guess you can find a prove online somewhere.

When an element is inserted or deleted. A fix-up is done, it involves rotations in a tree, so the properties still hold. This ensures the tree is quitebalanced at all times and search is quite fast at all times.

$\endgroup$
  • $\begingroup$ This says essentially, "The property is needed to make stuff work. Look somewhere else to find out how." That's hardly an answer at all. $\endgroup$ – David Richerby Feb 21 '15 at 22:44
  • $\begingroup$ You're right. I intend to give a full explanation when time allows me to and no one else did by then. Maybe this vague explanation tickles OPs mind to look further into the matter, for now. $\endgroup$ – Auberon Feb 21 '15 at 22:51

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.