Can a red node have just 1 black child in a red-black tree?

2
votes

The rules for a 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.

Rule 4 mentions that red nodes need both black childs but what if there is just one child to begin with? Is there an argument to prove or disprove this?

1
data-structuresbinary-treebinary-search-treeproofred-black-tree
Possible duplicate of Red Black Tree ~ 1 Child Deletes – templatetypedef
This isn't possible, it would break rule (5). See this older question for details. – templatetypedef

1 Answers

1
votes

No,a red node cannot have one child,consider the following cases:- 1.If the single child it has is red...this cannot happen because no two consecutive nodes can be red. 2.If the child is black...again this cannot happen because this would violate the 'Black Height Rule'...this case would give one extra black node in a path which is not correct according to the rule.