Red Black Tree Deletion
Written by
Red Black Tree Deletion
The deletion of an element from a tree means the removal of a node from a tree. The process of deleting a node from a Red-black tree is complex than insertion. In the removal of a node, the notion of double black is followed.
Following steps are followed for deleting a node from Red-Black Tree:
- Standard BST removal: in this case, we delete a node that is either a leaf or has only one child. We will consider node to be deleted as L and node that replaces it as C.
- Simple case: Either L or C is red, we color the replaced child as black. Both the L and C nodes cannot be red as two consecutive red nodes are not allowed in a Red-Black Tree.
- If both L & C are black, the child node becomes double black after the removal of a black node.
// Program to show Deletion in red-black tree
#include <iostream>
using namespace std;
struct Node
{
int data;
Node * parent;
Node * left;
Node * right;
int color;
};
typedef Node * NodePtr;
class RedBlackTree
{
private:
NodePtr root;
NodePtr TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent)
{
node - > data = 0;
node - > parent = parent;
node - > left = nullptr;
node - > right = nullptr;
node - > color = 0;
}
void preOrderTraversal(NodePtr node)
{
if (node != TNULL)
{
cout << node - > data << " ";
preOrderTraversal(node - > left);
preOrderTraversal(node - > right);
}
}
void inOrderTraversal(NodePtr node)
{
if (node != TNULL)
{
inOrderTraversal(node - > left);
cout << node - > data << " ";
inOrderTraversal(node - > right);
}
}
void postOrderTraversal(NodePtr node)
{
if (node != TNULL)
{
postOrderTraversal(node - > left);
postOrderTraversal(node - > right);
cout << node - > data << " ";
}
}
NodePtr searchTreeTraversal(NodePtr node, int key)
{
if (node == TNULL || key == node - > data)
{
return node;
}
if (key < node - > data)
{
return searchTreeTraversal(node - > left, key);
}
return searchTreeTraversal(node - > right, key);
}
void deleteFix(NodePtr x)
{
NodePtr s;
while (x != root && x - > color == 0)
{
if (x == x - > parent - > left)
{
s = x - > parent - > right;
if (s - > color == 1)
{
s - > color = 0;
x - > parent - > color = 1;
leftRotate(x - > parent);
s = x - > parent - > right;
}
if (s - > left - > color == 0 && s - > right - > color == 0)
{
s - > color = 1;
x = x - > parent;
} else
{
if (s - > right - > color == 0)
{
s - > left - > color = 0;
s - > color = 1;
rightRotate(s);
s = x - > parent - > right;
}
s - > color = x - > parent - > color;
x - > parent - > color = 0;
s - > right - > color = 0;
leftRotate(x - > parent);
x = root;
}
} else
{
s = x - > parent - > left;
if (s - > color == 1)
{
s - > color = 0;
x - > parent - > color = 1;
rightRotate(x - > parent);
s = x - > parent - > left;
}
if (s - > right - > color == 0 && s - > right - > color == 0)
{
s - > color = 1;
x = x - > parent;
} else
{
if (s - > left - > color == 0)
{
s - > right - > color = 0;
s - > color = 1;
leftRotate(s);
s = x - > parent - > left;
}
s - > color = x - > parent - > color;
x - > parent - > color = 0;
s - > left - > color = 0;
rightRotate(x - > parent);
x = root;
}
}
}
x - > color = 0;
}
void rbTransplant(NodePtr u, NodePtr v)
{
if (u - > parent == nullptr)
{
root = v;
} else if (u == u - > parent - > left)
{
u - > parent - > left = v;
} else
{
u - > parent - > right = v;
}
v - > parent = u - > parent;
}
void deleteNodeHelper(NodePtr node, int key)
{
NodePtr z = TNULL;
NodePtr x, y;
while (node != TNULL)
{
if (node - > data == key)
{
z = node;
}
if (node - > data <= key)
{
node = node - > right;
} else
{
node = node - > left;
}
}
if (z == TNULL)
{
cout << "Key not found in the tree" << endl;
return;
}
y = z;
int y_original_color = y - > color;
if (z - > left == TNULL)
{
x = z - > right;
rbTransplant(z, z - > right);
} else if (z - > right == TNULL)
{
x = z - > left;
rbTransplant(z, z - > left);
} else
{
y = minimum(z - > right);
y_original_color = y - > color;
x = y - > right;
if (y - > parent == z)
{
x - > parent = y;
} else
{
rbTransplant(y, y - > right);
y - > right = z - > right;
y - > right - > parent = y;
}
rbTransplant(z, y);
y - > left = z - > left;
y - > left - > parent = y;
y - > color = z - > color;
}
delete z;
if (y_original_color == 0)
{
deleteFix(x);
}
}
void insertFix(NodePtr k)
{
NodePtr u;
while (k - > parent - > color == 1)
{
if (k - > parent == k - > parent - > parent - > right)
{
u = k - > parent - > parent - > left;
if (u - > color == 1)
{
u - > color = 0;
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
k = k - > parent - > parent;
} else
{
if (k == k - > parent - > left)
{
k = k - > parent;
rightRotate(k);
}
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
leftRotate(k - > parent - > parent);
}
} else
{
u = k - > parent - > parent - > right;
if (u - > color == 1)
{
u - > color = 0;
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
k = k - > parent - > parent;
} else
{
if (k == k - > parent - > right)
{
k = k - > parent;
leftRotate(k);
}
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
rightRotate(k - > parent - > parent);
}
}
if (k == root)
{
break;
}
}
root - > color = 0;
}
void printHelper(NodePtr root, string indent, bool last)
{
if (root != TNULL)
{
cout << indent;
if (last)
{
cout << "R----";
indent += " ";
} else
{
cout << "L----";
indent += "| ";
}
string sColor = root - > color ? "RED" : "BLACK";
cout << root - > data << "(" << sColor << ")" << endl;
printHelper(root - > left, indent, false);
printHelper(root - > right, indent, true);
}
}
public:
RedBlackTree()
{
TNULL = new Node;
TNULL - > color = 0;
TNULL - > left = nullptr;
TNULL - > right = nullptr;
root = TNULL;
}
void preorder()
{
preOrderTraversal(this - > root);
}
void inorder()
{
inOrderTraversal(this - > root);
}
void postorder()
{
postOrderTraversal(this - > root);
}
NodePtr searchTree(int k)
{
return searchTreeTraversal(this - > root, k);
}
NodePtr minimum(NodePtr node)
{
while (node - > left != TNULL)
{
node = node - > left;
}
return node;
}
NodePtr maximum(NodePtr node)
{
while (node - > right != TNULL)
{
node = node - > right;
}
return node;
}
NodePtr successor(NodePtr x)
{
if (x - > right != TNULL)
{
return minimum(x - > right);
}
NodePtr y = x - > parent;
while (y != TNULL && x == y - > right)
{
x = y;
y = y - > parent;
}
return y;
}
NodePtr predecessor(NodePtr x)
{
if (x - > left != TNULL)
{
return maximum(x - > left);
}
NodePtr y = x - > parent;
while (y != TNULL && x == y - > left)
{
x = y;
y = y - > parent;
}
return y;
}
void leftRotate(NodePtr x)
{
NodePtr y = x - > right;
x - > right = y - > left;
if (y - > left != TNULL)
{
y - > left - > parent = x;
}
y - > parent = x - > parent;
if (x - > parent == nullptr)
{
this - > root = y;
} else if (x == x - > parent - > left)
{
x - > parent - > left = y;
} else
{
x - > parent - > right = y;
}
y - > left = x;
x - > parent = y;
}
void rightRotate(NodePtr x)
{
NodePtr y = x - > left;
x - > left = y - > right;
if (y - > right != TNULL)
{
y - > right - > parent = x;
}
y - > parent = x - > parent;
if (x - > parent == nullptr)
{
this - > root = y;
} else if (x == x - > parent - > right)
{
x - > parent - > right = y;
} else
{
x - > parent - > left = y;
}
y - > right = x;
x - > parent = y;
}
void insert(int key)
{
NodePtr node = new Node;
node - > parent = nullptr;
node - > data = key;
node - > left = TNULL;
node - > right = TNULL;
node - > color = 1;
NodePtr y = nullptr;
NodePtr x = this - > root;
while (x != TNULL)
{
y = x;
if (node - > data < x - > data)
{
x = x - > left;
} else
{
x = x - > right;
}
}
node - > parent = y;
if (y == nullptr)
{
root = node;
} else if (node - > data < y - > data)
{
y - > left = node;
} else
{
y - > right = node;
}
if (node - > parent == nullptr)
{
node - > color = 0;
return;
}
if (node - > parent - > parent == nullptr)
{
return;
}
insertFix(node);
}
NodePtr getRoot()
{
return this - > root;
}
void deleteNode(int data)
{
deleteNodeHelper(this - > root, data);
}
void printTree()
{
if (root)
{
printHelper(this - > root, "", true);
}
}
};
int main()
{
RedBlackTree bst;
bst.insert(55);
bst.insert(40);
bst.insert(65);
bst.insert(60);
bst.insert(75);
bst.insert(57);
bst.printTree();
cout << endl
<<
"After deleting" << endl;
bst.deleteNode(40);
bst.printTree();
}
