Red Black Tree Insertion

What is the insertion operation in the red-black tree?

The insertion operation in a red-black tree is a process that involves adding a new node while maintaining the tree’s balanced structure and its properties. A red-black tree is a type of self-balancing binary search tree with specific rules that make sure the tree remains roughly balanced after each insertion. Here’s how insertion works in a red-black tree:

1. Standard BST Insertion: First, the new node is added just like in a regular binary search tree (BST). It’s inserted as a red node (which helps with balancing) to the appropriate position following the BST property.

2. Fixing Violations: After insertion, the tree may violate the red-black tree properties:

• Every node is either red or black.
• The root is always black.
• Red nodes cannot have red children (no consecutive red nodes).
• Every path from a node to its descendant NULL nodes has the same number of black nodes (black height).

3. Balancing Steps (Cases): When a red-red conflict occurs, there are three main cases to resolve it, depending on the colors of the uncle node (the sibling of the parent node):

• Case 1 (Recoloring): If the parent and uncle are both red, the color of the parent and uncle is changed to black, and the grandparent is changed to red. The process is then repeated up the tree to check if the new configuration violates any properties.
• Case 2 (Rotation and Recoloring): If the parent is red, but the uncle is black, and the node is an "inner child" (left-right or right-left), a rotation is performed to convert the tree into an outer case (left-left or right-right). This rotation is called a "double rotation" or "rotation to fix insertion."
• Case 3 (Single Rotation and Recoloring): If the parent is red, the uncle is black, and the node is an outer child (left-left or right-right), a single rotation is performed, and colors of nodes are adjusted to maintain red-black properties.

4. Ensuring Root is Black: After resolving any red-red conflicts, the last step is to ensure the root node is black, as this is a requirement in red-black trees. If the root node turns red during the balancing process, it’s simply recolored to black.

Algorithm to Insert a New Node

To insert a new node into a Red-Black Tree, we follow a specific algorithm to ensure the tree maintains its balance and red-black properties. Here’s the step-by-step algorithm for insertion in a Red-Black Tree:

1. Insert the new node:

• Insert the new node just like in a regular binary search tree (BST). This new node is always inserted as a red node.
• The node will initially be placed at the correct position based on its value.

2. Fix Violations (Balancing the Tree):

• After insertion, we need to fix any violations of the Red-Black Tree properties. This may involve changing the colors of nodes and performing rotations.

3. Fix the tree for violations (start from the newly inserted node and work upwards):

• Case 1: If the parent of the newly inserted node is black, no violation occurs, and the insertion is complete.
• Case 2: If the parent is red, a violation occurs (since two consecutive red nodes violate the Red-Black property). This needs to be fixed with one of the following steps:

Steps to Fix Violations

Case 1: No violation (Parent is black)

• If the parent of the newly inserted node is black, the Red-Black Tree properties are maintained, and no further action is required.

Case 2: Violation (Parent is red)

• If both the parent and the uncle (sibling of the parent) of the newly inserted node are red, we have a violation. In this case:
  1. Recoloring: Change the parent and the uncle to black, and the grandparent to red.
  2. Move the pointer up to the grandparent and repeat the process.

Case 3: Violation (Parent is red, Uncle is black or NULL)

• If the parent is red, but the uncle is black or NULL, we need to perform rotations to restore balance:
  1. Left-Left Case (Outer Case): If the newly inserted node is the left child of the left child of the parent, perform a right rotation on the grandparent.
  2. Right-Right Case (Outer Case): If the newly inserted node is the right child of the right child of the parent, perform a left rotation on the grandparent.
  3. Left-Right or Right-Left Case (Inner Case): If the newly inserted node is the right child of the left child of the parent, or the left child of the right child of the parent, perform a double rotation:
     • First, rotate the parent (left or right depending on the case) to convert the inner case into an outer case.
     • Then perform the outer rotation as described in cases 1 or 2.
  4. Fix the root color: After fixing the violations, ensure that the root of the tree is always black. If the root is red, recolor it to black.

Example 1

Input

The order of nodes for red black tree insertion:

11, 19, 6, 15, 16, 31, 27

Output

Inorder Traversal of the new Tree is:

6 11 15 16 19 27 31 

Explanation

Step 1: If the tree is empty, create a new node as a root node with the color black.

Step 2: If the tree is not empty, create a new node as a leaf node with red color.

Step 3: If the tree is not empty, create a new node as a leaf node with red color.

Step 4:  If a parent of the new node is red then check, the color of the parent’s sibling of the new node, and if If color is red, then recolor and also check parent’s parent of the new node is not the root node, then recolor it and recheck.

Step 5:  If the parent of the new node is red then check, the color of the parent’s sibling of the new node and If the color is black or null, then do suitable rotation and recolor. For rotation, we use the AVL tree’s rotation technique.

Step 6: Using the LR rotation technique of  AVL trees, first, we will rotate left and then right. So first, after left rotationt.

Step 7: After left rotation to apply the right rotation technique on the tree.

Step 8: If the parent of the new node is red then check, the color of the parent’s sibling of the new node, and if If color is red, then recolor and also check the parent’s parent of the new node whether the root node is, then recolor it and recheck.

Step 9: If the parent of the new node is red then check, the color of the parent’s sibling of the new node and If the color is black or null, then do suitable rotation and recolor. For rotation, we use the AVL tree’s rotation technique.

Step 10: After doing RL rotation 

Approaches in Red Black Tree Insertion

In the AVL tree, we use the concept of rotation to do the balancing. In Red Black tree insertion, we have to use two techniques that are rotation and recoloring. First, we try for recoloring if the recoloring does not work, then we go for rotation. The recoloring algorithm work on two edge case that is based on the parent’s sibling color. Given below is the detailed algorithm.

Algorithm

1. If the tree is empty, create a new node as a root node with the color black.
2. If the tree is not empty, create a new node as a leaf node with red color.
3. If a parent of the new node is black, then exit.
4. If the parent of the new node is red then check, the color of the parent’s sibling of the new node:
5. If the color is black or null, then do suitable rotation and recolor.
6. If the color is red, then recolor and also check parent’s parent of the new node is not the root node, then recolor it and recheck

Insertion in Red Black Tree Examples

Implementation:

• C++

C++

#include <bits/stdc++.h>
using namespace std;


// Two colors of the red black tree
enum Colors {RED, BLACK};


// Tree Node structure
class TreeNode
{
    public:

    int val;
    bool color;
    TreeNode *left, *right, *parent;

    // Constructor 
    TreeNode(int val)
    {
    this->val = val;
    left = right = parent = NULL;
    this->color = RED;
    }
};


// Red-Black Tree structure
class RedBlackTree
{
public:
    TreeNode *root;

    // Functions for rotation
    void rotateLeft(TreeNode *&, TreeNode *&);
    void rotateRight(TreeNode *&, TreeNode *&);
    void fixViolation(TreeNode *&, TreeNode *&);

    // Constructor
    RedBlackTree() { root = NULL; }
    void insert(const int &n);
    void inorder();
    void levelOrder();
};

// Inorder traversal
void inorderHelper(TreeNode *root)
{
    if (root == NULL)
        return;

    inorderHelper(root->left);
    cout << root->val << " ";
    inorderHelper(root->right);
}

// New node insertion in BST
TreeNode* BSTInsert(TreeNode* root, TreeNode *newnode)
{

    // If root is null simply return node to be inserted
    if (root == NULL)
    return newnode;

    // else recursively iterate on BST
    if (newnode->val < root->val)
    {
        root->left = BSTInsert(root->left, newnode);
        root->left->parent = root;
    }
    else if (newnode->val > root->val)
    {
        root->right = BSTInsert(root->right, newnode);
        root->right->parent = root;
    }

    return root;
}

// Left Rotation for avl trees
void RedBlackTree::rotateLeft(TreeNode *&root, TreeNode *&newnode)
{
    TreeNode *newnode_right = newnode->right;

    newnode->right = newnode_right->left;

    if (newnode->right != NULL)
        newnode->right->parent = newnode;

    newnode_right->parent = newnode->parent;

    if (newnode->parent == NULL)
        root = newnode_right;

    else if (newnode == newnode->parent->left)
        newnode->parent->left = newnode_right;

    else
        newnode->parent->right = newnode_right;

    newnode_right->left = newnode;
    newnode->parent = newnode_right;
}

// Right rotation for avl trees
void RedBlackTree::rotateRight(TreeNode *&root, TreeNode *&newnode)
{
    TreeNode *newnode_left = newnode->left;

    newnode->left = newnode_left->right;

    if (newnode->left != NULL)
        newnode->left->parent = newnode;

    newnode_left->parent = newnode->parent;

    if (newnode->parent == NULL)
        root = newnode_left;

    else if (newnode == newnode->parent->left)
        newnode->parent->left = newnode_left;

    else
        newnode->parent->right = newnode_left;

    newnode_left->right = newnode;
    newnode->parent = newnode_left;
}

// To fix error caused by insertion in BST
void RedBlackTree::fixViolation(TreeNode *&root, TreeNode *&newnode)
{
    TreeNode *parent_newnode = NULL;
    TreeNode *grand_parent_newnode = NULL;

    while ((newnode != root) && (newnode->color != BLACK) &&
        (newnode->parent->color == RED))
    {

        parent_newnode = newnode->parent;
        grand_parent_newnode = newnode->parent->parent;

        //  Case 1
        // Parent of current is left child of Grand-parent of newnode 
        if (parent_newnode == grand_parent_newnode->left)
        {

            TreeNode *uncle_newnode = grand_parent_newnode->right;

            // Case 1.1
            // The parent's sibling of newnode is also red Only Recoloring required 
            if (uncle_newnode != NULL && uncle_newnode->color ==
                                                RED)
            {
                grand_parent_newnode->color = RED;
                parent_newnode->color = BLACK;
                uncle_newnode->color = BLACK;
                newnode = grand_parent_newnode;
            }

            else
            {
                // Case 1.2
                // new node is right child of its parent hence Left-rotation required 
                if (newnode == parent_newnode->right)
                {
                    rotateLeft(root, parent_newnode);
                    newnode = parent_newnode;
                    parent_newnode = newnode->parent;
                }

                // Case  1.3
                // new node is left child of its parent hence Right-rotation required 
                rotateRight(root, grand_parent_newnode);
                swap(parent_newnode->color,
                        grand_parent_newnode->color);
                newnode = parent_newnode;
            }
        }

        // Case 2
        // Parent of new node is right child of Grand-parent of newnode 
        else
        {
            TreeNode *uncle_newnode = grand_parent_newnode->left;

            // Case 2.1
            // The parent's sibling of new node is also red hence Only Recoloring required
            if ((uncle_newnode != NULL) && (uncle_newnode->color ==
                                                    RED))
            {
                grand_parent_newnode->color = RED;
                parent_newnode->color = BLACK;
                uncle_newnode->color = BLACK;
                newnode = grand_parent_newnode;
            }
            else
            {

                // Case : 2.2
                // new node is left child of its parent hence Right-rotation required 
                if (newnode == parent_newnode->left)
                {
                    rotateRight(root, parent_newnode);
                    newnode = parent_newnode;
                    parent_newnode = newnode->parent;
                }

                // Case : 2.3
                // newnode is right child of its parent hence Left-rotation required 
                rotateLeft(root, grand_parent_newnode);
                swap(parent_newnode->color,
                        grand_parent_newnode->color);
                newnode = parent_newnode;
            }
        }
    }

    root->color = BLACK;
}

// Insert new node in redblack tree
void RedBlackTree::insert(const int &val)
{
    TreeNode *newnode = new TreeNode(val);

    // Normal insert for BST
    root = BSTInsert(root, newnode);

    // fix Red Black Tree violations
    fixViolation(root, newnode);
}

// Function to do inorder and level order traversals
void RedBlackTree::inorder(){ inorderHelper(root);}

int main()
{
    RedBlackTree tree;
 
    // Red black tree insertion order
    tree.insert(11);
    tree.insert(19);
    tree.insert(6);
    tree.insert(15);
    tree.insert(16);
    tree.insert(31);
    tree.insert(27);

    cout << "Inorder Traversal of the new Tree is:"<<endl;
    tree.inorder();

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Inorder Traversal of the new Tree is:
6 11 15 16 19 27 31

Time Complexity 

 O(log(N))

The time complexity for red black tree insertion is log(N), where ‘N’ is the number of nodes already present in the red-black tree. Since in order to insert a node in a self-balancing tree at every root node, we have two options either to go to the left or to go to the right. So at max, if the node is to be inserted at lowest position, it will cost height of tree complexity which is log(N) in a self-balancing tree.

Space Complexity

O(N)

The space complexity for red black tree insertion is O(N), where ‘N’ is the total number of nodes in the red-black trees. Since we are not using any extra space here so, no extra space complexity will be utilized, but due to recursion, the recursion call stack will roughly consume linear time complexity.

Frequently Asked Questions

What is the insertion complexity of a red-black tree?

The insertion complexity of a red-black tree is O(log⁡n)O(\log n)O(logn), as it involves standard BST insertion followed by a constant number of rotations and recoloring.

When inserting a new entry into a red-black tree, what condition might happen?

During insertion, the newly added node may violate the red-black properties, requiring recoloring or rotations to restore balance.

What is the difference between AVL tree and red-black tree?

AVL trees are strictly balanced, providing faster searches but requiring more rotations for insertions/deletions. Red-Black trees allow slight imbalance, making insertions/deletions faster but searches slightly slower. AVL suits searches; Red-Black suits frequent updates.

Conclusion

In this blog, we learned about red black tree insertion. Along with the algorithm, we also discussed the time and space complexity to insert a new node in red-black tree.
Check out this problem - Largest BST In Binary Tree