Do you think IIT Guwahati certified course can help you in your career?
No
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
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
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
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.
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.
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.
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.