Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
1.1.
Left-Leaning Red-Black Tree
2.
Solution
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

Insertion in Left-Leaning Red-Black Tree

Author GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Problem

 

Design an algorithm to insert nodes in the Left-Leaning Red-Black Tree.

Input: Nodes data to insert in the tree.

Output: The inorder Traversal of the tree.

Left-Leaning Red-Black Tree


A left-leaning Red-Black Tree(LLRB) is a version of the Red-Black Tree that ensures O(logn) time for all search, delete, and insert operations. We can simulate all Red-Black Tree properties by following the characteristics mentioned below.

Characteristics/ Rules of LLRB. 

  1. The root node is always Black.
  2. The color of every new Node inserted is always Red.
  3. Every NULL child of a node is Black. 
  4. If a node has a right Red child and a left Black child (or NULL child because all NULLS are Black), left rotate the Node and swap the colors of the current Node and its left child to keep rule 2 consistent, i.e., the new Node must be Red.

Example, 

 

  1. If there is a node with a left Red child and a left RED grandchild, right-rotate the node and swap the colors of the current node and its right child to keep rule 2 consistent, i.e., the new node must be Red.

 

For example, 

 

  1. If a node has a left Red child and a Right Red child, invert the colors of the current node, left child, and the right child.

 

For example, 

 

Let’s understand with an example,

 


 

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 

 


 

Insert the following data into the LEFT-LEANING RED-BLACK TREE and print the inorder traversal of the tree.

 

Input: 2 4 6 5

Output: 2 4 5 6

 

Explanation:

 

Step1: Insert 2.

 

Step2: Insert 4.

 

Step3: Insert 6.

 

Step4: Insert 5.

 

Recommended: Try to solve it yourself before moving on to the solution.

Solution

 

Idea: The idea is to do insertions just like insertions in the Binary Search Tree. At every step, retrace back to the root and enforce the rules as mentioned above for LLRB.

Point to remember: The root may turn red while performing the above rotations and color swaps. We must ensure that the color of the root is always Black.
 

C++

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

struct node
{
    int data;
    // black --> false, red --> true.
    bool color;
    struct node *left, *right;

};

// Function to create a node.
node* newNode(int data, bool color)
{
    node *Node = new node();
    Node -> data = data;
    Node -> left = NULL;
    Node -> right = NULL;
    // New node is always red.
    Node -> color = true;
    return Node;
}

// Left Rotation.
node* leftRotate(node* Node)
{
    node *child = Node -> right;
    node *childLeft = child -> left;

    child -> left = Node;
    Node -> right = childLeft;

    return child;
}

// Right Rotation.
node* rightRotate(node* Node)
{
    node *child = Node -> left;
    node *childRight = child -> right;

    child -> right = Node;
    Node -> left = childRight;

return child;
}

// Function to check if the node is red in color.
bool isRed(node *Node)
{
    if (Node == NULL)
        return false;
    return (Node -> color == true);
}

// To swap the color of two nodes.
void swapColor(node *node1, node *node2)
{
    bool temp = node2 -> color;
    node2 -> color = node1 -> color;
    node1 -> color = temp;
}

// Insertion into the Left-Leaning Red-Black Tree.
node* insert(node* Node, int data)
{
    if ( !Node )
         return newNode(data, false);

    if (data < Node -> data)
        Node -> left = insert(Node -> left, data);

    else if (data > Node -> data)
        Node -> right = insert(Node -> right, data);

    else
        return Node;

    // case 1.
    // when the right child is Red, and the left child is Black or doesn't exist.
    if (isRed(Node -> right) && !isRed(Node -> left))
    {
         // Left rotate.
        Node = leftRotate(Node);

        // Swap the colors.
        swapColor(Node, Node -> left);
    }

    // case 2
    // when the left child, and the left grandchild in Red.
    if (isRed(Node -> left) && isRed(Node -> left -> left))
    {
        // Right rotate.
        Node = rightRotate(Node);

        // Swap the colors.
        swapColor(Node, Node -> right);
    }

    // case 3
    // when both the children are Red.
    if (isRed(Node -> left) && isRed(Node -> right))
    {

        // Invert the colors.
        Node -> color = !Node -> color;
        Node -> left -> color = false;
        Node -> right -> color = false;
    }
    return Node;
}

// Inorder traversal
void inorder(node *node)
{
    if(!node)
        return;
    inorder(node -> left);
    cout<< node -> data << " ";
    inorder(node -> right);
}

int main()
{
    node *root = NULL;

    // Make sure that the root remains black.
    root = insert(root, 2);
    root -> color = false;

    root = insert(root, 4);
    root -> color = false;

    root = insert(root, 6);
    root -> color = false;

    root = insert(root, 5);
    root -> color = false;

    // inorder traversal.
    cout<< "The inorder traversal is ";
    inorder(root);
    return 0;
}

 

Input: Insert in the order 2, 4, 6, 5.

Output:


The output tree is

 

Time Complexity:  O(log n), same as a BST.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What is a Red-Black Tree?
    A red-black tree is a self-balancing binary search tree with one extra bit at each node, which is a color (red or black). These colors are used to keep the tree balanced during insertions and deletions.
     
  2. What is a Binary Search Tree?
    A binary search tree (BST) is a binary tree in which each node has a Comparable key (and an associated value) greater than the keys in all nodes in its left subtree and smaller than the keys in all nodes in its right subtree.
     
  3. Why do we use Red-Black Trees?
    In the worst case, a BST may have a height of O(n) that takes O(n) time for search, insert, or delete operations, but a red-black tree is a height-balanced  BST with a worst-case height of O(logn).

Key Takeaways

 

In this article, we learned about the characteristics of the Left-Leaning Red-Black Tree and designed an algorithm to do insertions in it. 

With the help of an example, we learned about left rotations, right rotations, and color swapping to keep the tree height-balanced.

 

You can learn about trees from here.
Check out this problem - Largest BST In Binary Tree

 

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Previous article
Red-Black Trees Top-Down Insertion
Next article
Check if a given Binary Search Tree is height-balanced like a Red-Black Tree
Live masterclass