HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why should leaf nodes in a red-black tree be black?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whynodesredleafshouldtreeblack

Problem

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



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

Solution

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.

Context

StackExchange Computer Science Q#23119, answer score: 3

Revisions (0)

No revisions yet.