This post will outline the procedure for inserting an element into a Red-Black Tree. I have a separate post for deletion. This post will not focus on why all of the different cases are needed and why they work, but I may be following up with a separate post to further explain.
If the tree is currently empty, just create a new node, set its color to be black (since the color of the root must be black), and set it to be the root.
Otherwise, the first step for insertion is to insert a node like how it would normally be inserted in a binary search tree – by following nodes that are already in the tree, until you have the new nodes parent. Add the new node as a red child.
If the parent that the node will be inserted under is black, then the tree is balanced and the insertion is complete.
So long as the node being considered and its parent is red, will need to handle the double red special case:
- Uncle is red: In this case, can push the blackness from the grandparent to parent and uncle. So set the parent and uncle to be black.
Then, if the grandparent is not the root, set it to be red. If the parent of the grandparent is red, then need to recursively handle the double red special case, with the grandparent as the node being considered in double red case.
- Otherwise: will need to do rotations based around the grandparent, with there being 4 different rotation subcases, depending on the orientation of nodes to each other. The final coloring will be identical. The two main subcases are based on the parents relation to grandparent:
- Parent is left child of grandparent: Will ultimately do a right rotation on grandparent to shift it to the right side of the subtree.
- Parent is right child of grandparent: These cases work out to be the exactly opposite compared to if the parent was to the left of the grandparent.
Once the rotations are completed, the new subtree owner (the new parent for what was the grandparent) must be colored black, while the grandparent and its new sibling should be red. This final color scheme is shown correctly for all of the above cases.
After these rotations and re-colorings, the tree is balanced.
The original sources I looked at to find out how to implement insertion in a Red Black tree are at http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees and http://www.geeksforgeeks.org/red-black-tree-set-2-insert.