Algorithm : Red-Black Trees

Invariants

1. Every node is either red or black.
2. The root node is black.
3. Both children of a red node are black. (assume null children are black)
4. For each node, all paths to descendant leaves contain the same number of black nodes.

Insertion

• Perform a binary-search-tree insertion to add the node. Call the node X.
• Color node X red.
• Cases:
  1. X is the root node?
     • Color X black.
  2. Parent is red, pibling is red?
     1. Color parent and pibling black.
     2. Color grandparent red.
     3. X now refers to the grandparent, and repeat the Cases section.
  3. Parent is red, pibling is black?
     1. X is left-child and parent is right-child? (zig-zag)
        1. Color grandparent red.
        2. Color X black.
        3. Rotate right on parent.
        4. Rotate left on grandparent.
     2. X is right-child and parent is left-child? (zag-zig)
        1. Color grandparent red.
        2. Color X black.
        3. Rotate left on parent.
        4. Rotate right on grandparent.
     3. X and parent are both left children? (zig-zig)
        1. Color grandparent red.
        2. Color parent black.
        3. Rotate right on grandparent.
     4. X and parent are both right children? (zag-zag)
        1. Color grandparent red.
        2. Color parent black.
        3. Rotate left on grandparent.

Adapted from Chapter 13 of Introduction to Algorithms, 2nd Edition by Cormen, Leiserson, Rivest, and Stein, and notes of unknown provenance.