RB_fixup.py

# in this happy fairy land of pseudo code:
# all non-existent nodes don't throw seg faults and instead have color BLACK!

def fixup(red_node):
  while red_node.parent.color == RED:
    parent = red_node.parent
    grandpa = red_node.parent.parent
    if parent == grandpa.left:
      uncle = grandparent.right
      if uncle.color == RED:
        #case 1,  a 2-3-4 split
        parent.color = BLACK
        uncle.color = BLACK
        grandpa.color = RED
        red_node = grandpa
      else:
        #uncle is black so this is case 2/3 where red_node wants to join a partial parent "2-3-4 node"
        if red_node == parent.right:
          #case 2
          red_node = parent
          red_node.rotate_left()
        #case 3 was created in trying to fix case 2
        red_node.parent.color = BLACK
        red_node.parent.parent = RED
        red_node.parent.parent.rotate_right()
    else:
      #All the same stuff but switch left and right
  #somehow get root
  root.color = BLACK