Red-Black Tree

---

A Red-Black Tree is a type of self-balancing binary search tree with an additional constraint that helps maintain balance during insertion and deletion operations. It ensures that the tree remains balanced by enforcing specific rules on the colors of nodes. These constraints help guarantee that the tree remains approximately balanced, leading to efficient search, insertion, and deletion operations.

In this blog post, we will cover the fundamental properties, operations, and the insertion process of a Red-Black Tree. We will also provide a Python code implementation for insertion into a Red-Black Tree to help you understand the mechanics.

---

What is a Red-Black Tree?

A Red-Black Tree (RBT) is a binary search tree where each node has an extra bit of storage for its color, which can either be red or black. It is self-balancing and guarantees that the tree remains balanced after insertions and deletions, thus maintaining an efficient time complexity for operations like searching, insertion, and deletion.

Red-Black Tree Properties

A Red-Black Tree follows five key properties:

1. Node Colors:

   • Each node is either red or black.

2. Root Property:

   • The root node is always black.

3. Red Node Property:

   • Red nodes cannot have red children. This means that no two consecutive red nodes are allowed along any path from the root to the leaves.

4. Black Height Property:

   • Every path from a node to its descendant null pointer must have the same number of black nodes. This is known as the black height.

5. Leaf Nodes:

   • Every leaf node (null node) is considered black.

Why Use Red-Black Trees?

The main advantage of Red-Black Trees over regular binary search trees is that they are guaranteed to be approximately balanced, ensuring that the operations of searching, inserting, and deleting have a worst-case time complexity of O(log n).

---

Operations on a Red-Black Tree

1. Insertion

Insertion in a Red-Black Tree involves placing a new node in the tree, just like in a regular binary search tree, but with additional operations to maintain the Red-Black Tree properties.

Steps for insertion:

• Insert the node as in a regular binary search tree.
• Color the node red.
• Fix violations of the Red-Black properties using rotations and color flips.

2. Deletion

Deletion in a Red-Black Tree is more complex because it involves fixing the tree to maintain its properties. After removing the node, the tree might violate the Red-Black properties, so we use various cases of rotations and color flips to restore balance.

---

Red-Black Tree Insertion Algorithm

Insertion in a Red-Black Tree involves the following steps:

1. Insert the new node as a red node at the appropriate position, following the binary search tree insertion rules.
2. Fix any Red-Black Tree violations by performing color flips and rotations to restore balance.

Insertion Cases

There are several cases to handle after insertion:

• Case 1: The parent node is black (no violation).
• Case 2: The parent node is red, and the uncle node is also red (color flip is needed).
• Case 3: The parent is red and the uncle is black or null (rotation is needed to balance).

---

Python Code Example: Insertion into a Red-Black Tree

Below is a Python implementation of insertion in a Red-Black Tree. This code demonstrates how to insert a node while maintaining the Red-Black Tree properties using rotations and color flips.

class Node:
    def __init__(self, data):
        self.data = data
        self.color = "RED"  # New nodes are always inserted as red
        self.left = None
        self.right = None
        self.parent = None


class RedBlackTree:
    def __init__(self):
        self.TNULL = Node(0)  # Sentinel node for leaves
        self.TNULL.color = "BLACK"
        self.root = self.TNULL

    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 == self.TNULL:
            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 == self.TNULL:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def fix_insert(self, k):
        while k.parent.color == "RED":
            if k.parent == k.parent.parent.left:
                u = k.parent.parent.right
                if u.color == "RED":
                    u.color = "BLACK"
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    self.right_rotate(k.parent.parent)
            else:
                u = k.parent.parent.left
                if u.color == "RED":
                    u.color = "BLACK"
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    self.left_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = "BLACK"

    def insert(self, key):
        node = Node(key)
        node.parent = None
        node.data = key
        node.left = self.TNULL
        node.right = self.TNULL
        node.color = "RED"

        y = None
        x = self.root

        while x != self.TNULL:
            y = x
            if node.data < x.data:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if y == None:
            self.root = node
        elif node.data < y.data:
            y.left = node
        else:
            y.right = node

        if node.parent == None:
            node.color = "BLACK"
            return

        if node.parent.parent == None:
            return

        self.fix_insert(node)

    def inorder(self, root):
        if root != self.TNULL:
            self.inorder(root.left)
            print(root.data, end=" ")
            self.inorder(root.right)

# Example Usage
rb_tree = RedBlackTree()

# Insert keys into the Red-Black Tree
keys = [20, 15, 25, 10, 5, 1]
for key in keys:
    rb_tree.insert(key)

# In-order traversal of the Red-Black Tree
print("In-order Traversal of Red-Black Tree:")
rb_tree.inorder(rb_tree.root)

---

Explanation of the Code

1. Node Class:

   • Each node has a data field, a color field (either "RED" or "BLACK"), and pointers to its left child, right child, and parent.
   • A sentinel node TNULL is used to represent leaves and simplifies boundary cases.

2. RedBlackTree Class:

   • This class manages the Red-Black Tree operations, including insertion, left rotation, right rotation, and fixing insertions.
   • Left and Right Rotations: Used to maintain the Red-Black Tree properties when a violation occurs during insertion.
   • fix_insert(): The method that fixes violations of the Red-Black properties after an insertion, using rotations and color flips as needed.

3. insert():

   • This method inserts a new node into the tree and calls fix_insert() to restore the Red-Black properties.
   • Initially, the inserted node is colored red, and the tree is adjusted to ensure it remains balanced.

4. inorder():

   • This is a standard in-order traversal that prints the keys of the tree in ascending order.

---

---