Search code examples
algorithmred-black-tree

Which of these are valid Red-Black Trees?

Properties of Red-Black Tree:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

According to the properties, are these valid or invalid red black trees?

A. enter image description here

I think this is valid

B. enter image description here

I think this is valid, but I am not sure since there two adjacent red nodes?

C. enter image description here

I think this is valid, but I am not sure since there two adjacent red nodes?

D. enter image description here

I think this is not valid since it violate Property 4?

Did I understand these properties of a RBtree right? If not, where am I wrong?

Solution

  • You have listed the properties of Red-Black trees correctly. Of the four trees only C is not a valid red-black tree:

    A. enter image description here

    This is a valid tree. Wikipedia confirms:

    every perfect binary tree that consists only of black nodes is a red–black tree.

    B. enter image description here

    I think this is valid, but I am not sure since there two adjacent red nodes?

    It is valid. There is no problem with red nodes being siblings. They just should not be in a parent-child relationship.

    C. enter image description here

    I think this is valid, but I am not sure since there two adjacent red nodes?

    It is not valid. Not because of the adjacent red nodes, but because of property 5. The node with label 12 has paths to its leaves with varying number of black nodes. Same for the node 25.

    As a general rule, a red node can never have exactly one NIL-leaf as child. Its children should either both be NIL-leaves, or both be (black) internal nodes. This follows from the properties.

    D. enter image description here

    I think this is not valid since it violate Property 4?

    Property 4 is not violated: the children of the red nodes are NIL leaves (not visualised here), which are black. The fact that these red nodes have black NIL leaves as siblings is irrelevant: there are no rules that concern siblings. So this is valid.

    For an example that combines characteristics of tree C and D, see this valid tree depicted in the Wikipedia article, which also depicts the NIL leaves:

    enter image description here