RedBlack Tree Insertion
This lesson will cover the insertion operation in RedBlack trees, discussing all four insertion cases.
We'll cover the following
Insertion in RedBlack Tree
Here is a highlevel description of the algorithm involved in inserting a value in a RedBlack Tree:

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

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

If the given node is not the root, then we will have to perform some operations to make the tree follow the RedBlack property.
Rebalancing the Tree
There are two ways to balance an unbalanced tree:
 Recoloring Nodes
 Rotating Nodes (left or right)
But before the details are explained, let’s define the structure of the RedBlack Tree and some nodes relative to the given node, 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, we will check Node U. Based on Node U’s color, we balance the tree. If Node U is Red, do the following:
 Change the color of Node P and U to Black
 Change the color of Node G to Red
 Make Node G the new current node and repeat the same process from step two