3
$\begingroup$

From the property of Red-Black Trees we know that:

  • All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms")

An example of a red–black tree. From Wikipedia

But what is the reason that we should enforce them as Black, even though they're NILL's?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ One of the other properties is that red nodes have two black children. $\endgroup$
    – Louis
    Mar 27, 2014 at 11:00

2 Answers 2

Reset to default
3
$\begingroup$

Take a uncolored leaf node, now you can color it as either red or black. If you colored it as red then you may have chance that your immediate ancestor is also red which is contradicting(according to basic principle). If you color it as black then no problem even though the immediate ancestor is red. And also no change in the number of black nodes from root to leaf paths(i.e every path get +1). This may be the possible reason behind that.

Improve this answer
$\endgroup$
3
$\begingroup$

It's simply a part of the definition of a red-black tree. It is also necessary to maintain one of the other rules associated with red-black trees: If a node is red, then both its children are black.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.