5
$\begingroup$

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.

  1. Every node has a color either red or black.
  2. Root of tree is always black.
  3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
  4. 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? Invalid RB Tree

Thank you!

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ This rules apply also in construction phase, during nodes insertion? Could you give more context how it was constructed or what was the actual question? $\endgroup$ – Evil Aug 15 '16 at 20:24
  • $\begingroup$ @Evil The question was: There are 8 internal nodes, Label each of them with a color (red,black) so that it's a legal red-black tree. Those nodes were empty and I filled them, no other information was given about how the tree constructed. $\endgroup$ – Confused_CS_Student Aug 15 '16 at 20:26
  • 2
    $\begingroup$ The answer seems to follow immediately as soon as you look at the example & picture in Wikipedia: en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties. A tip: when you're confused, it's good to look at existing resources first before asking (e.g., check Wikipedia, common textbooks), and tell us in the question what investigation you did. $\endgroup$ – D.W.♦ Aug 15 '16 at 22:41
  • $\begingroup$ @D.W. Thanks exampled helped quite a lot! $\endgroup$ – Confused_CS_Student Aug 16 '16 at 0:01
  • $\begingroup$ Hint: Count the black nodes from root to leaves at each given path $\endgroup$ – Nick Zuber Aug 16 '16 at 21:40
4
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

There are 5 nodes with <2 children. In red-black trees, all nodes with <2 children must have the same black-depth, i.e. the number of black parents between it and the root, a black node with <2 children is a +1 in its own black depth. The node directly to the right of the root has black depth of 1 while every other node with <2 children has a black depth of 2.

| cite | improve this answer | | | | |
$\endgroup$

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.