Red-Black Tree Insertion

Insertion in Red-Black Tree #

The following are the steps involved in inserting value into a Red-Black Tree:

1. Insert currentNode using the standard BST insertion technique that we studied earlier, and make currentNode red.

2. If currentNode is the root, then change the color of currentNode to black.

3. If currentNode is not the root, then we will have to perform some operations to make the tree follow the Red-Black property.

Rebalancing the Tree #

To balance an unbalanced tree, we have two techniques which are used depending on some conditions that we will discuss shortly. The two techniques are:

1. Recoloring Nodes.
2. Rotating Nodes (left or right).

But before going deeper into the concepts that’ll be a mess for you to understand at this point, let’s slow down and go step by step.

First, we need to define the structure of the Red-Black Tree and some nodes relative to the currentNode, which is the node that we inserted in the Red-Black Tree.

• Node C – newly inserted node (currentNode)
• Node P – parent of currentNode
• Node G – grandparent of currentNode
• Node U – uncle of currentNode / sibling of Node P / child of Node G

If currentNode is not a root, and the parent of currentNode is not black, first, we will check Node U (the uncle of currentNode). Based on Node U’s color, we will perform some steps to make the tree balanced. If Node U is red, then do the following:

1. Change the color of Node P and U to black
2. Change the color of Node G to red
3. Make Node G the currentNode and repeat the same process from step two

Disclaimer: The illustrations given in this lesson are providing the visual representation of one case at a time. Therefore, you may notice that the tree gets unbalanced at the end of some of the illustrations. These trees have dummy values. However, in the case of an actual tree with real values, if one step ends up unbalancing the tree, then we keep moving in a bottom-up manner and applying the next possible case until the tree gets balanced again.