Red-Black Tree Insertion

---

Inserting nodes into a Red-Black Tree involves specific steps to ensure the tree maintains its balanced structure after each operation. A Red-Black Tree (RBT) is a self-balancing binary search tree, and insertion into it follows a process that ensures the tree properties remain valid. These properties include node colorings and balancing rules, which we need to uphold after adding a new node.

---

What is a Red-Black Tree?

A Red-Black Tree (RBT) is a self-balancing binary search tree where each node contains an extra bit of information for its color. The color can be either red or black. These color properties ensure that the tree remains balanced, providing efficient time complexity for search, insert, and delete operations.

Red-Black Tree Properties

The Red-Black Tree has the following properties that are crucial for maintaining balance:

1. Every node is either red or black.
2. The root is always black.
3. Red nodes cannot have red children (i.e., no two consecutive red nodes are allowed).
4. Every path from a node to its descendant leaf nodes must have the same number of black nodes (black height property).
5. Leaf nodes (null nodes) are always black.

---

Insertion in a Red-Black Tree

The insertion process in a Red-Black Tree is divided into two main parts:

1. Insertion as in a regular binary search tree.
2. Fixing violations of the Red-Black Tree properties.

Insertion Algorithm

The insertion process in a Red-Black Tree follows these key steps:

1. Regular Binary Search Tree Insertion

• Insert the new node as you would in a regular binary search tree (BST), following the BST property:
  • If the new key is smaller than the current node, move left.
  • If the new key is larger, move right.
• Insert the new node as a red node.

2. Fixing Red-Black Tree Violations

• After insertion, the tree may violate some of the Red-Black properties. Specifically, the parent of the newly inserted red node might also be red, which violates the Red Node Property (no two consecutive red nodes).
• To restore the Red-Black Tree properties, color flips and rotations are used.

Fixing Violations with Cases

When a violation occurs after insertion, there are several cases to handle:

• Case 1: The parent node is black (no violation).
• Case 2: The parent node is red, and the uncle node is also red. In this case, both parent and uncle are turned black, and the grandparent is turned red. This may propagate upwards if the grandparent becomes red.
• Case 3: The parent is red, and the uncle is black or null. In this case, rotations are required:
  • If the new node is inserted as the right child of the left child of the grandparent (or vice versa), a rotation is needed.
  • If the new node is inserted as the left child of the left child of the grandparent (or the right child of the right child), a single rotation or double rotation is performed to balance the tree.

---

Python Code for Red-Black Tree Insertion

Below is a Python code implementation that demonstrates insertion into a Red-Black Tree:

class Node:
    def __init__(self, data):
        self.data = data
        self.color = "RED"  # New nodes are 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.

---

---