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.

For a complete description of what a Red-Black tree is (including some terminology I will be using), see my **Red-Black Tree Introduction**.

You can view my complete C++ insertion code or the complete implementation of a Red-Black Tree on GitHub.

### Insertion

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.**Node is right child of parent:**Node is to the left right of grandparent, so need to do a**left rotation**on parent before a**right rotation**on grandparent:

**Node is left child of parent:**Node is to the left left of grandparent, so just need to do a**right rotation**on grandparent:

**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.**Node is left child of parent:**Node is to the right left of grandparent, so need to do a**right rotation**on parent before a**left rotation**on grandparent:

**Node is right child of parent:**Node is to the right right of grandparent, so just need to do a**left rotation**on 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.

I have example code for insertion in C++, and the complete Red Black Tree C++ implementation is available on GitHub. I have also created a post for how to implement deletion in a Red Black Tree.