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:
-
Search for the Node to Delete:
- Perform a standard binary search to locate the node to be deleted.
-
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).
-
Adjust Colors and Balance:
- After the standard BST delete, the Red-Black Tree properties may be violated. To restore these properties, additional adjustments are required.
-
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.
-
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.
-
-
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:
print(f"Node with key {key} not found.")
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 =
#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;
}
}
#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)
return; // Node with key not found
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
#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
}
Demonstration
Deletion From a Red-Black Tree-DevsEnv