Deletion from a Red-Black Tree

---

Deleting a node from a Red-Black Tree (RBT) is more complex than insertion because it requires maintaining the tree's balancing properties. Just like insertion, deletion might violate one or more of the Red-Black Tree properties, such as the black height or the red node property. These violations must be fixed using rotations and color changes to restore the tree's balance.

---

What is a Red-Black Tree?

A Red-Black Tree (RBT) is a self-balancing binary search tree where each node is colored either red or black. These color properties help maintain balance, ensuring that operations such as insertion, deletion, and searching have a time complexity of O(log n).

Red-Black Tree Properties

A Red-Black Tree satisfies the following properties:

1. Every node is either red or black.
2. The root is always black.
3. Red nodes cannot have red children (no two consecutive red nodes).
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.

---

Deletion in a Red-Black Tree

The process of deleting a node from a Red-Black Tree involves the following steps:

1. Standard BST Deletion:
   • First, delete the node in the usual manner as you would in a regular binary search tree (BST).
2. Fixing Violations:
   • After deletion, the tree may violate some of the Red-Black Tree properties, especially the black height property. These violations must be fixed using rotations and color flips.

Deletion Algorithm

Here are the steps to delete a node from a Red-Black Tree:

1. Find the Node to Delete

• The node to be deleted is found using standard binary search tree rules.

2. Delete the Node

• If the node to be deleted has two children, find its in-order successor (or in some cases, its in-order predecessor), copy its value to the node to be deleted, and then delete the successor (which will have at most one child).
• If the node to be deleted has one child or no children, we can simply remove the node and replace it with its child (if any).

3. Fix Violations

• Deleting a node might cause double black violations (i.e., having an extra black node on a path). This must be corrected by a series of cases that use rotations and color flips.

Fixing Double Black Violations

When a node is deleted, it might cause one of the following cases:

• Case 1: If the sibling is red, perform a rotation to make the sibling black and the parent red.
• Case 2: If the sibling is black and its children are either both black or at least one is black, we perform a series of rotations and color flips to restore the Red-Black Tree properties.

These cases continue recursively until the tree is balanced again.

---

Python Code for Deletion in a Red-Black Tree

Below is a Python implementation that demonstrates deletion in a Red-Black Tree. This code will show how to handle various cases of deletions and fix the tree's balance after the removal of a node.

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_delete(self, x):
        while x != self.root and x.color == "BLACK":
            if x == x.parent.left:
                w = x.parent.right
                if w.color == "RED":
                    w.color = "BLACK"
                    x.parent.color = "RED"
                    self.left_rotate(x.parent)
                    w = x.parent.right

                if w.left.color == "BLACK" and w.right.color == "BLACK":
                    w.color = "RED"
                    x = x.parent
                else:
                    if w.right.color == "BLACK":
                        w.left.color = "BLACK"
                        w.color = "RED"
                        self.right_rotate(w)
                        w = x.parent.right

                    w.color = x.parent.color
                    x.parent.color = "BLACK"
                    w.right.color = "BLACK"
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                w = x.parent.left
                if w.color == "RED":
                    w.color = "BLACK"
                    x.parent.color = "RED"
                    self.right_rotate(x.parent)
                    w = x.parent.left

                if w.right.color == "BLACK" and w.left.color == "BLACK":
                    w.color = "RED"
                    x = x.parent
                else:
                    if w.left.color == "BLACK":
                        w.right.color = "BLACK"
                        w.color = "RED"
                        self.left_rotate(w)
                        w = x.parent.left

                    w.color = x.parent.color
                    x.parent.color = "BLACK"
                    w.left.color = "BLACK"
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = "BLACK"

    def delete(self, node, key):
        z = self.TNULL
        while node != self.TNULL:
            if node.data == key:
                z = node

            if node.data <= key:
                node = node.right
            else:
                node = node.left

        if z == self.TNULL:
            print("Node not found in the tree")
            return

        y = z
        y_original_color = y.color
        if z.left == self.TNULL:
            x = z.right
            self.transplant(z, z.right)
        elif z.right == self.TNULL:
            x = z.left
            self.transplant(z, z.left)
        else:
            y = self.tree_minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = y
            else:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y

            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y
            y.color = z.color

        if y_original_color == "BLACK":
            self.fix_delete(x)

    def transplant(self, u, v):
        if u.parent == self.TNULL:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent

    def tree_minimum(self, node):
        while node.left != self.TNULL:
            node = node.left
        return 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 before deletion
print("In-order Traversal of Red-Black Tree before deletion:")
rb_tree.inorder(rb_tree.root)

# Delete node with key 10
rb_tree.delete(rb_tree.root, 10)

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

---

Explanation of the Code

1. Node Class:

   • The Node class contains data, color, left, right, and parent attributes. It represents a node in the Red-Black Tree.

2. RedBlackTree Class:

   • The class manages operations like insert, delete, and fix_delete.
   • fix_delete: This function restores the Red-Black Tree properties after a deletion. It handles various cases like double black violations using rotations and color flips.

3. delete:

   • This method deletes a node from the tree following the Red-Black Tree deletion algorithm.
   • After deletion, it calls fix_delete to fix any violations caused by the removal of the node.

4. transplant:

   • This helper function replaces one subtree with another during the deletion process.

5. inorder:

   • Standard in-order traversal that prints the keys of the tree in ascending order.

---

---