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

Why is this not a valid Red-Black tree?

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

Problem

I'm having some difficulty understanding the rules for valid red-black tree.
If my understanding is correct there are 4 rules that a tree has to follow to be a red-black tree.

  • Every node has a color either red or black.



  • Root of tree is always black.



  • There are no two adjacent red nodes (A red node cannot have a red parent or red child).



  • Every path from root to a NULL node has same number of black nodes.



So I drew the tree below in a quiz, and apparently it's not valid. Could someone tell me why this tree is invalid?

Thank you!

Solution

If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty leaf hitting 2 black nodes. This is not allowed in a Red Black Tree because by definition a path from root to an empty leaf should contain the same amount of black nodes as every other path from root to an empty leaf.

The other important thing to know is that NULL nodes (leaves) aren't drawn; only the internal nodes are drawn. By convention, all leaves (NULL nodes) automatically are considered to be colored black.

Context

StackExchange Computer Science Q#62626, answer score: 5

Revisions (0)

No revisions yet.