Painless Red-Black Tree Implementation – Insertion

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:

  1. 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.
    Parent and Uncle become black, grandparent becomes red.
  2. 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:
        Left shift on parent
        Right shift on grandparent for Left Right case. Will have the original node as the new red root of the subtree, with its original parent being the left black child, and grandparent being its right black child.
      • Node is left child of parent: Node is to the left left of grandparent, so just need to do a right rotation on grandparent:
        Right shift on grandparent for Left Left case. Will have the original parent as the new red root of the subtree, with the original node being the left black child, and grandparent being its right black child.
    • 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:
        Right shift on parent
        Left shift on grandparent for Right Left case. Will have the original node as the new red root of the subtree, with its original parent being the left black child, and grandparent being its right black child.
      • Node is right child of parent: Node is to the right right of grandparent, so just need to do a left rotation on grandparent:
        Left shift on grandparent for Right Right case. Will have the original parent as the new red root of the subtree, with the original node being the right black child, and grandparent being its left black child.

    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.

Leave a Reply

Your email address will not be published. Required fields are marked *

[TOP]