Implementing Red-Black Tree Using Python

A Red-Black Tree is a self-balancing binary search tree that maintains balance by ensuring specific properties. It provides efficient search, insertion, and deletion operations in O(log n) time.

Properties of a Red-Black Tree

A Red-Black Tree follows these key properties:

1. Each node is either red or black.
2. The root node is always black.
3. All leaves (NIL nodes) are black.
4. If a node is red, its children must be black (no two consecutive red nodes).
5. Every path from a node to its descendant NIL nodes must have the same number of black nodes.

Implementing a Red-Black Tree in Python

Node Structure

Each node stores a value, left and right child pointers, a color, and a parent pointer.

class Node:
    def __init__(self, data):
        self.data = data
        self.color = "red"  # New nodes are red by default
        self.left = None
        self.right = None
        self.parent = None

Red-Black Tree Class

class RedBlackTree:
    def __init__(self):
        self.NIL = Node(0)  # Sentinel NIL node
        self.NIL.color = "black"
        self.root = self.NIL

Insertion Operation

def insert(self, key):
    new_node = Node(key)
    new_node.left = self.NIL
    new_node.right = self.NIL
    y = None
    x = self.root

    while x != self.NIL:
        y = x
        if new_node.data < x.data:
            x = x.left
        else:
            x = x.right
    new_node.parent = y

    if y is None:
        self.root = new_node
    elif new_node.data < y.data:
        y.left = new_node
    else:
        y.right = new_node

    new_node.color = "red"
    self.fix_insert(new_node)

 

Left Rotation

def left_rotate(self, x):
    y = x.right
    x.right = y.left
    if y.left != self.NIL:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

 

Right Rotation

def right_rotate(self, x):
    y = x.left
    x.left = y.right
    if y.right != self.NIL:
        y.right.parent = x
    y.parent = x.parent
    if x.parent is None:
        self.root = y
    elif x == x.parent.right:
        x.parent.right = y
    else:
        x.parent.left = y
    y.right = x
    x.parent = y

Conclusion

The Red-Black Tree provides efficient insertion, deletion, and search operations while ensuring balance. Understanding its rotations and color adjustments is key to implementing it effectively. With this implementation, you can use Red-Black Trees in applications that require balanced search structures, such as databases and memory management systems.