Red-Black Tree Insertion Repair Operations

Used when there is a red property violation in a Red-Black Tree (in other words, when a red node has a red child).

Case 1: Null or Black Aunt

1. See if red child, red parent, and grandparent are in a straight line:

   • If not (e.g., the node after stepping left twice or stepping right twice from the grandparent node isn't the red child), perform a left or right rotation to fix this

2. Rotate and color swap:

   • Rotate the red parent and the grandparent
   • Swap the colors of the old parent and grandparent (now the parent and sibling of the red child node)

Case 2: Red Aunt

1. Recolor:

   • Change the red parent's color to black
   • Change the red aunt's color to black
   • Change the grandparent's color to red

2. Check color of grandparent's parent:

   • If the grandparent's parent is red, recursively repair the red property violation
   • If the grandparent is the root node, change its color to black

More information on Red-Black Trees can be found here.