Red-Black Trees: Insertion

Below are the details of the different cases that can occur after the insertion of a new node into a red-black tree.

Case 1: Red Aunt

1. Rotate (if necessary): Rotate the red parent and child if they are not in alignment.
2. Rotate: Rotate the red parent with the subtree's root node.
3. Recolor: Change the nodes colors so that the new root node is black and its children are both red.

Case 2: Black Aunt

1. Recolor: Change the root node to red and its childre to black.
2. Check: Look to see if the recolored root node has cased any double red violations.