## Algorithm

In a Red-Black Tree, deletion is a complex operation that must maintain the properties of the tree while removing a specific node. Red-Black Trees are binary search trees with additional properties to ensure balance, and these properties must be preserved after the deletion operation.

Here is an overview of the steps involved in deleting a node from a Red-Black Tree:

1. Search for the Node to Delete:

• Perform a standard binary search to locate the node to be deleted.
2. Perform Standard BST Delete:

• If the node to be deleted has zero or one child, perform the standard binary search tree delete operation. If the node has two children, find its in-order successor (or predecessor), replace the node's value with the in-order successor (or predecessor), and then delete the in-order successor (or predecessor).

• After the standard BST delete, the Red-Black Tree properties may be violated. To restore these properties, additional adjustments are required.
4. Case 1: Double Black Propagation:

• When a black node is deleted from the tree, it can result in a "double black" situation where the black height is violated. This situation is propagated up the tree until it is resolved.
5. Cases 2-6: Restructuring and Recoloring:

• Based on the properties of Red-Black Trees, there are several cases that need to be handled to maintain balance. These cases involve rotations and recoloring of nodes to ensure that the Red-Black properties are not violated.

• Case 2: Sibling is red.

• Case 3: Parent, sibling, and sibling's children are black.

• Case 4: Sibling and sibling's children are black, but the parent is red.

• Case 5: Sibling is black, and the closer nephew is red.

• Case 6: Sibling is black, and the farther nephew is red.

6. Update Root:

• After all adjustments, make sure that the root of the tree is black.

These steps ensure that after the deletion, the Red-Black Tree properties are maintained. The double-black cases involve restructuring the tree through rotations and recoloring to restore balance.

## Code Examples

### #1 Deletion From a Red-Black Tree implement in Python

```Code - Python Programming```

``````class Node:
def __init__(self, key, color='RED'):
self.key = key
self.left = None
self.right = None
self.parent = None
self.color = color

class RedBlackTree:
def __init__(self):
self.NIL = Node(None, color='BLACK')  # Sentinel node
self.root = self.NIL

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

def right_rotate(self, y):
x = y.left
y.left = x.right

if x.right != self.NIL:
x.right.parent = y

x.parent = y.parent

if y.parent is None:
self.root = x
elif y == y.parent.left:
y.parent.left = x
else:
y.parent.right = x

x.right = y
y.parent = x

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

v.parent = u.parent

def delete_node(self, key):
z = self.search(self.root, key)
if z is None:
return

y = z
y_original_color = y.color
if z.left == self.NIL:
x = z.right
self.transplant(z, z.right)
elif z.right == self.NIL:
x = z.left
self.transplant(z, z.left)
else:
y = self.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.delete_fixup(x)

def delete_fixup(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 minimum(self, node):
while node.left != self.NIL:
node = node.left
return node

def search(self, node, key):
if node is None or node.key == key:
return node

if key < node.key:
return self.search(node.left, key)
return self.search(node.right, key)

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

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

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

if new_node.parent is None:
new_node.color = 'BLACK'
return
if new_node.parent.parent is None:
return

self.insert_fixup(new_node)

def insert_fixup(self, node):
while node.parent.color == 'RED':
if node.parent == node.parent.parent.right:
y = node.parent.parent.left
if y.color == 'RED':
node.parent.color = 'BLACK'
y.color = 'BLACK'
node.parent.parent.color = 'RED'
node = node.parent.parent
else:
if node == node.parent.left:
node = node.parent
self.right_rotate(node)
node.parent.color = 'BLACK'
node.parent.parent.color = 'RED'
self.left_rotate(node.parent.parent)
else:
y = node.parent.parent.right
if y.color == 'RED':
node.parent.color = 'BLACK'
y.color = 'BLACK'
node.parent.parent.color = 'RED'
node = node.parent.parent
else:
if node == node.parent.right:
node = node.parent
self.left_rotate(node)
node.parent.color = 'BLACK'
node.parent.parent.color = 'RED'
self.right_rotate(node.parent.parent)

if node == self.root:
break

self.root.color = 'BLACK'

def inorder_traversal(self, node):
if node != self.NIL:
self.inorder_traversal(node.left)
print(node.key, end=" ")
self.inorder_traversal(node.right)

def display(self):
print("Inorder Traversal:")
self.inorder_traversal(self.root)
print()

# Example usage:
rb_tree = RedBlackTree()

keys = [3, 1, 5, 0, 2, 4, 6]
for key in keys:
rb_tree.insert(key)

print("Original Red-Black Tree:")
rb_tree.display()

key_to_delete =
``````
Copy The Code &

### #2 Deletion From a Red-Black Tree implement in Java

```Code - Java Programming```

``````// Node class for Red-Black Tree
class Node {
int data;
Node parent;
Node left;
Node right;
int color; // 0 for black, 1 for red

public Node(int data) {
this.data = data;
this.color = 1; // new nodes are always red
}
}

public class RedBlackTree {
private Node root;
private Node TNULL;

// Preorder
// In-order
// Postorder

// Other methods...

// Search for a node with the given key
private Node searchTree(int key) {
return searchTreeRecursive(root, key);
}

private Node searchTreeRecursive(Node node, int key) {
if (node == TNULL || key == node.data) {
return node;
}

if (key  <  node.data) {
return searchTreeRecursive(node.left, key);
}

return searchTreeRecursive(node.right, key);
}

// Delete a node with the given key
public void delete(int key) {
deleteNode(searchTree(key));
}

// Helper method for deleting a node
private void deleteNode(Node node) {
Node y = node;
Node x;
int yOriginalColor = y.color;

if (node.left == TNULL) {
x = node.right;
transplant(node, node.right);
} else if (node.right == TNULL) {
x = node.left;
transplant(node, node.left);
} else {
y = minimum(node.right);
yOriginalColor = y.color;
x = y.right;

if (y.parent == node) {
x.parent = y;
} else {
transplant(y, y.right);
y.right = node.right;
y.right.parent = y;
}

transplant(node, y);
y.left = node.left;
y.left.parent = y;
y.color = node.color;
}

if (yOriginalColor == 0) {
deleteFixup(x);
}
}

// Helper method for fixing the tree after deletion
private void deleteFixup(Node x) {
while (x != root && x.color == 0) {
if (x == x.parent.left) {
Node w = x.parent.right;
if (w.color == 1) {
w.color = 0;
x.parent.color = 1;
leftRotate(x.parent);
w = x.parent.right;
}

if (w.left.color == 0 && w.right.color == 0) {
w.color = 1;
x = x.parent;
} else {
if (w.right.color == 0) {
w.left.color = 0;
w.color = 1;
rightRotate(w);
w = x.parent.right;
}

w.color = x.parent.color;
x.parent.color = 0;
w.right.color = 0;
leftRotate(x.parent);
x = root;
}
} else {
Node w = x.parent.left;
if (w.color == 1) {
w.color = 0;
x.parent.color = 1;
rightRotate(x.parent);
w = x.parent.left;
}

if (w.right.color == 0 && w.right.color == 0) {
w.color = 1;
x = x.parent;
} else {
if (w.left.color == 0) {
w.right.color = 0;
w.color = 1;
leftRotate(w);
w = x.parent.left;
}

w.color = x.parent.color;
x.parent.color = 0;
w.left.color = 0;
rightRotate(x.parent);
x = root;
}
}
}

x.color = 0;
}

// Helper method to transplant a subtree
private void transplant(Node u, Node v) {
if (u.parent == null) {
root = v;
} else if (u == u.parent.left) {
u.parent.left = v;
} else {
u.parent.right = v;
}

v.parent = u.parent;
}

// Helper method to perform a left rotation
private void leftRotate(Node x) {
Node y = x.right;
x.right = y.left;

if (y.left != TNULL) {
y.left.parent = x;
}

y.parent = x.parent;

if (x.parent == null) {
root = y;
} else if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}

y.left = x;
x.parent = y;
}

// Helper method to perform a right rotation
private void rightRotate(Node x) {
Node y = x.left;
x.left = y.right;

if (y.right != TNULL) {
y.right.parent = x;
}

y.parent = x.parent;

if (x.parent == null) {
root = y;
} else if (x == x.parent.right) {
x.parent.right = y;
} else {
x.parent.left = y;
}

y.right = x;
x.parent = y;
}

// Helper method to find the minimum value node in a subtree
private Node minimum(Node node) {
while (node.left != TNULL) {
node = node.left;
}
return node;
}
}
``````
Copy The Code &

### #3 Deletion From a Red-Black Tree implement in C

```Code - C Programming```

``````#include <stdio.h>
#include <stdlib.h>

// Node structure for the Red-Black Tree
typedef struct Node {
int data;
char color; // 'R' for red, 'B' for black
struct Node* parent;
struct Node* left;
struct Node* right;
} Node;

// Helper function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->color = 'R'; // New nodes are always red
newNode->parent = NULL;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Helper function to perform left rotation
void leftRotate(Node** root, Node* x) {
Node* y = x->right;
x->right = y->left;

if (y->left != NULL)
y->left->parent = x;

y->parent = x->parent;

if (x->parent == NULL)
*root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;

y->left = x;
x->parent = y;
}

// Helper function to perform right rotation
void rightRotate(Node** root, Node* y) {
Node* x = y->left;
y->left = x->right;

if (x->right != NULL)
x->right->parent = y;

x->parent = y->parent;

if (y->parent == NULL)
*root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;

x->right = y;
y->parent = x;
}

// Helper function to fix the tree after deletion
void deleteFixup(Node** root, Node* x) {
while (x != *root && (x == NULL || x->color == 'B')) {
if (x == x->parent->left) {
Node* w = x->parent->right;
if (w->color == 'R') {
w->color = 'B';
x->parent->color = 'R';
leftRotate(root, x->parent);
w = x->parent->right;
}
if ((w->left == NULL || w->left->color == 'B') &&
(w->right == NULL || w->right->color == 'B')) {
w->color = 'R';
x = x->parent;
} else {
if (w->right == NULL || w->right->color == 'B') {
if (w->left != NULL)
w->left->color = 'B';
w->color = 'R';
rightRotate(root, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = 'B';
if (w->right != NULL)
w->right->color = 'B';
leftRotate(root, x->parent);
x = *root; // Exit the loop
}
} else {
Node* w = x->parent->left;
if (w->color == 'R') {
w->color = 'B';
x->parent->color = 'R';
rightRotate(root, x->parent);
w = x->parent->left;
}
if ((w->right == NULL || w->right->color == 'B') &&
(w->left == NULL || w->left->color == 'B')) {
w->color = 'R';
x = x->parent;
} else {
if (w->left == NULL || w->left->color == 'B') {
if (w->right != NULL)
w->right->color = 'B';
w->color = 'R';
leftRotate(root, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = 'B';
if (w->left != NULL)
w->left->color = 'B';
rightRotate(root, x->parent);
x = *root; // Exit the loop
}
}
}
if (x != NULL)
x->color = 'B';
}

// Helper function to find the minimum value node in a tree
Node* findMin(Node* root) {
while (root != NULL && root->left != NULL)
root = root->left;
return root;
}

// Helper function to replace a node with another node
void transplant(Node** root, Node* u, Node* v) {
if (u->parent == NULL)
*root = v;
else if (u == u->parent->left)
u->parent->left = v;
else
u->parent->right = v;
if (v != NULL)
v->parent = u->parent;
}

// Helper function to delete a node from the tree
void deleteNode(Node** root, int key) {
Node* z = *root;
while (z != NULL) {
if (key == z->data)
break;
if (key  <  z->data)
z = z->left;
else
z = z->right;
}
if (z == NULL)

Node* y = z;
char yOriginalColor = y->color;
Node* x;

if (z->left == NULL) {
x = z->right;
transplant(root, z, z->right);
} else if (z->right == NULL) {
x = z->left;
transplant(root, z, z->left);
} else {
y = findMin(z->right);
yOriginalColor = y->color;
x = y->right;
if (y->parent == z)
x->parent = y;
else {
transplant(root, y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(root, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}

free(z);

if (yOriginalColor == 'B')
deleteFixup(root, x);
}

// Function to print the tree (in-order traversal)
void printTree(Node* root) {
if (root != NULL) {
printTree(root->left);
printf("(%d, %c) ", root->data, root->color);
printTree(root->right
``````
Copy The Code &

### #4 Deletion From a Red-Black Tree implement in C++

```Code - C++ Programming```

``````#include <iostream>

enum Color { RED, BLACK };

struct Node {
int data;
Color color;
Node* parent;
Node* left;
Node* right;

// Constructor
Node(int val) : data(val), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};

class RedBlackTree {
private:
Node* root;

// Other private helper methods

public:
// Constructor
RedBlackTree() : root(nullptr) {}

// Other public methods

// Delete a node with a given value
void deleteNode(int key);

private:
// Private helper methods for deletion
void deleteNodeHelper(Node* node, int key);
void fixDoubleBlack(Node* node);
Node* findMin(Node* node);
Node* findMax(Node* node);
void deleteNodeCases(Node* node);
void rotateLeft(Node* node);
void rotateRight(Node* node);
};

void RedBlackTree::deleteNode(int key) {
if (root == nullptr) {
std::cout << "Tree is empty!" << std::endl;
return;
}

deleteNodeHelper(root, key);
}

void RedBlackTree::deleteNodeHelper(Node* node, int key) {
// Search for the node to delete
// Implement your search logic here

// Delete the node (if found)
// Implement your deletion logic here

// Fix the double-black violation
fixDoubleBlack(node);
}

void RedBlackTree::fixDoubleBlack(Node* node) {
// Implement your fixDoubleBlack logic here
}

Node* RedBlackTree::findMin(Node* node) {
// Implement your findMin logic here
return nullptr;
}

Node* RedBlackTree::findMax(Node* node) {
// Implement your findMax logic here
return nullptr;
}

void RedBlackTree::deleteNodeCases(Node* node) {
// Implement your deleteNodeCases logic here
}

void RedBlackTree::rotateLeft(Node* node) {
// Implement your rotateLeft logic here
}

void RedBlackTree::rotateRight(Node* node) {
// Implement your rotateRight logic here
}
``````
Copy The Code &