Dealing with Black Uncles

The Rules:

1. a node is red or black
2. root is black
3. all leaves are black (null pointers count as leaves)
4. red nodes can only have black children
5. every path from node to leaves must have same # of black nodes (i.e. "black height")

The rules that matter:

4.  red nodes can only have black children
5. every path from any node to the leaves must have the same # of black nodes (black-height)
*.  (make a new node start out red)


x = the new node (or the node you recursed on)
p = new node's parent
u = new node's uncle, sibling of p
g = new node's grandparent



Root
Make it black.


Any Black Parent
You are done.


Red Parent, Red Uncle
Recolor, recurse on g



Red Parent, Black Uncle, Left-Left
R-Rotate(g)
recolor p, g



Red Parent, Black Uncle, Right-Right

L-Rotate(g)
recolor p,g



Red Parent, Black Uncle, Left-Right
L-Rotate(p)
Follow Left-Left procedure...



Red Parent, Black Uncle, Right-Left
R-Rotate(p)
Follow Right-Right procedure




Tips

You only need to get involved when the parent is red, and that is only difficult when you have a red parent AND a black uncle.  In that case there are four cases, but two of them (the ones with both 'right' and 'left' in the title are just an extra step on top of the others).

Now as far as remembering this shit for longer than a week...I have no idea.