Red-black tree - insertion case 5

Technical Discussion
1

Hi all,

When adding to a red black tree, in the 5th and last case: new node is red, parent is red, grandparent black and uncle black.

case5-rb-tree

This tree (red parent, black grandparent and black non nil uncle) is not red black. If new node an parent are on the left side, then the right side contians more black nodes in its path, before we add our new node.

Is this observation correct ? Do we still need to treat this case, simply because when rotatig/recoloring in the other situations for instert, this situation will arise ?

2

According definition of a Red-black tree (from Wikipedia):

  • Each node is either red or black.
  • The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
  • All leaves (NIL) are black.
  • If a node is red, then both its children are black.
  • Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.
2 Likes
3

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.