Red Black Tree

Uncle and grandparent nodes in a red black tree

  • Let Z be the node being studied.
  • Uncle nodes refer to the sibling nodes of the parent node of Z.
  • Grandparent node refer to the parent node of the parent node of Z.

Pictorial Representation of uncle,parent and grandparent nodes in a red black tree

Insertion Algorithm

Let Z be the node to be inserted.

  • Insert Node and color it red.
  • Recolor and rotate nodes to fix violations

There are 4 subcases to be handled to fix violations.

Case 1.Z is the root node.

  • Color the node as black.

Case 2.The uncle node of Z is red.

  • Recolor the parent and grandparent of Z to fix violations.

Case 3.The uncle node of Z is black and Z, parent node of Z and grandparent node of Z form a triangle.

  • Rotate parent of Z.

Case 4.The uncle node of Z is black and Z, parent node of Z and grandparent node of Z form a line.

  • Rotate the grandparent of Z and recolor the parent and grandparent of Z to fix violations.