In this article, let’s try to understand the Red-Black Tree. A red-black tree is a self-balancing binary search tree that was invented in 1972 by Rudolf Bayer who called it the “symmetric binary B-tree.
Although a red-black tree is complex, it has good worst-case running time for its operations and is efficient to use as searching, insertion, and deletion. Those can all be done in O(logN) time, where N is the number of nodes in the tree.
Practically, a red-black tree is a binary search tree that inserts and removes intelligently, to keep the tree reasonably balanced. A special point to note about the red-black tree is that in this tree, no data is stored the leaf nodes.
Also read: Beam Search Algorithm With Logic and Implementation in Python
Properties of Red-Black Tree
A red-black tree is a binary search tree in which every node has a color that is either red or black. Apart from the other restrictions of a binary search tree, the red-black tree has the following additional requirements:
- The color of a node is either red or black.
- The color of the root node is always black.
- All leaf nodes are black.
- Every red node has both children colored in black.
- Every simple path from a given node to any of its leaf nodes has an equal number of black
The below figure is an example of a Red-Black Tree
These constraints enforce a critical property of red-black trees.
The longest path from the root node to any leaf node is no more than twice as long as the shortest path from the root to any other leaf in that tree.
This results in a roughly balanced tree. Since operations such as insertion, deletion, and searching require worst-case times proportional to the height of the tree, this theoretical upper bound on the height allows red-black trees to be efficient in the worst case, unlike ordinary binary search trees.
To understand the importance of these properties, it suffices to note that according to property 4, no path can have two red nodes in a row. The shortest possible path will have all black nodes, and the longest possible path would alternately have a red and a black node. Since all maximal paths have the same number of black nodes (property 5), no path is more than twice as long as any other path.
Different Operations on Red-Black Trees
Performing a read-only operation (like traversing the nodes in a tree) on a red-black tree requires no modification from those used for binary search trees. Remember that every red-black tree is a special case of a binary search tree. However, insertion and deletion operations may violate the properties of a red-black tree. Therefore, these operations may create a need to restore the red-black properties that may require a small number of (O(log N) or amortized O(1)) color changes.
1. Inserting Nodes
The insertion operation starts in the same way as we add a new node in the binary search tree. However, in a binary search tree, we always add the new node as a leaf, while in a red-black tree, leaf nodes contain no data. So instead of adding the new node as a leaf node, we add a red interior node that has two black leaf nodes. Note that the color of the new node is red and its leaf nodes are colored black. Once a new node is added, it may violate some properties of the red-black tree. So in order to restore their property, we check for certain cases and restore the property depending on the case that turns up after insertion.
When we insert a new node in a red-black tree, note the following:
- All leaf nodes are always black. So property 3 always holds true.
- Property 4 (both children of every red node are black) is threatened only by adding a red node, repainting a black node-red, or a rotation.
- Property 5 (all paths from any given node to its leaf nodes has an equal number of black nodes) is threatened only by adding a black node, repainting a red node black, or a rotation.
Case 1: New node added to root tree
In this case, N is repainted black, as the root of the tree is always black. Since s adds one black node to every path at once, Property 5 is not violated.
Case 2: New Node’s Parent (P) is Black
In this case, both children of every red node are black, so Property 4 is not invalidated. Property 5 is also not threatened. This is because the new node S has two black leaf children, but because is red, the paths through each of its children have the same number of black nodes.
(In the following cases, it is assumed that has a grandparent node (parent of parent node) – G, because its parent P is red, and if it were the root, it would be black. Thus, N also has an uncle node (sibling of the parent node) – U (irrespective of whether U is a leaf node or an internal node).)
Case 3: Both the Parent (P) and Uncle (U) Nodes are red.
In this case, Property 5 which says all paths from any given node to its leaf nodes have an equal number of black nodes is violated. Insertion in the third case is illustrated below.
In order to restore Property 5, both nodes (P and U) are repainted black and the grandparent G is repainted red. Now, the new red node N has a black parent. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed.
However, grandparent G may now violate Property 2 which says that the root node is always black or Property 4 which states that both children of every red node are black.
Property 4 will be violated when G has a red parent. In order to fix this problem, this entire procedure is recursively performed on G from Case 1.
Case 4: Parent P is Red but the Uncle U is Black and N is the Right Child of P and P is the Left Child of G
In order to fix this problem, a left rotation is done to switch the roles of the new node S and its parent. After the rotation, note that we have re-labeled N and P, and then, case 5 is called to deal with the new node’s parent. This is done because Property 4 which states that both children of every red node should be black is still violated. The below figure illustrates Case 4 insertion. Note that in the case of N being the left child and P being the right child of G, we have to perform a right rotation.
Case 5: Parent P is Red but the Uncle U is Black and the New Node N is the Left Child of P, and P is the Left Child of its Parent G.
In order to fix this problem, a right rotation on G (the grandparent of N) is performed. After this rotation, the former parent P is now the parent of both the new node N and the former grandparent G. We know that the color of G is black (because otherwise, its former child could not have been red). Now switch the colors of P and G so that the resulting tree satisfies Property 4 which states that both children of a red node are black. Case 5 insertion is illustrated in the below figure.
2. Deleting Node
We start deleting a node from a red-black tree in the same way as we do in the case of a binary search tree. In a binary search tree, when we delete a node with two non-leaf children, we find either the maximum element in its left sub-tree of the node or the minimum element in its right sub-tree, and move its value into the node being deleted.
After that, we delete the node from which we had copied the value. Note that this node must have less than two non-leaf children. Therefore, merely copying a value does not violate any red-black properties, but it just reduces the problem of deleting to the problem of deleting a node with at most one non-leaf child.
In this section, we will assume that we are deleting a node with at most one non-leaf child, which we will call its child. In case this node has both leaf children, then let one of them be its child.
While deleting a node, if its color is red, then we can simply replace it with its child, which must be black. All paths through the deleted node will simply pass through one less red node, and both the deleted node’s parent and child must be black, so none of the properties will be violated.
Another simple case is when we delete a black node that has a red child. In this case, property 4 and property 5 could be violated, so to restore them, just repaint the deleted node’s child with black. However, a complex situation arises when both the node to be deleted as well as its child is black. In this case, we begin by replacing the node to be deleted with its child.
Case 1: N is the new node.
In this case, we have removed one black node from every path, and the new root is black, so none of the properties are violated.
Case 2: Sibling S is Red
In this case, interchange the colors of P and S, and then rotate left at P. In the resultant tree, S will become N’s grandparent. The below illustrates Case 2 deletion.
Case 3: P, S, and S’s Children are Black
In this case, simply repaint S with red. In the resultant tree, all the paths passing through S will have one less black node. Therefore, all the paths that pass through P now have one fewer black node than the paths that do not pass through P, so Property 5 is still violated. To fix this problem, we perform the rebalancing procedure on P, starting at Case 1. Case 3 is illustrated below
Case 4: S and S’s Children are Black, but P is Red
In this case, we interchange the colors of S and P. Although this will not affect the number of black nodes on the paths going through S, it will add one black node to the paths going through N making up for the deleted black node on those paths. The below diagram illustrates this case.
Case 5: N is the Left Child of P and S is Black, S’s Left Child is Red, and S’s Right Child is Black
In this case, perform a right rotation at S. After the rotation, S’s left child becomes S’s parent and N’s new sibling. Also, interchange the colors of S and its new parent. Note that now all paths still have an equal number of black nodes, but N has a black sibling whose right child is red, so we fall into Case 6. Refer to the below diagram.
Case 6: S is Black, S’s Right Child is Red, and N is the Left Child of its Parent P
In this case, a left rotation is done at p to make s the parent of P and S’s right child. After the rotation, the colors of P and S are interchanged and S’s right child is colored black. Once these steps are followed, you will observe that property 4 and property 5 remain valid. Case 6 is explained in the below diagram
Implementing the Red Green Tree Algorithm in Python
import sys
class Node():
def __init__(self, item):
self.item = item
self.parent = None #parent node
self.left = None # left node
self.right = None # right node
self.color = 1 #1=red , 0 = black
class RedBlackTree():
def __init__(self):
self.TNULL = Node(0)
self.TNULL.color = 0
self.TNULL.left = None
self.TNULL.right = None
self.root = self.TNULL
# Preorder
def pre_order_helper(self, node):
if node != TNULL:
sys.stdout.write(node.item + " ")
self.pre_order_helper(node.left)
self.pre_order_helper(node.right)
# Balancing the tree after deletion
def delete_fix(self, x):
while x != self.root and x.color == 0:
if x == x.parent.left:
s = x.parent.right
if s.color == 1:
s.color = 0
x.parent.color = 1
self.left_rotate(x.parent)
s = x.parent.right
if s.left.color == 0 and s.right.color == 0:
s.color = 1
x = x.parent
else:
if s.right.color == 0:
s.left.color = 0
s.color = 1
self.right_rotate(s)
s = x.parent.right
s.color = x.parent.color
x.parent.color = 0
s.right.color = 0
self.left_rotate(x.parent)
x = self.root
else:
s = x.parent.left
if s.color == 1:
s.color = 0
x.parent.color = 1
self.right_rotate(x.parent)
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:
s.right.color = 0
s.color = 1
self.left_rotate(s)
s = x.parent.left
s.color = x.parent.color
x.parent.color = 0
s.left.color = 0
self.right_rotate(x.parent)
x = self.root
x.color = 0
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
# Node deletion
def delete_node_helper(self, node, key):
z = self.TNULL
while node != self.TNULL:
if node.item == key:
z = node
if node.item <= key:
node = node.right
else:
node = node.left
if z == self.TNULL:
print("Cannot find key in the tree")
return
y = z
y_original_color = y.color
if z.left == self.TNULL:
x = z.right
self.__rb_transplant(z, z.right)
elif (z.right == self.TNULL):
x = z.left
self.__rb_transplant(z, z.left)
else:
y = self.minimum(z.right)
y_original_color = y.color
x = y.right
if y.parent == z:
x.parent = 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:
self.delete_fix(x)
# Balance the tree after insertion
def fix_insert(self, k):
while k.parent.color == 1:
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self.right_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.left_rotate(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self.left_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.right_rotate(k.parent.parent)
if k == self.root:
break
self.root.color = 0
# Print
def __print_helper(self, node, indent, last):
if node != self.TNULL:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent += " "
else:
sys.stdout.write("L----")
indent += "| "
s_color = "RED" if node.color == 1 else "BLACK"
print(str(node.item) + "(" + s_color + ")")
self.__print_helper(node.left, indent, False)
self.__print_helper(node.right, indent, True)
def preorder(self):
self.pre_order_helper(self.root)
def minimum(self, node):
while node.left != self.TNULL:
node = node.left
return node
def maximum(self, node):
while node.right != self.TNULL:
node = node.right
return node
def successor(self, x):
if x.right != self.TNULL:
return self.minimum(x.right)
y = x.parent
while y != self.TNULL and x == y.right:
x = y
y = y.parent
return y
def predecessor(self, x):
if (x.left != self.TNULL):
return self.maximum(x.left)
y = x.parent
while y != self.TNULL and x == y.left:
x = y
y = y.parent
return y
def left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def right_rotate(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
def insert(self, key):
node = Node(key)
node.parent = None
node.item = key
node.left = self.TNULL
node.right = self.TNULL
node.color = 1
y = None
x = self.root
while x != self.TNULL:
y = x
if node.item < x.item:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.item < y.item:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self.fix_insert(node)
def get_root(self):
return self.root
def delete_node(self, item):
self.delete_node_helper(self.root, item)
def print_tree(self):
self.__print_helper(self.root, "", True)
if __name__ == "__main__":
bst = RedBlackTree()
bst.insert(70)
bst.insert(60)
bst.insert(85)
bst.insert(80)
bst.insert(95)
bst.insert(65)
bst.print_tree()
print("\nAfter deleting an element")
bst.delete_node(80)
bst.print_tree()
Output
Applications of Red-Black Trees
Red-black trees are efficient binary search trees, as they offer a worst-case time guarantee for insertion, deletion, and search operations.
Red-black trees are not only valuable in time-sensitive applications such as real-time applications, but are also preferred to be used as a building block in other data structures which provide a worst-case guarantee, AVL trees also support O(log n) search, insertion, and deletion operations, but they are more rigidly balanced than red-black trees, thereby resulting in slower insertion and removal but faster retrieval of data.
Summary
In this article, we have thoroughly studied the Red-Black Tree, its implementation in python, and its application. Finally, we can draw the conclusion that A red-black tree is a self-balancing binary search tree which is also called a ‘symmetric binary B-tree’. Although a red-black tree is complex, it has good worst-case running time for its operations and is efficient to use, as searching, insertion, and deletion can all be done in O(log n) time.