RUN

Red Black Tree Deletion

Written By -

What is Red Black Tree ?

Insertion in Red Black Tree

Deletion in Red Black Tree

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:

1. 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.
2. 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.
3. 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)

{

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();

}

Related Posts:

Tutorials

Examples

Online Compilers

Interview Questions

Recent Articles