Table of contents
1.
Introduction
2.
Approach
3.
Algorithm 
4.
Code:
5.
Time Complexity 
6.
Space Complexity 
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

Red-Black Trees Top-Down Insertion

Author Apoorv
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

This blog will discuss how to insert a node in a red-black tree using a top-down approach. We are given an order in which nodes are entered, and we have to insert the same in the red-black tree. Write an efficient algorithm for Red-Black Trees Top-Down Insertion.

 

Approach

Bottom-Up Red-Black Tree insertion uses "basic" Binary Search Tree insertion, followed by RB-Tree Violation rectification on the way back up to the root. With the use of recursion, this is simple to accomplish. Corrections are made when navigating down the tree to the insertion location in Top-Down Insertion. There are no more corrections needed after the actual insertion, therefore there is no need to go back up the tree. As a result, the purpose of Top-Down insertion is to maintain RB characteristics while traversing from the root to the insertion site. As a result of this iterative strategy, Top-Down insertion is faster than Bottom-Up insertion. The given below is the detailed algorithm and implementation for this approach using English sentences for Red-Black Trees Top-Down Insertion.

 

Algorithm 

  • The two basic operations  for fixing the violations of the tree and balancing of the tree are Recoloring and Rotation
  • The main purpose of this technique is to find an insertion site where the new node's parent or uncle is black.
  • Let newNode be the new node that has to be added.
  • If Y and Z are Black or If X’s Parent is Black.
  • X’s Parent P is Red, Grandparent is Black and X and P are both left OR right children of Grandparent G:
  • Recolor X, Y, Z
  • Rotate P around G
  • Color P black
  • Color G red
  • X’s Parent is Red, Grandparent is Black and X and P are opposite children of Grandparent G
  • Recolor X, Y, Z
  • Rotate X around P
  • Rotate X around G
  • Recolor X and G

 

Code:

# Red-Black Trees Top-Down Insertion

# Red Black Tree structure and its methods
class RedblackTree:

    Root = None

    # Height calculation for a red black tree
    def HeightOfTree(self,Root):

        leftheight, rightheight=0, 0

        if (Root == None or (Root.child == None and Root.child[1] == None)):
            return 0
        leftheight = self.HeightOfTree(Root.child[0])
        rightheight = self.HeightOfTree(Root.child[1])

        return (max(leftheight, rightheight) + 1)

    @staticmethod
    def check(dir):
        return 1 if dir == 0 else 0

    # To check the node colour
    @staticmethod
    def isRed(currNode):
        return currNode != None and currNode.color=="Red"

    # Single rotation
    def SingleRotateTree(self, currNode, dir):

        curr = currNode.child[self.check(dir)]
        currNode.child[self.check(dir)] = curr.child[dir]
        curr.child[dir] = currNode
        self.Root.color = "Red"
        curr.color = "Black"

        return curr

    # Double rotation
    def DoubleRotateTree(self, currNode, dir):

        currNode.child[self.check(dir)] = self.SingleRotate(currNode.child[self.check(dir)], self.check(dir))
        return self.SingleRotate(currNode, dir)

    # Insertion of a new node in the tree
    def Insert(self, tree, val):

        if (tree.Root == None):

            tree.Root = TreeNode(val)
            if (tree.Root == None):
                return None
        else:

            # A temporary current root
            curr = TreeNode("")

            # Grandparent and Parent
            g, t=None,None
            p, q=None,None

            dir = 0; last = 0

            t = curr

            g = p = None

            t.child[1] = tree.Root

            q = t.child[1]
            while (True):

                if (q == None):

                    # Inserting root node
                    q = TreeNode(val)
                    p.child[dir] = q

                # If the Sibling is red
                elif (self.isRed(q.child[0]) and self.isRed(q.child[1])):

                    # Recoloring if both the children are red
                    q.color = "Red"
                    q.child[0].color = "Black"
                    q.child[1].color = "Black"

                if (self.isRed(q) and self.isRed(p)):

                    # Correcting the red red violation
                    dir2=0
                    if (t.child[1] == g):
                        dir2 = 1
                    else:
                        dir2 = 0

                    # If children and parent are left-left or
                    # right-right of grand-parent
                    if (q == p.child[last]):
                        t.child[dir2] = self.SingleRotateTree(g, 1 if last == 0 else 0)

                    # If they are opposite childs i.e left-right
                    # or right-left
                    else:
                        t.child[dir2] = self.DoubleRotateTree(g,1 if last == 0 else 0)

                # Current position of node 
                if (q.val==val):
                    break
                last = dir

                # Find path to traverse that may be either left or right
                dir = 1 if q.val<val else 0

                if (g != None):
                    t = g

                # Updating Pointers
                g = p
                p = q
                q = q.child[dir]

            tree.Root = curr.child[1]

        # Black colour to new node
        tree.Root.color = "Black"

        return tree.Root

    # level order traversal
    def PrintLevel(self, root, i):
        if (root == None):
            return

        if (i == 1):
            print("{} -- {} --".format(root.val,root.color),end='')

            if (root.child[0] != None):
                print(" {} --".format(root.child[0].val),end='')
            else:
                print(" None --",end='')
            if (root.child[1] != None):
                print(" {} --".format(root.child[1].val),end='')
            else:
                print(" None --",end='')

            return

        self.PrintLevel(root.child[0], i - 1)
        self.PrintLevel(root.child[1], i - 1)

    # level order traversal
    def LevelOrderTraversal(self, root):

        for i in range(self.HeightOfTree(root) + 1):
            self.PrintLevel(root, i)
            print('\n')

# Tree structure
class TreeNode:
    # constructor
    def __init__(self, val):

        self.val = val
        self.color = "Red" # R here is red colour
        self.child = [None,None]

# main code
# Red-Black Trees Top-Down Insertion storing a english sentence
if __name__=='__main__':
    # Tree Node format in the output
    
    # DATA -- COLOR -- LEFT CHILD -- RIGHT CHILD 
    
    InputTree = RedblackTree()
    Sentence, Word='',''
    Sentence = "rohan is good in"

    # Array containing all the words of the sentence
    Word_Array = Sentence.split()

    for i in range(len(Word_Array)):
        InputTree.Root = InputTree.Insert(InputTree, Word_Array[i])

    # Print Level Order Traversal
    print("The Level Order Traversal the tree is:")
    InputTree.LevelOrderTraversal(InputTree.Root)

    # inserting a new word in Red-Black Trees Top-Down Insertion
    print("\nAfter Insertion in the tree:")
    Word = "school"
    InputTree.Root = InputTree.Insert(InputTree, Word)

    InputTree.LevelOrderTraversal(InputTree.Root)
You can also try this code with Online Python Compiler
Run Code

 

 

Output:

The Level Order Traversal the tree is:

is -- B -- good -- rohan --

good -- B -- None -- in --rohan -- B -- None -- None --

in -- R -- None -- None --

After Insertion in the tree:

is -- B -- good -- rohan --

good -- B -- None -- in --rohan -- B -- None -- school --

in -- R -- None -- None --school -- R -- None -- None --
You can also try this code with Online Python Compiler
Run Code

 

 

Time Complexity 

 O(log(N))

The time complexity for Red-Black Trees Top-Down 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 the lowest position, it will cost the height of tree complexity which is log(N) in a self-balancing tree.

Space Complexity 

O(N)

The space complexity for Red-Black Trees Top-Down 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.

 

FAQs

 

  1. What is a Binary Search Tree?
    A genric tree with at most two child nodes for every node, the left subtree has a value less than the root node, and the right subtree has a value greater than the root node. 
     
  2. What is an AVL tree?
    AVL trees are self-balancing binary search trees. Here self-balancing means The height of the left and the right subtrees of every node differs by at most 1, which implies the difference between the heights will always be either 1,0 or -1.
     
  3. What is a Red-Black Tree?
    A red-black tree is a self-balancing binary search tree with one additional bit at each node, generally referred to as the color (red or black). As insertions and deletions are made, these colors are utilized to keep the tree balanced.

 

Key Takeaways

 

In this blog, we learned about red-black tree top-down insertion. Along with the algorithm, we also discussed the time and space complexity to insert a new node in the red-black tree.

Check out this problem - Duplicate Subtree In Binary Tree

If you want to learn more about red-black tree top-down insertion and want to practice some questions on red-black tree top-down insertion, deletion which require you to take your basic knowledge on these topics a notch higher, then you can visit our Guided Paths on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.

 

Live masterclass