Red Black Trees

Insertion

Red Aunt

1. Swap the colors of the parent, aunt, & grandparent
2. Check for red-child violations

Black Aunt Aligned

1. Rotate parent & grandparent
2. Swap colors of parent & grandparent

Black Aunt Not Aligned

1. Rotate parent & grandparent (don't recolor)
2. Rotate new parent & grandparent
3. Recolor parent & grandparent

Deletion

Black Sibling & Black Niece

1. Recolor sibling
2. Move Black Marker up one
• If the parent is red, recolor and resolve Black Marker
• If the parent is black, continue resolving (looking at the parent node's sibling)
• If the parent is the root, resolve the Black Marker

Black Sibling & Red Niece

1. If Sibling and Red Niece are NOT aligned then rotate & recolor them
2. Rotate the parent & sibling
3. Recolor the parent, sibling, & niece

Red Sibling

1. Rotate & recolor the parent & sibling
2. Continue to resolve the Black Marker with the new tree configuration

For more information, visit UW Madison's page on Red Black Trees