# Red-Black Tree (Python Code with Examples)

In this article, we will study what is a red-black tree is and why it is useful. We will understand various operations of the red-black tree along with their algorithm, example, and python code. Later we will also go through various advantages, disadvantages, and applications of the red-black tree.

## What is a Red-Black Tree?

A red-black tree is the variation of the binary search tree with the property of self-balancing. A red-black tree is also called symmetric binary B-Tree. Every node of the red-black tree contains an extra attribute denoting the color of the node, specifically, either red or black. The importance of these colors in the nodes of the tree ensures that the tree is balanced while insertion and deletion operations of the node. Therefore, the red-black tree follows the below properties:

1. Tree Property: Red-Black tree should be a binary search tree.
2. Red/Black Property: Every node of the tree is colored either red or black.
3. Root Property: The color attribute of the root node is always black.
4. Leaf Property: Every leaf of the tree is black.
5. Red Property: The child node is always black if the parent node is red in color. Therefore, there should not be two consecutive red nodes.
6. Depth Property: Every path from the root node to any leaf node should have the same number of black-colored nodes.

Remember that every node of the red-black tree consumes only 1 bit of memory storage to store the color information, hence the tree is identical to the classic binary search tree.

### Why Use Red-Black Tree?

As you know that binary search tree maintains the natural order of the data inserted, but it does not restrict the size, length, or height of the tree. Consider the below image where the nodes inserted in the binary search tree are 10,20,30,40,50. Here, the height of the tree is 5 as the tree grows linearly when the new node is inserted. Hence, as the height of the tree grows linearly, the search operation in the tree becomes the worst-case scenario and takes O(n) time where n is the total number of nodes inserted. This problem can be solved by using a red-black tree. As the red-black tree maintains its height of the tree after every insertion and deletion operation, the tree can be avoided from skewing. Therefore, the time complexity for search operation is reduced to O(log n) where n is the number of nodes in the tree.

Instead of a red-black tree, you can also use an AVL tree to balance the height of the tree. But it is noted, that the red-black tree makes fewer structural changes to balance the height of the tree in comparison to AVL trees. Hence, the red-black tree is potentially faster during insertion and deletion operations in comparison to AVL trees.

## Rotations in Red Black Tree

The rotation is the process of adjusting or interchange the nodes of the subtrees inside the tree in such a way that the height of the tree is restored. It helps to maintain the red-black tree properties which are sometimes violated while insertion and deletion operations. Basically, there are two types of rotation in Red-Black Tree:

### 1) Left Rotation

The nodes on the right of the tree are transformed on the left node is called the left rotation. Look at the below algorithm for understanding.

Algorithm

• Consider the below red-black tree • Assign ‘a’ as a parent node of the left subtree of ‘b’, if ‘b’ has a left subtree. • Assign ‘b’ as the root of the tree if the parent node of ‘a’ is NULL
• Assign ‘b’ as the left child of ‘n’, if ‘a’ is the left child of ‘n’
• Assign ‘b’ as the right child of ‘n’, if ‘a’ is right child of ‘n’ • Make ‘b’ as the parent node of ‘a’ ### 2) Right Rotation

The nodes on the left of the tree are transformed on the right node is called the left rotation. Look at the below algorithm for understanding.

Algorithm

• Consider the below given red-black tree • Assign ‘b’ as the parent node of the right subtree of ‘a’, if ‘a’ has a right subtree • Assign ‘a’ as the root of the tree if the parent of ‘b’ is NULL
• Assign ‘a’ as the right child of ‘n’, if ‘b’ is the right child of ‘n’.
• Assign ‘a’ as the left child of ‘n’, if ‘b’ is the right child of ‘n’ • Make ‘a’ as the parent node of ‘b’ ### 3) Right-Left and Left-Right Rotations

In right-left rotation, first, you perform right rotation followed by a left rotation. In left-right rotation, first, you perform left rotation followed by right rotation ## Operations in Red-Black Tree

There are two operations performed in Red-Black Tree:

1. Insertion Operation
2. Deletion Operation

### 1) Insertion Operation

When you insert a new node in the tree, it will always be inserted as Red Node. This is because the insertion of a new node does not violate the depth property of the red-black tree. But what if the red node gets attached to the red node? Well, this problem is easier to fix using rotation rather than violating the depth property of the tree. Later, if the tree properties are violated then the red-black tree undergoes the following operations:

• Recolor
• Rotation

#### Algorithm For Insertion of the Node

```Let ‘x’ be the root node of the tree and ‘y’ be the leaf node
If the tree is empty, add NewNode as the root node and black in color
Else, repeat the below steps till we reach the leaf of the tree
Compare NewNode with RootNode

If NewNode is greater than RootNode, traverse to the right subtree

Otherwise, traverse through the left subtree

Assign parent of leaf to parent of NewNode
If LeafNode is greater than NewNode, assign NewNode as RightChild
Otherwise, assign NewNode as LeftChild
Assign Null to LeftChild and RightChild of NewNode
Assign NewNode as Red color
Apply InsertionFix Algorithm if the property of the red-black tree is violated
```

#### InsertionFix Algorithm to Maintain the Red-Black Tree Property

```If parent ‘n’ of NewNode is Red then:
If ‘n’ is the LeftChild of GrandParent ‘gp’ of ‘m’ then
Case 1:

If RightChild of ‘gp’ is Red color, set color of both children of ‘gp’ as Black color and ‘gp’ as Red Color

Assign ‘gp’ to NewNode

Case 2:

If NewNode is RightChild of ‘n’ then, assign ‘n’ to NewNode

Left-Rotate NewNode

Case 3:

Assign ‘n’ as Black and ‘gp’ as Red

Right-Rotate ‘gp’

Otherwise, do the following
If LeftChild of ‘gp’ of ‘z’ is Red color, then set both children of ‘gp’ as Black color and ‘gp’ as Red color

Assign ‘gp’ to NewNode

If NewNode is LeftChild of ‘n’ then, assign ‘n’ to NewNode and Right Rotate NewNode

Set ‘n’ as Black color and ‘gp’ as Red color

Left-Rotate ‘gp’

Set Root of the tree as Black color
```

Example

Insert node ‘4’ inside an empty tree. As discussed, the first inserted element is always the root node and black in color Now, insert node ‘20’ inside the tree. As 20 > 4, it will be inserted as the right subtree of the root node and red in color Now, insert node ‘31’ inside the tree. As 31> 20, it will be the right child of parent node ‘20’. Node ’31’ is red in color and according to the property of the red-black tree, no two red color nodes can be together and therefore we undergo the RR rotation to regain the balance of the tree. Now, insert node ‘14’ inside the tree. As 14> 4 but 14<20, node ‘14’ will be the right child of node ‘4’. Again, the red-black tree property is violated because you have two consecutive red color nodes. Hence, we perform the recoloring in the tree which results in a red-colored parent node. So we simple color it black colored as shown below Therefore the final tree structure will be as given below: ## Deletion Operation

When you delete a node from the tree, there are possibilities that you violate the red-black tree property. Therefore, after removing the node from the tree, make sure you balance the tree by following the properties of the tree.

#### Algorithm for Deleting a Node

```Save the color of DeletingNode in OriginalColor
If LeftChild of DeletingNode is Null
Assign the RightChild of DeletingNode to be ‘a’

Transplant DeletingNode with ‘a’

Otherwise, if the RighChild of DeletingNode is Null
Assign the LeftChild of DeletingNode into ‘a’

Transplant DeletingNode with ‘a’

Otherwise
Assign the minimum of Right-Subtree of DeletingNode into ‘b’

Save the color of ‘b’ in OriginalColor

Assign the RightChild of ‘b’ into ‘a’

If ‘b’ is a child of DeletingNode, then set the parent of ‘a’ as ‘b’

Otherwise, transplant ‘b’ with RightChild of ‘b’

Transplant DeletingNode with ‘b’

Set color of ‘b’ with OriginalColor

Call DeletionFix if the OriginalColor is Black
```

When the DeletingNode is black in color, it violates the red-black tree property. This scenario can be corrected by assuming that the node ‘a’ is had extra black. Therefore, node ‘a’ is neither Red nor Black rather it is either double black or black and red at the same time. Hence, the red-black tree property is violated.

Therefore, the extra black can be removed if

• It reached the RootNode
• If ‘a’ points to the red-black node. In this case, ‘a’ is colored, Black
• Required rotations and recoloring is performed

#### DeletionFix Algorithm to Maintain the Red-Black Tree Property

```Repeat the following until the ‘a’ is not the RootNode of the tree and ‘a’ is not the Black colored
If ‘a’ is the LeftChild of its parent then,
Assign ‘n’ to the sibling of ‘a’

If RightChild of the parent of ‘a’ is Red

Case 1:

Set RightChild of the parent of ‘a’ as Black color

Set parent of ‘a’ as Red Color

Left-Rotate the parent of ‘a’

Assign the RightChild of the parent of ‘a’ to ‘n’

If RightChild and the LeftChild of ‘n’ is Black in color
Case 2:

Set ‘n’ as Red color

Assign parent of ‘a’ to ‘a’

Otherwise, if the RightChild of ‘n’ is Black in color
Case 3:

Set the LeftChild of ‘n’ as Black color

Set ‘n’ as Red color

Right-rotate ‘n’

Assign the RightChild of the parent of ‘a’ to ‘n’

If all of the above cases don’t occur, then do the following
Case 4:

Set color of ‘n’ as the color of the parent of ‘a’

Set parent of ‘a’ as Black color

Set RightChild ‘n’ as Black color

Left-rotate the parent of ‘a’

Set ‘a’ as RootNode of tree

Repeat the same steps as above by interchanging the right to left and vice versa
Set ‘a’ as Black color
```

Example

Consider the below given red-black tree Now we want to delete 21 from the above tree. When node ‘21’ is deleted, it will be replaced by Null, so eventually Null will become double black as shown below Now according to the algorithm of deletion, sibling of DeletingNode i.e Node ‘41’ is black colored with at least one red-colored child i.e. Node ‘36’ and Node ‘51’. Therefore, it will undergo RR rotation to retain the balance of the tree as shown below Hence, the final tree structure will be as given below ## Python Code for Red-Black Tree

```# Define Node
class Node():
def __init__(self,val):
self.val = val                                   # Value of Node
self.parent = None                               # Parent of Node
self.left = None                                 # Left Child of Node
self.right = None                                # Right Child of Node
self.color = 1                                   # Red Node as new node is always inserted as Red Node

# Define R-B Tree
class RBTree():
def __init__(self):
self.NULL = Node ( 0 )
self.NULL.color = 0
self.NULL.left = None
self.NULL.right = None
self.root = self.NULL

# Insert New Node
def insertNode(self, key):
node = Node(key)
node.parent = None
node.val = key
node.left = self.NULL
node.right = self.NULL
node.color = 1                                   # Set root colour as Red

y = None
x = self.root

while x != self.NULL :                           # Find position for new node
y = x
if node.val < x.val :
x = x.left
else :
x = x.right

node.parent = y                                  # Set parent of Node as y
if y == None :                                   # If parent i.e, is none then it is root node
self.root = node
elif node.val < y.val :                          # Check if it is right Node or Left Node by checking the value
y.left = node
else :
y.right = node

if node.parent == None :                         # Root node is always Black
node.color = 0
return

if node.parent.parent == None :                  # If parent of node is Root Node
return

self.fixInsert ( node )                          # Else call for Fix Up

def minimum(self, node):
while node.left != self.NULL:
node = node.left
return node

# Code for left rotate
def LR ( self , x ) :
y = x.right                                      # Y = Right child of x
x.right = y.left                                 # Change right child of x to left child of y
if y.left != self.NULL :
y.left.parent = x

y.parent = x.parent                              # Change parent of y as parent of x
if x.parent == None :                            # If parent of x == None ie. root node
self.root = y                                # Set y as root
elif x == x.parent.left :
x.parent.left = y
else :
x.parent.right = y
y.left = x
x.parent = y

# Code for right rotate
def RR ( self , x ) :
y = x.left                                       # Y = Left child of x
x.left = y.right                                 # Change left child of x to right child of y
if y.right != self.NULL :
y.right.parent = x

y.parent = x.parent                              # Change parent of y as parent of x
if x.parent == None :                            # If x is root node
self.root = y                                # Set y as root
elif x == x.parent.right :
x.parent.right = y
else :
x.parent.left = y
y.right = x
x.parent = y

# Fix Up Insertion
def fixInsert(self, k):
while k.parent.color == 1:                        # While parent is red
if k.parent == k.parent.parent.right:         # if parent is right child of its parent
u = k.parent.parent.left                  # Left child of grandparent
if u.color == 1:                          # if color of left child of grandparent i.e, uncle node is red
u.color = 0                           # Set both children of grandparent node as black
k.parent.color = 0
k.parent.parent.color = 1             # Set grandparent node as Red
k = k.parent.parent                   # Repeat the algo with Parent node to check conflicts
else:
if k == k.parent.left:                # If k is left child of it's parent
k = k.parent
self.RR(k)                        # Call for right rotation
k.parent.color = 0
k.parent.parent.color = 1
self.LR(k.parent.parent)
else:                                         # if parent is left child of its parent
u = k.parent.parent.right                 # Right child of grandparent
if u.color == 1:                          # if color of right child of grandparent i.e, uncle node is red
u.color = 0                           # Set color of childs as black
k.parent.color = 0
k.parent.parent.color = 1             # set color of grandparent as Red
k = k.parent.parent                   # Repeat algo on grandparent to remove conflicts
else:
if k == k.parent.right:               # if k is right child of its parent
k = k.parent
self.LR(k)                        # Call left rotate on parent of k
k.parent.color = 0
k.parent.parent.color = 1
self.RR(k.parent.parent)              # Call right rotate on grandparent
if k == self.root:                            # If k reaches root then break
break
self.root.color = 0                               # Set color of root as black

# Function to fix issues after deletion
def fixDelete ( self , x ) :
while x != self.root and x.color == 0 :           # Repeat until x reaches nodes and color of x is black
if x == x.parent.left :                       # If x is left child of its parent
s = x.parent.right                        # Sibling of x
if s.color == 1 :                         # if sibling is red
s.color = 0                           # Set its color to black
x.parent.color = 1                    # Make its parent red
self.LR ( x.parent )                  # Call for left rotate on parent of x
s = x.parent.right
# If both the child are black
if s.left.color == 0 and s.right.color == 0 :
s.color = 1                           # Set color of s as red
x = x.parent
else :
if s.right.color == 0 :               # If right child of s is black
s.left.color = 0                  # set left child of s as black
s.color = 1                       # set color of s as red
self.RR ( s )                     # call right rotation on x
s = x.parent.right

s.color = x.parent.color
x.parent.color = 0                    # Set parent of x as black
s.right.color = 0
self.LR ( x.parent )                  # call left rotation on parent of x
x = self.root
else :                                        # If x is right child of its parent
s = x.parent.left                         # Sibling of x
if s.color == 1 :                         # if sibling is red
s.color = 0                           # Set its color to black
x.parent.color = 1                    # Make its parent red
self.RR ( x.parent )                  # Call for right rotate on parent of x
s = x.parent.left

if s.right.color == 0 and s.right.color == 0 :
s.color = 1
x = x.parent
else :
if s.left.color == 0 :                # If left child of s is black
s.right.color = 0                 # set right child of s as black
s.color = 1
self.LR ( s )                     # call left rotation on x
s = x.parent.left

s.color = x.parent.color
x.parent.color = 0
s.left.color = 0
self.RR ( x.parent )
x = self.root
x.color = 0

# Function to transplant nodes
def __rb_transplant ( self , u , v ) :
if u.parent == None :
self.root = v
elif u == u.parent.left :
u.parent.left = v
else :
u.parent.right = v
v.parent = u.parent

# Function to handle deletion
def delete_node_helper ( self , node , key ) :
z = self.NULL
while node != self.NULL :                          # Search for the node having that value/ key and store it in 'z'
if node.val == key :
z = node

if node.val <= key :
node = node.right
else :
node = node.left

if z == self.NULL :                                # If Kwy is not present then deletion not possible so return
print ( "Value not present in Tree !!" )
return

y = z
y_original_color = y.color                          # Store the color of z- node
if z.left == self.NULL :                            # If left child of z is NULL
x = z.right                                     # Assign right child of z to x
self.__rb_transplant ( z , z.right )            # Transplant Node to be deleted with x
elif (z.right == self.NULL) :                       # If right child of z is NULL
x = z.left                                      # Assign left child of z to x
self.__rb_transplant ( z , z.left )             # Transplant Node to be deleted with x
else :                                              # If z has both the child nodes
y = self.minimum ( z.right )                    # Find minimum of the right sub tree
y_original_color = y.color                      # Store color of y
x = y.right
if y.parent == z :                              # If y is child of z
x.parent = y                                # Set parent of x as y
else :
self.__rb_transplant ( y , y.right )
y.right = z.right
y.right.parent = y

self.__rb_transplant ( z , y )
y.left = z.left
y.left.parent = y
y.color = z.color
if y_original_color == 0 :                          # If color is black then fixing is needed
self.fixDelete ( x )

# Deletion of node
def delete_node ( self , val ) :
self.delete_node_helper ( self.root , val )         # Call for deletion

# Function to print
def __printCall ( self , node , indent , last ) :
if node != self.NULL :
print(indent, end=' ')
if last :
print ("R----",end= ' ')
indent += "     "
else :
print("L----",end=' ')
indent += "|    "

s_color = "RED" if node.color == 1 else "BLACK"
print ( str ( node.val ) + "(" + s_color + ")" )
self.__printCall ( node.left , indent , False )
self.__printCall ( node.right , indent , True )

# Function to call print
def print_tree ( self ) :
self.__printCall ( self.root , "" , True )

if __name__ == "__main__":
bst = RBTree()

bst.insertNode(10)
bst.insertNode(20)
bst.insertNode(30)
bst.insertNode(5)
bst.insertNode(4)
bst.insertNode(2)

bst.print_tree()

print("\nAfter deleting an element")
bst.delete_node(2)
bst.print_tree()```

### Output

R---- 20(BLACK)
L---- 5(RED)
| L---- 4(BLACK)
| | L---- 2(RED)
| R---- 10(BLACK)
R---- 30(BLACK)

After deleting an element
R---- 20(BLACK)
L---- 5(RED)
|    L---- 4(BLACK)
|    R---- 10(BLACK)
R---- 30(BLACK)

### Time Complexity

For insertion, deletion, and search operation, the time complexity for the red-black tree is logarithmic function i.e. O(log n) where n is the total number of nodes in the red-black tree. Whereas, the space complexity of the red-black tree is O(n).

## Difference between Red-Black Tree and AVL Tree

 Red-Black Tree AVL Tree It does not provide efficient searching as red-black tree are roughly balanced It provides efficient searching as AVL trees are strictly balanced Insertion and deletion operation is easier as require less number of rotation to balance the tree Insertion and deletion operation is difficult as require more number of rotation to balance the tree The nodes are either red or black in color The nodes have no colors It does not contain any balance factor to balance the height of the tree It contains the balance factor to maintain the difference in the height of the tree. Mostly used for insertion and deletion operations Mostly used for searching operations

• Red-black tree balance the height of the binary tree
• Red-black tree takes less time to structure the tree by restoring the height of the binary tree
• The time complexity for search operation is O(log n)
• It has comparatively low constants in a wide range of scenarios

• Relatively complicated to implement
• The red-black tree is not rigidly balanced in comparison to the AVL tree

## Applications of Red-Black Tree

• A red-black tree is used to implement the finite maps
• It is most important to implement the Java Libraries Packages like java.util.TreeSet and java.util.TreeMap
• A red-black tree is used while building the Linux kernel
• A red-black tree is used to implement the standard template library in C++
• It is used to implement the CPU scheduling algorithm like “completely fair scheduler” in Linux.
• A red-black tree is used in reducing the time complexity in the K-mean clustering algorithm
• It is used in MySQL for table indexing
• A red-black tree is used in Computation Geometry Data structure
• It is useful to keep track of the virtual memory segments for the process
• Hashmap data structure makes use of the red-black tree to store the key-value pair instead of linked-list for the faster search operation

## Conclusion

The red-black tree is one of the members of the binary search tree which helps to maintain the height of the binary tree just like the AVL tree. Every node in the binary search tree is colored either red or black which further helps to maintain the properties of the tree and provides an effective and efficient method for insertion and deletion operations of the node in the binary tree by undergoing a fewer rotation. Therefore it is important to understand and make use of the red-black tree to enhance the searching time complexity of the binary search tree by preventing the tree from skewing. For more details, please refer to our extensive tutor program designed by experts at Favtutor

### FavTutor - 24x7 Live Coding Help from Expert Tutors! 