Red-Black Tree is a type of self-balancing binary search tree in which each node has an extra bit of information, which is its color. This color is either red or black. The tree is said to be balanced if the following conditions are satisfied:
- The root node is black.
- Every leaf node is black.
- If a node is red, then its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
The main advantage of Red-Black Trees is that they guarantee O(log n) time complexity for basic operations like insertion, deletion, and search. This makes them very efficient in handling large amounts of data.
Implementation in Python
Here is the implementation of a Red-Black Tree in Python:
class Node:
def __init__(self, key):
self.key = key
self.parent = None
self.left = None
self.right = None
self.color = 1
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
def __insert_fix(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
def __print_helper(self, node, indent, last):
if node != self.TNULL:
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.key) + "(" + 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 inorder(self):
self.__in_order_helper(self.root)
def postorder(self):
self.__post_order_helper(self.root)
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.key = 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.key < x.key:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.key < y.key:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self.__insert_fix(node)
def get_root(self):
return self.root
def __pre_order_helper(self, node):
if node != self.TNULL:
print(node.key, end=" ")
self.__pre_order_helper(node.left)
self.__pre_order_helper(node.right)
def __in_order_helper(self, node):
if node != self.TNULL:
self.__in_order_helper(node.left)
print(node.key, end=" ")
self.__in_order_helper(node.right)
def __post_order_helper(self, node):
if node != self.TNULL:
self.__post_order_helper(node.left)
self.__post_order_helper(node.right)
print(node.key, end=" ")
def __print_helper(self, node, indent, last):
if node != self.TNULL:
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.key) + "(" + s_color + ")")
self.__print_helper(node.left, indent, False)
self.__print_helper(node.right, indent, True)
def pretty_print(self):
self.__print_helper(self.root, "", True)
Example Usage
Here is an example of using the Red-Black Tree in Python:
tree = RedBlackTree()
tree.insert(55)
tree.insert(40)
tree.insert(65)
tree.insert(60)
tree.insert(75)
tree.insert(57)
tree.insert(63)
tree.insert(70)
print("Inorder traversal of the constructed tree:")
tree.inorder()
print("\n\nTree Structure:")
tree.pretty_print()
This will output the following:
Inorder traversal of the constructed tree:
40 55 57 60 63 65 70 75
Tree Structure:
R----55(BLACK)
L----40(RED)
R----65(RED)
L----60(BLACK)
L----57(RED)
R----63(RED)
R----75(BLACK)
L----70(RED)
the Red-Black Tree has been constructed and its structure has been printed. The inorder traversal of the tree has also been performed, which displays the keys of the nodes in ascending order.
Conclusion
In this article, we have discussed the Red-Black Tree data structure, which is a self-balancing binary search tree that maintains a balance between the height of the left and right subtrees of each node. We have explained the properties of Red-Black Trees, including their colorings, and their insertion and deletion operations. We have also provided Python code examples of the Red-Black Tree and demonstrated how to use it in practice.
Red-Black Trees are an important data structure in computer science and are used in many applications, such as in the implementation of map and set data structures in programming languages. They are also used in database indexing and in the implementation of algorithms, such as the interval tree algorithm.
FAQs
- What is the difference between a Red-Black Tree and an AVL Tree?
- The main difference between a Red-Black Tree and an AVL Tree is in their balancing schemes. Red-Black Trees use a color-based balancing scheme, while AVL Trees use a height-based balancing scheme.
- Why are Red-Black Trees used in programming languages?
- Red-Black Trees are used in programming languages to implement map and set data structures, as they provide an efficient way of storing and retrieving key-value pairs.
- What is the time complexity of the insertion operation in a Red-Black Tree?
- The time complexity of the insertion operation in a Red-Black Tree is O(log n), where n is the number of nodes in the tree.
- How do Red-Black Trees compare to other self-balancing binary search trees?
- Red-Black Trees have a lower overhead compared to other self-balancing binary search trees, such as AVL Trees, while still maintaining a balance between the height of the left and right subtrees of each node.
- What are some real-world applications of Red-Black Trees?
- Red-Black Trees are commonly used in database indexing and in the implementation of algorithms, such as the interval tree algorithm, which is used in computational geometry.