Red-Black Tree Insertion

This lesson will cover the insertion operation in Red-Black trees, discussing all the four insertion cases.

We'll cover the following

Insertion in Red-Black Tree

Here is a high-level description of the algorithm involved in inserting a value in a Red-Black Tree:

  1. Insert the given node using the standard BST Insertion technique that we studied earlier and color it Red.

  2. If the given node is the root, then change its color to Black

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

Rebalancing the Tree

There are two ways to balance an unbalanced tree:

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

But before the details are explained, let’s define the structure of the Red-Black Tree and some nodes relative to the given node, which is the node that we inserted in the Tree.

  • Node C – the newly inserted node
  • Node P – the parent of the newly inserted node
  • Node G – the grandparent of the newly inserted node
  • Node U – the sibling of the parent of the newly inserted node, i.e., the sibling of Node P / child of Node G

If the newly inserted node is not a root and the parent of the newly inserted node is not Black, first, we will check Node U, which is based on Node U’s color, we balance the Tree. If Node U is Red, 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 new currentNode and repeat the same process from step two

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.