# Red Black tree node deletion

In the world of data structures, Red-Black Trees offer a balanced and efficient way to manage dynamic datasets. This article delves into the intricate process of deleting nodes from a Red-Black Tree. With detailed explanations, step-by-step algorithms, and illustrative code, we'll explore how to maintain the balance and properties of the tree during deletion.

## Problem Statement and Description

The challenge is to implement the node deletion operation for a Red-Black Tree while preserving its properties. Deleting nodes requires handling various cases, including replacing deleted nodes, restructuring the tree, and recoloring nodes.

## Example

We'll work with the following Red-Black Tree as our example:

``````       9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40``````

We'll perform deletions while ensuring the Red-Black Tree properties are maintained.

For example delete node 1:

``````
9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
``````

## Idea to Solve

To delete a node from a Red-Black Tree, we'll follow these key steps:

1. Identify the node to be deleted.
2. If the node has two children, replace it with its inorder successor (a node with the smallest key in its right subtree).
3. Determine the color of the replacement node.
4. Delete the node and address any violations of the Red-Black Tree properties using deletion cases.

## Pseudocode

``````struct TreeNode:
TreeNode left, right, parent
int key
enum Color color

struct RBTree:
TreeNode root

deleteNode(tree, key):
n = findNode(tree.root, key)
if n is NULL:
return
child = NULL
if n.left is NULL or n.right is NULL:
child = n.left or n.right
if n.left is not NULL and n.right is not NULL:
child = inorderSuccessor(n.left)
n.key = child.key
n = child
if nodeColor(n) == BLACK:
n.color = nodeColor(child)
deleteCase1(tree, n)
replaceNode(tree, n, child)
verifyProperties(tree.root)

deleteCase1(tree, n):
if n.parent is NULL:
return
deleteCase2(tree, n)

deleteCase2(tree, n):
s = sibling(n)
if nodeColor(s) == RED:
n.parent.color = RED
s.color = BLACK
if n is n.parent.left:
rotateLeft(tree, n.parent)
else:
rotateRight(tree, n.parent)
deleteCase3(tree, n)

deleteCase3(tree, n):
s = sibling(n)
if nodeColor(n.parent) == BLACK and nodeColor(s) == BLACK and \
nodeColor(s.left) == BLACK and nodeColor(s.right) == BLACK:
s.color = RED
deleteCase1(tree, n)
else:
deleteCase4(tree, n)

deleteCase4(tree, n):
s = sibling(n)
if nodeColor(n.parent) == RED and nodeColor(s) == BLACK and \
nodeColor(s.left) == BLACK and nodeColor(s.right) == BLACK:
s.color = RED
n.parent.color = BLACK
else:
deleteCase5(tree, n)

deleteCase5(tree, n):
s = sibling(n)
if n is n.parent.left and nodeColor(s) == BLACK and \
nodeColor(s.left) == RED and nodeColor(s.right) == BLACK:
s.color = RED
s.left.color = BLACK
rotateRight(tree, s)
else if n is n.parent.right and nodeColor(s) == BLACK and \
nodeColor(s.right) == RED and nodeColor(s.left) == BLACK:
s.color = RED
s.right.color = BLACK
rotateLeft(tree, s)
deleteCase6(tree, n)

deleteCase6(tree, n):
s = sibling(n)
s.color = nodeColor(n.parent)
n.parent.color = BLACK
if n is n.parent.left:
s.right.color = BLACK
rotateLeft(tree, n.parent)
else:
s.left.color = BLACK
rotateRight(tree, n.parent)``````

## Algorithm Explanation

• The algorithm leverages the standard Red-Black Tree insertion approach and modifies it for node deletion.
• The `deleteNode` function identifies the node to be deleted and proceeds with the deletion process, maintaining properties.
• The `deleteCase1` function handles the initial case when the node to be deleted is the root.
• The subsequent `deleteCase` functions address various cases of tree restructuring and recoloring to ensure property preservation.

## Code Solution

``````// Include header file
#include <stdio.h>
#include <stdlib.h>
/*
C program for
Red Black tree node deletion
*/
enum Color
{
RED , BLACK
};
struct TreeNode
{
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode *parent;
int key;
enum Color  color;
};
struct RBTree
{
struct TreeNode *root;

};

void deleteCase1(struct RBTree *,struct TreeNode *);
void insertCase1(struct RBTree *,struct TreeNode *);
struct TreeNode* newNode(int key,enum Color nodeColor)
{
struct TreeNode*node = (struct TreeNode*)malloc(sizeof(struct TreeNode));

if(node!=NULL)
{
node->key = key;
node->color = nodeColor;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
}
return node;
}

struct RBTree* newTree()
{
struct RBTree*tree = (struct RBTree*)malloc(sizeof(struct RBTree));

if(tree!=NULL)
{
tree->root = NULL;

}
return tree;
}
struct TreeNode *sibling(struct TreeNode *node)
{
if (node->parent == NULL)
{
//  Fail case
printf("Fail Subling has no parent\n");
return NULL;
}
else
{
if (node == node->parent->left)
{
return node->parent->right;
}
else
{
return node->parent->left;
}
}
}

struct TreeNode *uncle(struct TreeNode *node)
{
if (node->parent == NULL)
{
//  Fail case
printf("Fail Uncle has no parent\n");
return NULL;
}
else if (node->parent->parent == NULL)
{
//  Fail case
printf("Fail Children of root have no uncle\n");
return NULL;
}
return sibling(node->parent);
}

struct TreeNode *grandparent(struct TreeNode *node)
{
if (node->parent == NULL || node->parent->parent == NULL)
{
//  Fail case
printf("Fail Grandparent has no parent\n");
return NULL;
}
return node->parent->parent;
}
enum Color nodeColor(struct TreeNode *n)
{
if (n == NULL)
{
return BLACK;
}
else
{
return n->color;
}
}
int verifyProperty5Helper(struct TreeNode *n, int blackCount, int pathBlackCount)
{
if (nodeColor(n) == BLACK)
{
blackCount++;
}
if (n == NULL)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
//  Fail case
printf("Fail Property of verifyProperty5Helper\n");
}
return pathBlackCount;
}
pathBlackCount = verifyProperty5Helper(n->left, blackCount, pathBlackCount);
pathBlackCount = verifyProperty5Helper(n->right, blackCount, pathBlackCount);
return pathBlackCount;
}
void verifyProperty5(struct TreeNode *root)
{
verifyProperty5Helper(root, 0, -1);
}
void verifyProperty4(struct TreeNode *n)
{
if (nodeColor(n) == RED)
{
if (nodeColor(n->left) != BLACK
|| nodeColor(n->right) != BLACK
|| nodeColor(n->parent) != BLACK)
{
//  Fail case
printf("Fail Property of verifyProperty4\n");
}
}
if (n == NULL)
{
return;
}
verifyProperty4(n->left);
verifyProperty4(n->right);
}
void verifyProperty2(struct TreeNode *n)
{
if (nodeColor(n) != BLACK)
{
//  Fail case
printf(" Fail case verifyProperty2 \n");
}
}
void verifyProperty1(struct TreeNode *n)
{
if (!(nodeColor(n) == RED || nodeColor(n) == BLACK))
{
//  Fail case
printf(" Fail case verifyProperty1 \n");
return;
}
if (n == NULL)
{
return;
}
verifyProperty1(n->left);
verifyProperty1(n->right);
}
void verifyProperties(struct TreeNode *node)
{
verifyProperty1(node);
verifyProperty2(node);
verifyProperty4(node);
verifyProperty5(node);
}

struct  TreeNode *findNode(struct TreeNode *root,int key)
{
struct  TreeNode *n = root;

while (n != NULL)
{
if (key == n->key)
{
return n;
}
else if (key < n->key)
{
n = n->left;
}
else
{
n = n->right;
}
}
return n;
}

void replaceNode(struct RBTree *tree,struct TreeNode *oldn, struct TreeNode *newn)
{
if (oldn->parent == NULL)
{
tree->root = newn;
if (tree->root != NULL)
{
tree->root->color = BLACK;
}
}
else
{
if (oldn == oldn->parent->left)
{
oldn->parent->left = newn;
}
else
{
oldn->parent->right = newn;
}
}
if (newn != NULL)
{
newn->parent = oldn->parent;
}
}
struct TreeNode *inorderSuccessor(struct TreeNode *n)
{
if (n == NULL)
{
//  Fail case
printf("\n Fail Inorder Successor is NULL\n");
return NULL;
}
while (n->right != NULL)
{
n = n->right;
}
return n;
}

void rotateLeft(struct RBTree *tree,struct TreeNode *n)
{
struct TreeNode *r = n->right;
replaceNode(tree, n, r);
n->right = r->left;
if (r->left != NULL)
{
r->left->parent = n;
}
r->left = n;
n->parent = r;
}
void rotateRight(struct RBTree *tree,struct TreeNode *n)
{
struct TreeNode *l = n->left;
replaceNode(tree,n, l);
n->left = l->right;
if (l->right != NULL)
{
l->right->parent = n;
}
l->right = n;
n->parent = l;
}
void insertCase5(struct RBTree *tree,struct TreeNode *n)
{
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left)
{
rotateRight(tree,grandparent(n));
}
else
{
if (n == n->parent->right && n->parent == grandparent(n)->right)
{
rotateLeft(tree,grandparent(n));
}
else
{
//  Fail case
printf("\n Fail insertCase5 \n");
}
}
}
void insertCase4(struct RBTree *tree,struct TreeNode *n)
{
if (n == n->parent->right && n->parent == grandparent(n)->left)
{
rotateLeft(tree,n->parent);
n = n->left;
}
else if (n == n->parent->left && n->parent == grandparent(n)->right)
{
rotateRight(tree,n->parent);
n = n->right;
}
insertCase5(tree,n);
}
void insertCase3(struct RBTree *tree,struct TreeNode *n)
{
if (nodeColor(uncle(n)) == RED)
{
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insertCase1(tree,grandparent(n));
}
else
{
insertCase4(tree,n);
}
}

void insertCase2(struct RBTree *tree, struct TreeNode *n)
{
if (nodeColor(n->parent) == BLACK)
//  Tree is still valid
{
return;
}
else
{
insertCase3(tree,n);
}
}
void insertCase1(struct RBTree *tree,struct TreeNode *n)
{
if (n->parent == NULL)
{
n->color = BLACK;
}
else
{
insertCase2(tree,n);
}
}
void insert(struct RBTree *tree,int key)
{
struct TreeNode *insertedNode = newNode(key, RED);
if (tree->root == NULL)
{
tree->root = insertedNode;
}
else
{
struct TreeNode *n = tree->root;
while (1)
{
if (key < n->key)
{
if (n->left == NULL)
{
n->left = insertedNode;
break;
}
else
{
n = n->left;
}
}
else if (key > n->key)
{
if (n->right == NULL)
{
n->right = insertedNode;
break;
}
else
{
n = n->right;
}
}
else
{
return;
}
}
insertedNode->parent = n;
}
insertCase1(tree,insertedNode);
verifyProperties(tree->root);
}

void deleteCase6(struct RBTree *tree,struct TreeNode *n)
{
sibling(n)->color = nodeColor(n->parent);
n->parent->color = BLACK;
if (n == n->parent->left)
{
if (nodeColor(sibling(n)->right) == RED)
{
sibling(n)->right->color = BLACK;
rotateLeft(tree,n->parent);
}
else
{
//  Fail case
printf("\n Fail delete case 6 : sibling right node is BLACK \n");
}
}
else
{
if (nodeColor(sibling(n)->left) == RED)
{
sibling(n)->left->color = BLACK;
rotateRight(tree,n->parent);
}
else
{
//  Fail case
printf("\n Fail delete case 6 : sibling left node is BLACK \n");
}
}
}
void deleteCase5(struct RBTree *tree,struct TreeNode *n)
{
if (n == n->parent->left
&& nodeColor(sibling(n)) == BLACK
&& nodeColor(sibling(n)->left) == RED
&& nodeColor(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
sibling(n)->left->color = BLACK;
rotateRight(tree,sibling(n));
}
else if (n == n->parent->right
&& nodeColor(sibling(n)) == BLACK
&& nodeColor(sibling(n)->right) == RED
&& nodeColor(sibling(n)->left) == BLACK)
{
sibling(n)->color = RED;
sibling(n)->right->color = BLACK;
rotateLeft(tree,sibling(n));
}
deleteCase6(tree,n);
}
void deleteCase4(struct RBTree *tree,struct TreeNode *n)
{
if (nodeColor(n->parent) == RED && nodeColor(sibling(n)) == BLACK
&& nodeColor(sibling(n)->left) == BLACK
&& nodeColor(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
n->parent->color = BLACK;
}
else
{
deleteCase5(tree,n);
}
}
void deleteCase3(struct RBTree *tree,struct TreeNode *n)
{
if (nodeColor(n->parent) == BLACK
&& nodeColor(sibling(n)) == BLACK
&& nodeColor(sibling(n)->left) == BLACK
&& nodeColor(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
deleteCase1(tree,n->parent);
}
else
{
deleteCase4(tree,n);
}
}
void deleteCase2(struct RBTree *tree,struct TreeNode *n)
{
if (nodeColor(sibling(n)) == RED)
{
n->parent->color = RED;
sibling(n)->color = BLACK;
if (n == n->parent->left)
{
rotateLeft(tree,n->parent);
}
else
{
rotateRight(tree,n->parent);
}
}
deleteCase3(tree,n);
}
void deleteCase1(struct RBTree *tree,struct TreeNode *n)
{
if (n->parent == NULL)
//  Delete root node
{
return;
}
else
{
deleteCase2(tree,n);
}
}

// Print tree elements in preorder traversal
void preorder(struct TreeNode *n)
{
if (n == NULL)
{
return;
}
// display node key
printf("  %d", n->key);
//  recursively visiting left and right subtree
preorder(n->left);
preorder(n->right);
}
// Print tree elements in inorder traversal
void inorder(struct TreeNode *n)
{
if (n == NULL)
{
return;
}
inorder(n->left);
// display node key
printf("  %d", n->key);
inorder(n->right);
}
// Print tree elements in preorder traversal
void postorder(struct TreeNode *n)
{
if (n == NULL)
{
return;
}
//  recursively visiting left and right subtree
postorder(n->left);
postorder(n->right);
// display node key
printf("  %d", n->key);
}
//  Handles the request to print tree nodes
void printTree(struct TreeNode*root)
{
if (root == NULL)
{
printf("\nEmpty Tree\n\n");
return;
}
printf("\nInorder\n");
inorder(root);
printf("\nPreorder\n");
preorder(root);
printf("\nPostOrder\n");
postorder(root);
}

//  This is handle the request to delete node in tree
void deleteNode(struct RBTree *tree,int key)
{
// First find the deleted node
struct TreeNode *n = findNode(tree->root,key);
if (n == NULL)
{
//  When key node are not exists
return;
}
struct TreeNode *child = NULL;
if (n->left != NULL && n->right != NULL)
{
child = inorderSuccessor(n->left);
n->key = child->key;
n = child;
}
if (n->left == NULL || n->right == NULL)
{
if (n->left == NULL)
{
child = n->right;
}
else
{
child = n->left;
}
}
if (nodeColor(n) == BLACK)
{
n->color = nodeColor(child);
deleteCase1(tree,n);
}
replaceNode(tree,n, child);
verifyProperties(tree->root);
printf("\n\nAfter Delete TreeNode [%d]",key);
printTree(tree->root);
}
int main()
{
struct RBTree *tree = newTree();
insert(tree,18);
insert(tree,5);
insert(tree,1);
insert(tree,11);
insert(tree,21);
insert(tree,6);
insert(tree,9);
insert(tree,7);
insert(tree,30);
insert(tree,40);
printTree(tree->root);
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
deleteNode(tree,1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
deleteNode(tree,5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
deleteNode(tree,9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
deleteNode(tree,18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
printf("\n");
return 0;
}``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````/*
Java program for
Red Black tree node deletion
*/
enum Color
{
RED , BLACK
}
//Define Tree Node
class TreeNode
{
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public Color color;
public TreeNode(int key, Color nodeColor)
{
this.key = key;
this.color = nodeColor;
this.left = null;
this.right = null;
this.parent = null;
}
public TreeNode uncle()
{
if (parent == null)
{
// Fail case
System.out.print("Fail Uncle has no parent\n");
return null;
}
else if (parent.parent == null)
{
// Fail case
System.out.print("Fail Children of root have no uncle\n");
return null;
}
return parent.sibling();
}
public TreeNode sibling()
{
if (parent == null)
{
// Fail case
System.out.print("Fail Subling has no parent\n");
return null;
}
else
{
if (this == parent.left)
{
return parent.right;
}
else
{
return parent.left;
}
}
}
public TreeNode grandparent()
{
if (parent == null || parent.parent == null)
{
// Fail case
System.out.print("Fail Grandparent has no parent\n");
return null;
}
return parent.parent;
}
}
public class RBTree
{
public TreeNode root;
public RBTree()
{
this.root = null;
this.verifyProperties();
}
public void verifyProperties()
{
verifyProperty1(root);
verifyProperty2(root);
verifyProperty4(root);
verifyProperty5(root);
}
private void verifyProperty1(TreeNode n)
{
if (!(nodeColor(n) == Color.RED || nodeColor(n) == Color.BLACK))
{
// Fail case
System.out.print(" Fail case verifyProperty1 \n");
return;
}
if (n == null)
{
return;
}
verifyProperty1(n.left);
verifyProperty1(n.right);
}
private void verifyProperty2(TreeNode n)
{
if (nodeColor(n) != Color.BLACK)
{
// Fail case
System.out.print(" Fail case verifyProperty2 \n");
}
}
private Color nodeColor(TreeNode n)
{
if (n == null)
{
return Color.BLACK;
}
else
{
return n.color;
}
}
private void verifyProperty4(TreeNode n)
{
if (nodeColor(n) == Color.RED)
{
if (nodeColor(n.left) != Color.BLACK || nodeColor(n.right) != Color.BLACK || nodeColor(n.parent) != Color.BLACK)
{
// Fail case
System.out.print("Fail Property of verifyProperty4\n");
}
}
if (n == null)
{
return;
}
verifyProperty4(n.left);
verifyProperty4(n.right);
}
private void verifyProperty5(TreeNode root)
{
verifyProperty5Helper(root, 0, -1);
}
private int verifyProperty5Helper(TreeNode n, int blackCount, int pathBlackCount)
{
if (nodeColor(n) == Color.BLACK)
{
blackCount++;
}
if (n == null)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
// Fail case
System.out.print("Fail Property of verifyProperty5Helper\n");
}
return pathBlackCount;
}
pathBlackCount = verifyProperty5Helper(n.left, blackCount, pathBlackCount);
pathBlackCount = verifyProperty5Helper(n.right, blackCount, pathBlackCount);
return pathBlackCount;
}
private TreeNode findNode(int key)
{
TreeNode n = root;
while (n != null)
{
if (key == n.key)
{
return n;
}
else if (key < n.key)
{
n = n.left;
}
else
{
n = n.right;
}
}
return n;
}
private void rotateLeft(TreeNode n)
{
TreeNode r = n.right;
replaceNode(n, r);
n.right = r.left;
if (r.left != null)
{
r.left.parent = n;
}
r.left = n;
n.parent = r;
}
private void rotateRight(TreeNode n)
{
TreeNode l = n.left;
replaceNode(n, l);
n.left = l.right;
if (l.right != null)
{
l.right.parent = n;
}
l.right = n;
n.parent = l;
}
public void insert(int key)
{
TreeNode insertedNode = new TreeNode(key, Color.RED);
if (root == null)
{
root = insertedNode;
}
else
{
TreeNode n = root;
while (true)
{
if (key < n.key)
{
if (n.left == null)
{
n.left = insertedNode;
break;
}
else
{
n = n.left;
}
}
else if (key > n.key)
{
if (n.right == null)
{
n.right = insertedNode;
break;
}
else
{
n = n.right;
}
}
else
{
return;
}
}
insertedNode.parent = n;
}
insertCase1(insertedNode);
verifyProperties();
}
private void insertCase1(TreeNode n)
{
if (n.parent == null)
{
n.color = Color.BLACK;
}
else
{
insertCase2(n);
}
}
private void insertCase2(TreeNode n)
{
if (nodeColor(n.parent) == Color.BLACK)
{
return; // Tree is still valid
}
else
{
insertCase3(n);
}
}
private void insertCase3(TreeNode n)
{
if (nodeColor(n.uncle()) == Color.RED)
{
n.parent.color = Color.BLACK;
n.uncle().color = Color.BLACK;
n.grandparent().color = Color.RED;
insertCase1(n.grandparent());
}
else
{
insertCase4(n);
}
}
private void insertCase4(TreeNode n)
{
if (n == n.parent.right && n.parent == n.grandparent().left)
{
rotateLeft(n.parent);
n = n.left;
}
else if (n == n.parent.left && n.parent == n.grandparent().right)
{
rotateRight(n.parent);
n = n.right;
}
insertCase5(n);
}
private void insertCase5(TreeNode n)
{
n.parent.color = Color.BLACK;
n.grandparent().color = Color.RED;
if (n == n.parent.left && n.parent == n.grandparent().left)
{
rotateRight(n.grandparent());
}
else
{
if (n == n.parent.right && n.parent == n.grandparent().right)
{
rotateLeft(n.grandparent());
}
else
{
// Fail case
System.out.print("\n Fail insertCase5 \n");
}
}
}
private TreeNode inorderSuccessor(TreeNode n)
{
if (n == null)
{
// Fail case
System.out.print("\n Fail Inorder Successor is NULL\n");
return null;
}
while (n.right != null)
{
n = n.right;
}
return n;
}
private void replaceNode(TreeNode oldn, TreeNode newn)
{
if (oldn.parent == null)
{
this.root = newn;
if (this.root != null)
{
this.root.color = Color.BLACK;
}
}
else
{
if (oldn == oldn.parent.left)
{
oldn.parent.left = newn;
}
else
{
oldn.parent.right = newn;
}
}
if (newn != null)
{
newn.parent = oldn.parent;
}
}
private void deleteCase6(TreeNode n)
{
n.sibling().color = nodeColor(n.parent);
n.parent.color = Color.BLACK;
if (n == n.parent.left)
{
if (nodeColor(n.sibling().right) == Color.RED)
{
n.sibling().right.color = Color.BLACK;
rotateLeft(n.parent);
}
else
{
// Fail case
System.out.print("\n Fail delete case 6 : sibling right node is BLACK \n");
}
}
else
{
if (nodeColor(n.sibling().left) == Color.RED)
{
n.sibling().left.color = Color.BLACK;
rotateRight(n.parent);
}
else
{
// Fail case
System.out.print("\n Fail delete case 6 : sibling left node is BLACK \n");
}
}
}
private void deleteCase5(TreeNode n)
{
if (n == n.parent.left
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().left) == Color.RED
&& nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().left.color = Color.BLACK;
rotateRight(n.sibling());
}
else if (n == n.parent.right
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().right) == Color.RED
&& nodeColor(n.sibling().left) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().right.color = Color.BLACK;
rotateLeft(n.sibling());
}
deleteCase6(n);
}
private void deleteCase4(TreeNode n)
{
if (nodeColor(n.parent) == Color.RED
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().left) == Color.BLACK
&& nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.parent.color = Color.BLACK;
}
else
{
deleteCase5(n);
}
}
private void deleteCase3(TreeNode n)
{
if (nodeColor(n.parent) == Color.BLACK
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().left) == Color.BLACK
&& nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
deleteCase1(n.parent);
}
else
{
deleteCase4(n);
}
}
private void deleteCase2(TreeNode n)
{
if (nodeColor(n.sibling()) == Color.RED)
{
n.parent.color = Color.RED;
n.sibling().color = Color.BLACK;
if (n == n.parent.left)
{
rotateLeft(n.parent);
}
else
{
rotateRight(n.parent);
}
}
deleteCase3(n);
}
private void deleteCase1(TreeNode n)
{
if (n.parent == null)
{
// Delete root node
return;
}
else
{
deleteCase2(n);
}
}
// This is handle the request to delete node in tree
public void deleteNode(int key)
{
//First find the deleted node
TreeNode n = findNode(key);
if (n == null)
{
// When key node are not exists
return;
}
TreeNode child = null;
if (n.left != null && n.right != null)
{
child = inorderSuccessor(n.left);
n.key = child.key;
n = child;
}
if (n.left == null || n.right == null)
{
if (n.left == null)
{
child = n.right;
}
else
{
child = n.left;
}
}
if (nodeColor(n) == Color.BLACK)
{
n.color = nodeColor(child);
deleteCase1(n);
}
replaceNode(n, child);
verifyProperties();
System.out.print("\n\nAfter Delete TreeNode [" + key + "]");
printTree();
}
//Print tree elements in preorder traversal
private void preorder(TreeNode n)
{
if (n == null)
{
return;
}
//display node key
System.out.print("  " + n.key);
// recursively visiting left and right subtree
this.preorder(n.left);
this.preorder(n.right);
}
//Print tree elements in inorder traversal
private void inorder(TreeNode n)
{
if (n == null)
{
return;
}
this.inorder(n.left);
//display node key
System.out.print("  " + n.key);
this.inorder(n.right);
}
//Print tree elements in preorder traversal
private void postorder(TreeNode n)
{
if (n == null)
{
return;
}
// recursively visiting left and right subtree
postorder(n.left);
postorder(n.right);
//display node key
System.out.print("  " + n.key);
}
// Handles the request to print tree nodes
public void printTree()
{
if (root == null)
{
System.out.print("\nEmpty Tree\n\n");
return;
}
System.out.print("\nInorder\n");
inorder(root);
System.out.print("\nPreorder\n");
preorder(root);
System.out.print("\nPostOrder\n");
postorder(root);
}
public static void main(String[] args)
{
RBTree tree = new RBTree();
tree.insert(18);
tree.insert(5);
tree.insert(1);
tree.insert(11);
tree.insert(21);
tree.insert(6);
tree.insert(9);
tree.insert(7);
tree.insert(30);
tree.insert(40);
tree.printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
tree.deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
tree.deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
tree.deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
tree.deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
System.out.print("\n");
}
}``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program for
Red Black tree node deletion
*/
enum Color
{
RED , BLACK
};

// Define Tree Node
class TreeNode
{
public:
int key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
Color  color;
TreeNode(int key, Color nodeColor)
{
this->key = key;
this->color = nodeColor;
this->left = NULL;
this->right = NULL;
this->parent = NULL;
}
TreeNode *uncle()
{
if (this->parent == NULL)
{
//  Fail case
cout << "Fail Uncle has no parent\n";
return NULL;
}
else if (this->parent->parent == NULL)
{
//  Fail case
cout << "Fail Children of root have no uncle\n";
return NULL;
}
return this->parent->sibling();
}
TreeNode *sibling()
{
if (this->parent == NULL)
{
//  Fail case
cout << "Fail Subling has no parent\n";
return NULL;
}
else
{
if (this == this->parent->left)
{
return this->parent->right;
}
else
{
return this->parent->left;
}
}
}
TreeNode *grandparent()
{
if (this->parent == NULL || this->parent->parent == NULL)
{
//  Fail case
cout << "Fail Grandparent has no parent\n";
return NULL;
}
return this->parent->parent;
}
};
class RBTree
{
public: TreeNode *root;
RBTree()
{
this->root = NULL;
this->verifyProperties();
}
void verifyProperties()
{
verifyProperty1(this->root);
verifyProperty2(this->root);
verifyProperty4(this->root);
verifyProperty5(this->root);
}
void verifyProperty1(TreeNode *n)
{
if (!(nodeColor(n) == RED || nodeColor(n) == BLACK))
{
//  Fail case
cout << " Fail case verifyProperty1 \n";
return;
}
if (n == NULL)
{
return;
}
this->verifyProperty1(n->left);
this->verifyProperty1(n->right);
}
void verifyProperty2(TreeNode *n)
{
if (nodeColor(n) != BLACK)
{
//  Fail case
cout << " Fail case verifyProperty2 \n";
}
}
Color nodeColor(TreeNode *n)
{
if (n == NULL)
{
return BLACK;
}
else
{
return n->color;
}
}
void verifyProperty4(TreeNode *n)
{
if (this->nodeColor(n) == RED)
{
if (this->nodeColor(n->left) != BLACK || this->nodeColor(n->right) != BLACK || this->nodeColor(n->parent) != BLACK)
{
//  Fail case
cout << "Fail Property of verifyProperty4\n";
}
}
if (n == NULL)
{
return;
}
this->verifyProperty4(n->left);
this->verifyProperty4(n->right);
}
void verifyProperty5(TreeNode *root)
{
verifyProperty5Helper(root, 0, -1);
}
int verifyProperty5Helper(TreeNode *n, int blackCount, int pathBlackCount)
{
if (this->nodeColor(n) == BLACK)
{
blackCount++;
}
if (n == NULL)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
//  Fail case
cout << "Fail Property of verifyProperty5Helper\n";
}
return pathBlackCount;
}
pathBlackCount = this->verifyProperty5Helper(n->left, blackCount, pathBlackCount);
pathBlackCount = this->verifyProperty5Helper(n->right, blackCount, pathBlackCount);
return pathBlackCount;
}
TreeNode *findNode(int key)
{
TreeNode *n = this->root;
while (n != NULL)
{
if (key == n->key)
{
return n;
}
else if (key < n->key)
{
n = n->left;
}
else
{
n = n->right;
}
}
return n;
}
void rotateLeft(TreeNode *n)
{
TreeNode *r = n->right;
replaceNode(n, r);
n->right = r->left;
if (r->left != NULL)
{
r->left->parent = n;
}
r->left = n;
n->parent = r;
}
void rotateRight(TreeNode *n)
{
TreeNode *l = n->left;
replaceNode(n, l);
n->left = l->right;
if (l->right != NULL)
{
l->right->parent = n;
}
l->right = n;
n->parent = l;
}
void insert(int key)
{
TreeNode *insertedNode = new TreeNode(key, RED);
if (this->root == NULL)
{
this->root = insertedNode;
}
else
{
TreeNode *n = this->root;
while (true)
{
if (key < n->key)
{
if (n->left == NULL)
{
n->left = insertedNode;
break;
}
else
{
n = n->left;
}
}
else if (key > n->key)
{
if (n->right == NULL)
{
n->right = insertedNode;
break;
}
else
{
n = n->right;
}
}
else
{
return;
}
}
insertedNode->parent = n;
}
insertCase1(insertedNode);
this->verifyProperties();
}
void insertCase1(TreeNode *n)
{
if (n->parent == NULL)
{
n->color = BLACK;
}
else
{
insertCase2(n);
}
}
void insertCase2(TreeNode *n)
{
if (this->nodeColor(n->parent) == BLACK)
//  Tree is still valid
{
return;
}
else
{
insertCase3(n);
}
}
void insertCase3(TreeNode *n)
{
if (this->nodeColor(n->uncle()) == RED)
{
n->parent->color = BLACK;
n->uncle()->color = BLACK;
n->grandparent()->color = RED;
this->insertCase1(n->grandparent());
}
else
{
insertCase4(n);
}
}
void insertCase4(TreeNode *n)
{
if (n == n->parent->right && n->parent == n->grandparent()->left)
{
this->rotateLeft(n->parent);
n = n->left;
}
else if (n == n->parent->left && n->parent == n->grandparent()->right)
{
this->rotateRight(n->parent);
n = n->right;
}
insertCase5(n);
}
void insertCase5(TreeNode *n)
{
n->parent->color = BLACK;
n->grandparent()->color = RED;
if (n == n->parent->left && n->parent == n->grandparent()->left)
{
this->rotateRight(n->grandparent());
}
else
{
if (n == n->parent->right && n->parent == n->grandparent()->right)
{
this->rotateLeft(n->grandparent());
}
else
{
//  Fail case
cout << "\n Fail insertCase5 \n";
}
}
}
TreeNode *inorderSuccessor(TreeNode *n)
{
if (n == NULL)
{
//  Fail case
cout << "\n Fail Inorder Successor is NULL\n";
return NULL;
}
while (n->right != NULL)
{
n = n->right;
}
return n;
}
void replaceNode(TreeNode *oldn, TreeNode *newn)
{
if (oldn->parent == NULL)
{
this->root = newn;
if (this->root != NULL)
{
this->root->color = BLACK;
}
}
else
{
if (oldn == oldn->parent->left)
{
oldn->parent->left = newn;
}
else
{
oldn->parent->right = newn;
}
}
if (newn != NULL)
{
newn->parent = oldn->parent;
}
}
void deleteCase6(TreeNode *n)
{
n->sibling()->color = this->nodeColor(n->parent);
n->parent->color = BLACK;
if (n == n->parent->left)
{
if (this->nodeColor(n->sibling()->right) == RED)
{
n->sibling()->right->color = BLACK;
this->rotateLeft(n->parent);
}
else
{
//  Fail case
cout << "\n Fail delete case 6 : sibling right node is BLACK \n";
}
}
else
{
if (this->nodeColor(n->sibling()->left) == RED)
{
n->sibling()->left->color = BLACK;
this->rotateRight(n->parent);
}
else
{
//  Fail case
cout << "\n Fail delete case 6 : sibling left node is BLACK \n";
}
}
}
void deleteCase5(TreeNode *n)
{
if (n == n->parent->left && this->nodeColor(n->sibling()) == BLACK && this->nodeColor(n->sibling()->left) == RED && this->nodeColor(n->sibling()->right) == BLACK)
{
n->sibling()->color = RED;
n->sibling()->left->color = BLACK;
this->rotateRight(n->sibling());
}
else if (n == n->parent->right && this->nodeColor(n->sibling()) == BLACK && this->nodeColor(n->sibling()->right) == RED && this->nodeColor(n->sibling()->left) == BLACK)
{
n->sibling()->color = RED;
n->sibling()->right->color = BLACK;
this->rotateLeft(n->sibling());
}
this->deleteCase6(n);
}
void deleteCase4(TreeNode *n)
{
if (this->nodeColor(n->parent) == RED && this->nodeColor(n->sibling()) == BLACK && this->nodeColor(n->sibling()->left) == BLACK && this->nodeColor(n->sibling()->right) == BLACK)
{
n->sibling()->color = RED;
n->parent->color = BLACK;
}
else
{
this->deleteCase5(n);
}
}
void deleteCase3(TreeNode *n)
{
if (this->nodeColor(n->parent) == BLACK && this->nodeColor(n->sibling()) == BLACK && this->nodeColor(n->sibling()->left) == BLACK && this->nodeColor(n->sibling()->right) == BLACK)
{
n->sibling()->color = RED;
deleteCase1(n->parent);
}
else
{
this->deleteCase4(n);
}
}
void deleteCase2(TreeNode *n)
{
if (this->nodeColor(n->sibling()) == RED)
{
n->parent->color = RED;
n->sibling()->color = BLACK;
if (n == n->parent->left)
{
this->rotateLeft(n->parent);
}
else
{
this->rotateRight(n->parent);
}
}
this->deleteCase3(n);
}
void deleteCase1(TreeNode *n)
{
if (n->parent == NULL)
//  Delete root node
{
return;
}
else
{
this->deleteCase2(n);
}
}
//  This is handle the request to delete node in tree
void deleteNode(int key)
{
// First find the deleted node
TreeNode *n = this->findNode(key);
if (n == NULL)
{
//  When key node are not exists
cout << "\n Delete TreeNode " << key << " Not Found \n";
return;
}
TreeNode *child = NULL;
if (n->left != NULL && n->right != NULL)
{
child = this->inorderSuccessor(n->left);
n->key = child->key;
n = child;
}
if (n->left == NULL || n->right == NULL)
{
if (n->left == NULL)
{
child = n->right;
}
else
{
child = n->left;
}
}
if (this->nodeColor(n) == BLACK)
{
n->color = this->nodeColor(child);
this->deleteCase1(n);
}
this->replaceNode(n, child);
this->verifyProperties();
cout << "\n\nAfter Delete TreeNode [" << key << "]";
printTree();
}
// Print tree elements in preorder traversal
void preorder(TreeNode *n)
{
if (n == NULL)
{
return;
}
// display node key
cout << "  " << n->key;
//  recursively visiting left and right subtree
this->preorder(n->left);
this->preorder(n->right);
}
// Print tree elements in inorder traversal
void inorder(TreeNode *n)
{
if (n == NULL)
{
return;
}
this->inorder(n->left);
// display node key
cout << "  " << n->key;
this->inorder(n->right);
}
// Print tree elements in preorder traversal
void postorder(TreeNode *n)
{
if (n == NULL)
{
return;
}
//  recursively visiting left and right subtree
this->postorder(n->left);
this->postorder(n->right);
// display node key
cout << "  " << n->key;
}
//  Handles the request to print tree nodes
void printTree()
{
if (this->root == NULL)
{
cout << "\nEmpty Tree\n\n";
return;
}
cout << "\nInorder\n";
this->inorder(this->root);
cout << "\nPreorder\n";
this->preorder(this->root);
cout << "\nPostOrder\n";
this->postorder(this->root);
}
};
int main()
{
RBTree tree = RBTree();
tree.insert(18);
tree.insert(5);
tree.insert(1);
tree.insert(11);
tree.insert(21);
tree.insert(6);
tree.insert(9);
tree.insert(7);
tree.insert(30);
tree.insert(40);
tree.printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
tree.deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
tree.deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
tree.deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
tree.deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
cout << "\n";
return 0;
}``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````// Include namespace system
using System;
/*
C# program for
Red Black tree node deletion
*/
public enum Color
{
RED,BLACK
}
// Define Tree Node
public class TreeNode
{
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public Color color;
public TreeNode(int key, Color nodeColor)
{
this.key = key;
this.color = nodeColor;
this.left = null;
this.right = null;
this.parent = null;
}
public TreeNode uncle()
{
if (parent == null)
{
//  Fail case
Console.Write("Fail Uncle has no parent\n");
return null;
}
else if (parent.parent == null)
{
//  Fail case
Console.Write("Fail Children of root have no uncle\n");
return null;
}
return parent.sibling();
}
public TreeNode sibling()
{
if (parent == null)
{
//  Fail case
Console.Write("Fail Subling has no parent\n");
return null;
}
else
{
if (this == parent.left)
{
return parent.right;
}
else
{
return parent.left;
}
}
}
public TreeNode grandparent()
{
if (parent == null || parent.parent == null)
{
//  Fail case
Console.Write("Fail Grandparent has no parent\n");
return null;
}
return parent.parent;
}
}
public class RBTree
{
public TreeNode root;
public RBTree()
{
this.root = null;
this.verifyProperties();
}
public void verifyProperties()
{
verifyProperty1(root);
verifyProperty2(root);
verifyProperty4(root);
verifyProperty5(root);
}
private void verifyProperty1(TreeNode n)
{
if (!(nodeColor(n) == Color.RED || nodeColor(n) == Color.BLACK))
{
//  Fail case
Console.Write(" Fail case verifyProperty1 \n");
return;
}
if (n == null)
{
return;
}
verifyProperty1(n.left);
verifyProperty1(n.right);
}
private void verifyProperty2(TreeNode n)
{
if (nodeColor(n) != Color.BLACK)
{
//  Fail case
Console.Write(" Fail case verifyProperty2 \n");
}
}
private Color nodeColor(TreeNode n)
{
if (n == null)
{
return Color.BLACK;
}
else
{
return n.color;
}
}
private void verifyProperty4(TreeNode n)
{
if (nodeColor(n) == Color.RED)
{
if (nodeColor(n.left) != Color.BLACK
|| nodeColor(n.right) != Color.BLACK
|| nodeColor(n.parent) != Color.BLACK)
{
//  Fail case
Console.Write("Fail Property of verifyProperty4\n");
}
}
if (n == null)
{
return;
}
verifyProperty4(n.left);
verifyProperty4(n.right);
}
private void verifyProperty5(TreeNode root)
{
verifyProperty5Helper(root, 0, -1);
}
private int verifyProperty5Helper(TreeNode n, int blackCount, int pathBlackCount)
{
if (nodeColor(n) == Color.BLACK)
{
blackCount++;
}
if (n == null)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
//  Fail case
Console.Write("Fail Property of verifyProperty5Helper\n");
}
return pathBlackCount;
}
pathBlackCount = verifyProperty5Helper(n.left, blackCount, pathBlackCount);
pathBlackCount = verifyProperty5Helper(n.right, blackCount, pathBlackCount);
return pathBlackCount;
}
private TreeNode findNode(int key)
{
TreeNode n = root;
while (n != null)
{
if (key == n.key)
{
return n;
}
else if (key < n.key)
{
n = n.left;
}
else
{
n = n.right;
}
}
return n;
}
private void rotateLeft(TreeNode n)
{
TreeNode r = n.right;
replaceNode(n, r);
n.right = r.left;
if (r.left != null)
{
r.left.parent = n;
}
r.left = n;
n.parent = r;
}
private void rotateRight(TreeNode n)
{
TreeNode l = n.left;
replaceNode(n, l);
n.left = l.right;
if (l.right != null)
{
l.right.parent = n;
}
l.right = n;
n.parent = l;
}
public void insert(int key)
{
TreeNode insertedNode = new TreeNode(key, Color.RED);
if (root == null)
{
root = insertedNode;
}
else
{
TreeNode n = root;
while (true)
{
if (key < n.key)
{
if (n.left == null)
{
n.left = insertedNode;
break;
}
else
{
n = n.left;
}
}
else if (key > n.key)
{
if (n.right == null)
{
n.right = insertedNode;
break;
}
else
{
n = n.right;
}
}
else
{
return;
}
}
insertedNode.parent = n;
}
insertCase1(insertedNode);
verifyProperties();
}
private void insertCase1(TreeNode n)
{
if (n.parent == null)
{
n.color = Color.BLACK;
}
else
{
insertCase2(n);
}
}
private void insertCase2(TreeNode n)
{
if (nodeColor(n.parent) == Color.BLACK)
//  Tree is still valid
{
return;
}
else
{
insertCase3(n);
}
}
private void insertCase3(TreeNode n)
{
if (nodeColor(n.uncle()) == Color.RED)
{
n.parent.color = Color.BLACK;
n.uncle().color = Color.BLACK;
n.grandparent().color = Color.RED;
insertCase1(n.grandparent());
}
else
{
insertCase4(n);
}
}
private void insertCase4(TreeNode n)
{
if (n == n.parent.right && n.parent == n.grandparent().left)
{
rotateLeft(n.parent);
n = n.left;
}
else if (n == n.parent.left && n.parent == n.grandparent().right)
{
rotateRight(n.parent);
n = n.right;
}
insertCase5(n);
}
private void insertCase5(TreeNode n)
{
n.parent.color = Color.BLACK;
n.grandparent().color = Color.RED;
if (n == n.parent.left && n.parent == n.grandparent().left)
{
rotateRight(n.grandparent());
}
else
{
if (n == n.parent.right && n.parent == n.grandparent().right)
{
rotateLeft(n.grandparent());
}
else
{
//  Fail case
Console.Write("\n Fail insertCase5 \n");
}
}
}
private TreeNode inorderSuccessor(TreeNode n)
{
if (n == null)
{
//  Fail case
Console.Write("\n Fail Inorder Successor is NULL\n");
return null;
}
while (n.right != null)
{
n = n.right;
}
return n;
}
private void replaceNode(TreeNode oldn, TreeNode newn)
{
if (oldn.parent == null)
{
this.root = newn;
if (this.root != null)
{
this.root.color = Color.BLACK;
}
}
else
{
if (oldn == oldn.parent.left)
{
oldn.parent.left = newn;
}
else
{
oldn.parent.right = newn;
}
}
if (newn != null)
{
newn.parent = oldn.parent;
}
}
private void deleteCase6(TreeNode n)
{
n.sibling().color = nodeColor(n.parent);
n.parent.color = Color.BLACK;
if (n == n.parent.left)
{
if (nodeColor(n.sibling().right) == Color.RED)
{
n.sibling().right.color = Color.BLACK;
rotateLeft(n.parent);
}
else
{
//  Fail case
Console.Write("\n Fail delete case 6 : sibling right node is BLACK \n");
}
}
else
{
if (nodeColor(n.sibling().left) == Color.RED)
{
n.sibling().left.color = Color.BLACK;
rotateRight(n.parent);
}
else
{
//  Fail case
Console.Write("\n Fail delete case 6 : sibling left node is BLACK \n");
}
}
}
private void deleteCase5(TreeNode n)
{
if (n == n.parent.left
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().left) == Color.RED
&& nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().left.color = Color.BLACK;
rotateRight(n.sibling());
}
else if (n == n.parent.right
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().right) == Color.RED
&& nodeColor(n.sibling().left) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().right.color = Color.BLACK;
rotateLeft(n.sibling());
}
deleteCase6(n);
}
private void deleteCase4(TreeNode n)
{
if (nodeColor(n.parent) == Color.RED
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().left) == Color.BLACK
&& nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.parent.color = Color.BLACK;
}
else
{
deleteCase5(n);
}
}
private void deleteCase3(TreeNode n)
{
if (nodeColor(n.parent) == Color.BLACK
&& nodeColor(n.sibling()) == Color.BLACK
&& nodeColor(n.sibling().left) == Color.BLACK
&& nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
deleteCase1(n.parent);
}
else
{
deleteCase4(n);
}
}
private void deleteCase2(TreeNode n)
{
if (nodeColor(n.sibling()) == Color.RED)
{
n.parent.color = Color.RED;
n.sibling().color = Color.BLACK;
if (n == n.parent.left)
{
rotateLeft(n.parent);
}
else
{
rotateRight(n.parent);
}
}
deleteCase3(n);
}
private void deleteCase1(TreeNode n)
{
if (n.parent == null)
//  Delete root node
{
return;
}
else
{
deleteCase2(n);
}
}
//  This is handle the request to delete node in tree
public void deleteNode(int key)
{
// First find the deleted node
TreeNode n = findNode(key);
if (n == null)
{
//  When key node are not exists
return;
}
TreeNode child = null;
if (n.left != null && n.right != null)
{
child = inorderSuccessor(n.left);
n.key = child.key;
n = child;
}
if (n.left == null || n.right == null)
{
if (n.left == null)
{
child = n.right;
}
else
{
child = n.left;
}
}
if (nodeColor(n) == Color.BLACK)
{
n.color = nodeColor(child);
deleteCase1(n);
}
replaceNode(n, child);
verifyProperties();
Console.Write("\n\nAfter Delete TreeNode [" + key + "]");
printTree();
}
// Print tree elements in preorder traversal
private void preorder(TreeNode n)
{
if (n == null)
{
return;
}
// display node key
Console.Write("  " + n.key);
//  recursively visiting left and right subtree
this.preorder(n.left);
this.preorder(n.right);
}
// Print tree elements in inorder traversal
private void inorder(TreeNode n)
{
if (n == null)
{
return;
}
this.inorder(n.left);
// display node key
Console.Write("  " + n.key);
this.inorder(n.right);
}
// Print tree elements in preorder traversal
private void postorder(TreeNode n)
{
if (n == null)
{
return;
}
//  recursively visiting left and right subtree
postorder(n.left);
postorder(n.right);
// display node key
Console.Write("  " + n.key);
}
//  Handles the request to print tree nodes
public void printTree()
{
if (root == null)
{
Console.Write("\nEmpty Tree\n\n");
return;
}
Console.Write("\nInorder\n");
inorder(root);
Console.Write("\nPreorder\n");
preorder(root);
Console.Write("\nPostOrder\n");
postorder(root);
}
public static void Main(String[] args)
{
RBTree tree = new RBTree();
tree.insert(18);
tree.insert(5);
tree.insert(1);
tree.insert(11);
tree.insert(21);
tree.insert(6);
tree.insert(9);
tree.insert(7);
tree.insert(30);
tree.insert(40);
tree.printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
tree.deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
tree.deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
tree.deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
tree.deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
Console.Write("\n");
}
}``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````<?php
/*
Php program for
Red Black tree node deletion
*/

abstract class Color
{
const  RED = 0;
const  BLACK = 1;
}

// Define Tree Node
class TreeNode
{
public \$key;
public \$left;
public \$right;
public \$parent;
public \$color;

function __construct(\$key, \$nodeColor)
{
\$this->key = \$key;
\$this->color = \$nodeColor;
\$this->left = null;
\$this->right = null;
\$this->parent = null;
}
public  function uncle()
{
if (\$this->parent == null)
{
//  Fail case
echo "Fail Uncle has no parent\n";
return null;
}
else if (\$this->parent->parent == null)
{
//  Fail case
echo "Fail Children of root have no uncle\n";
return null;
}
return \$this->parent->sibling();
}
public  function sibling()
{
if (\$this->parent == null)
{
//  Fail case
echo "Fail Subling has no parent\n";
return null;
}
else
{
if (\$this == \$this->parent->left)
{
return \$this->parent->right;
}
else
{
return \$this->parent->left;
}
}
}
public  function grandparent()
{
if (\$this->parent == null || \$this->parent->parent == null)
{
//  Fail case
echo "Fail Grandparent has no parent\n";
return null;
}
return \$this->parent->parent;
}
}
class RBTree
{
public \$root;

function __construct()
{
\$this->root = null;
\$this->verifyProperties();
}
public  function verifyProperties()
{
\$this->verifyProperty1(\$this->root);
\$this->verifyProperty2(\$this->root);
\$this->verifyProperty4(\$this->root);
\$this->verifyProperty5(\$this->root);
}
private function verifyProperty1(\$n)
{
if (!(\$this->nodeColor(\$n) == Color::RED || \$this->nodeColor(\$n) == Color::BLACK))
{
//  Fail case
echo " Fail case verifyProperty1 \n";
return;
}
if (\$n == null)
{
return;
}
\$this->verifyProperty1(\$n->left);
\$this->verifyProperty1(\$n->right);
}
private function verifyProperty2(\$n)
{
if (\$this->nodeColor(\$n) != Color::BLACK)
{
//  Fail case
echo " Fail case verifyProperty2 \n";
}
}
private function nodeColor(\$n)
{
if (\$n == null)
{
return Color::BLACK;
}
else
{
return \$n->color;
}
}
private function verifyProperty4(\$n)
{
if (\$this->nodeColor(\$n) == Color::RED)
{
if (\$this->nodeColor(\$n->left) != Color::BLACK || \$this->nodeColor(\$n->right) != Color::BLACK || \$this->nodeColor(\$n->parent) != Color::BLACK)
{
//  Fail case
echo "Fail Property of verifyProperty4\n";
}
}
if (\$n == null)
{
return;
}
\$this->verifyProperty4(\$n->left);
\$this->verifyProperty4(\$n->right);
}
private function verifyProperty5(\$root)
{
\$this->verifyProperty5Helper(\$root, 0, -1);
}
private function verifyProperty5Helper(\$n, \$blackCount, \$pathBlackCount)
{
if (\$this->nodeColor(\$n) == Color::BLACK)
{
\$blackCount++;
}
if (\$n == null)
{
if (\$pathBlackCount == -1)
{
\$pathBlackCount = \$blackCount;
}
else if (\$blackCount != \$pathBlackCount)
{
//  Fail case
echo "Fail Property of verifyProperty5Helper\n";
}
return \$pathBlackCount;
}
\$pathBlackCount = \$this->verifyProperty5Helper(\$n->left, \$blackCount, \$pathBlackCount);
\$pathBlackCount = \$this->verifyProperty5Helper(\$n->right, \$blackCount, \$pathBlackCount);
return \$pathBlackCount;
}
private function findNode(\$key)
{
\$n = \$this->root;
while (\$n != null)
{
if (\$key == \$n->key)
{
return \$n;
}
else if (\$key < \$n->key)
{
\$n = \$n->left;
}
else
{
\$n = \$n->right;
}
}
return \$n;
}
private function rotateLeft(\$n)
{
\$r = \$n->right;
\$this->replaceNode(\$n, \$r);
\$n->right = \$r->left;
if (\$r->left != null)
{
\$r->left->parent = \$n;
}
\$r->left = \$n;
\$n->parent = \$r;
}
private function rotateRight(\$n)
{
\$l = \$n->left;
\$this->replaceNode(\$n, \$l);
\$n->left = \$l->right;
if (\$l->right != null)
{
\$l->right->parent = \$n;
}
\$l->right = \$n;
\$n->parent = \$l;
}
public  function insert(\$key)
{
\$insertedNode = new TreeNode(\$key, Color::RED);
if (\$this->root == null)
{
\$this->root = \$insertedNode;
}
else
{
\$n = \$this->root;
while (true)
{
if (\$key < \$n->key)
{
if (\$n->left == null)
{
\$n->left = \$insertedNode;
break;
}
else
{
\$n = \$n->left;
}
}
else if (\$key > \$n->key)
{
if (\$n->right == null)
{
\$n->right = \$insertedNode;
break;
}
else
{
\$n = \$n->right;
}
}
else
{
return;
}
}
\$insertedNode->parent = \$n;
}
\$this->insertCase1(\$insertedNode);
\$this->verifyProperties();
}
private function insertCase1(\$n)
{
if (\$n->parent == null)
{
\$n->color = Color::BLACK;
}
else
{
\$this->insertCase2(\$n);
}
}
private function insertCase2(\$n)
{
if (\$this->nodeColor(\$n->parent) == Color::BLACK)
//  Tree is still valid
{
return;
}
else
{
\$this->insertCase3(\$n);
}
}
private function insertCase3(\$n)
{
if (\$this->nodeColor(\$n->uncle()) == Color::RED)
{
\$n->parent->color = Color::BLACK;
\$n->uncle()->color = Color::BLACK;
\$n->grandparent()->color = Color::RED;
\$this->insertCase1(\$n->grandparent());
}
else
{
\$this->insertCase4(\$n);
}
}
private function insertCase4(\$n)
{
if (\$n == \$n->parent->right && \$n->parent == \$n->grandparent()->left)
{
\$this->rotateLeft(\$n->parent);
\$n = \$n->left;
}
else if (\$n == \$n->parent->left && \$n->parent == \$n->grandparent()->right)
{
\$this->rotateRight(\$n->parent);
\$n = \$n->right;
}
\$this->insertCase5(\$n);
}
private function insertCase5(\$n)
{
\$n->parent->color = Color::BLACK;
\$n->grandparent()->color = Color::RED;
if (\$n == \$n->parent->left && \$n->parent == \$n->grandparent()->left)
{
\$this->rotateRight(\$n->grandparent());
}
else
{
if (\$n == \$n->parent->right && \$n->parent == \$n->grandparent()->right)
{
\$this->rotateLeft(\$n->grandparent());
}
else
{
//  Fail case
echo "\n Fail insertCase5 \n";
}
}
}
private function inorderSuccessor(\$n)
{
if (\$n == null)
{
//  Fail case
echo "\n Fail Inorder Successor is NULL\n";
return null;
}
while (\$n->right != null)
{
\$n = \$n->right;
}
return \$n;
}
private function replaceNode(\$oldn, \$newn)
{
if (\$oldn->parent == null)
{
\$this->root = \$newn;
if (\$this->root != null)
{
\$this->root->color = Color::BLACK;
}
}
else
{
if (\$oldn == \$oldn->parent->left)
{
\$oldn->parent->left = \$newn;
}
else
{
\$oldn->parent->right = \$newn;
}
}
if (\$newn != null)
{
\$newn->parent = \$oldn->parent;
}
}
private function deleteCase6(\$n)
{
\$n->sibling()->color = \$this->nodeColor(\$n->parent);
\$n->parent->color = Color::BLACK;
if (\$n == \$n->parent->left)
{
if (\$this->nodeColor(\$n->sibling()->right) == Color::RED)
{
\$n->sibling()->right->color = Color::BLACK;
\$this->rotateLeft(\$n->parent);
}
else
{
//  Fail case
echo "\n Fail delete case 6 : sibling right node is BLACK \n";
}
}
else
{
if (\$this->nodeColor(\$n->sibling()->left) == Color::RED)
{
\$n->sibling()->left->color = Color::BLACK;
\$this->rotateRight(\$n->parent);
}
else
{
//  Fail case
echo "\n Fail delete case 6 : sibling left node is BLACK \n";
}
}
}
private function deleteCase5(\$n)
{
if (\$n == \$n->parent->left && \$this->nodeColor(\$n->sibling()) == Color::BLACK && \$this->nodeColor(\$n->sibling()->left) == Color::RED && \$this->nodeColor(\$n->sibling()->right) == Color::BLACK)
{
\$n->sibling()->color = Color::RED;
\$n->sibling()->left->color = Color::BLACK;
\$this->rotateRight(\$n->sibling());
}
else if (\$n == \$n->parent->right && \$this->nodeColor(\$n->sibling()) == Color::BLACK && \$this->nodeColor(\$n->sibling()->right) == Color::RED && \$this->nodeColor(\$n->sibling()->left) == Color::BLACK)
{
\$n->sibling()->color = Color::RED;
\$n->sibling()->right->color = Color::BLACK;
\$this->rotateLeft(\$n->sibling());
}
\$this->deleteCase6(\$n);
}
private function deleteCase4(\$n)
{
if (\$this->nodeColor(\$n->parent) == Color::RED && \$this->nodeColor(\$n->sibling()) == Color::BLACK && \$this->nodeColor(\$n->sibling()->left) == Color::BLACK && \$this->nodeColor(\$n->sibling()->right) == Color::BLACK)
{
\$n->sibling()->color = Color::RED;
\$n->parent->color = Color::BLACK;
}
else
{
\$this->deleteCase5(\$n);
}
}
private function deleteCase3(\$n)
{
if (\$this->nodeColor(\$n->parent) == Color::BLACK && \$this->nodeColor(\$n->sibling()) == Color::BLACK && \$this->nodeColor(\$n->sibling()->left) == Color::BLACK && \$this->nodeColor(\$n->sibling()->right) == Color::BLACK)
{
\$n->sibling()->color = Color::RED;
\$this->deleteCase1(\$n->parent);
}
else
{
\$this->deleteCase4(\$n);
}
}
private function deleteCase2(\$n)
{
if (\$this->nodeColor(\$n->sibling()) == Color::RED)
{
\$n->parent->color = Color::RED;
\$n->sibling()->color = Color::BLACK;
if (\$n == \$n->parent->left)
{
\$this->rotateLeft(\$n->parent);
}
else
{
\$this->rotateRight(\$n->parent);
}
}
\$this->deleteCase3(\$n);
}
private function deleteCase1(\$n)
{
if (\$n->parent == null)
//  Delete root node
{
return;
}
else
{
\$this->deleteCase2(\$n);
}
}
//  This is handle the request to delete node in tree
public  function deleteNode(\$key)
{
// First find the deleted node
\$n = \$this->findNode(\$key);
if (\$n == null)
{
//  When key node are not exists
return;
}
\$child = null;
if (\$n->left != null && \$n->right != null)
{
\$child = \$this->inorderSuccessor(\$n->left);
\$n->key = \$child->key;
\$n = \$child;
}
if (\$n->left == null || \$n->right == null)
{
if (\$n->left == null)
{
\$child = \$n->right;
}
else
{
\$child = \$n->left;
}
}
if (\$this->nodeColor(\$n) == Color::BLACK)
{
\$n->color = \$this->nodeColor(\$child);
\$this->deleteCase1(\$n);
}
\$this->replaceNode(\$n, \$child);
\$this->verifyProperties();
echo "\n\nAfter Delete TreeNode [". \$key ."]";
\$this->printTree();
}
// Print tree elements in preorder traversal
private function preorder(\$n)
{
if (\$n == null)
{
return;
}
// display node key
echo "  ". \$n->key;
//  recursively visiting left and right subtree
\$this->preorder(\$n->left);
\$this->preorder(\$n->right);
}
// Print tree elements in inorder traversal
private function inorder(\$n)
{
if (\$n == null)
{
return;
}
\$this->inorder(\$n->left);
// display node key
echo "  ". \$n->key;
\$this->inorder(\$n->right);
}
// Print tree elements in preorder traversal
private function postorder(\$n)
{
if (\$n == null)
{
return;
}
//  recursively visiting left and right subtree
\$this->postorder(\$n->left);
\$this->postorder(\$n->right);
// display node key
echo "  ". \$n->key;
}
//  Handles the request to print tree nodes
public  function printTree()
{
if (\$this->root == null)
{
echo "\nEmpty Tree\n\n";
return;
}
echo "\nInorder\n";
\$this->inorder(\$this->root);
echo "\nPreorder\n";
\$this->preorder(\$this->root);
echo "\nPostOrder\n";
\$this->postorder(\$this->root);
}
}

function main()
{
\$tree = new RBTree();
\$tree->insert(18);
\$tree->insert(5);
\$tree->insert(1);
\$tree->insert(11);
\$tree->insert(21);
\$tree->insert(6);
\$tree->insert(9);
\$tree->insert(7);
\$tree->insert(30);
\$tree->insert(40);
\$tree->printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
\$tree->deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
\$tree->deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
\$tree->deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
\$tree->deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
echo "\n";
}
main();``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````/*
Node Js program for
Red Black tree node deletion
*/

class Color
{
static get RED() { return 0; }
static get BLACK() { return 1; }
}
// Define Tree Node
class TreeNode
{
constructor(key, color)
{
this.key = key;
this.color = color;
this.left = null;
this.right = null;
this.parent = null;
}
uncle()
{
if (this.parent == null)
{
//  Fail case
process.stdout.write("Fail Uncle has no parent\n");
return null;
}
else if (this.parent.parent == null)
{
//  Fail case
process.stdout.write("Fail Children of root have no uncle\n");
return null;
}
return this.parent.sibling();
}
sibling()
{
if (this.parent == null)
{
//  Fail case
process.stdout.write("Fail Subling has no parent\n");
return null;
}
else
{
if (this == this.parent.left)
{
return this.parent.right;
}
else
{
return this.parent.left;
}
}
}
grandparent()
{
if (this.parent == null || this.parent.parent == null)
{
//  Fail case
process.stdout.write("Fail Grandparent has no parent\n");
return null;
}
return this.parent.parent;
}
}
class RBTree
{
constructor()
{
this.root = null;
this.verifyProperties();
}
verifyProperties()
{
this.verifyProperty1(this.root);
this.verifyProperty2(this.root);
this.verifyProperty4(this.root);
this.verifyProperty5(this.root);
}
verifyProperty1(n)
{
if (!(this.nodeColor(n) == Color.RED || this.nodeColor(n) == Color.BLACK))
{
//  Fail case
process.stdout.write(" Fail case verifyProperty1 \n");
return;
}
if (n == null)
{
return;
}
this.verifyProperty1(n.left);
this.verifyProperty1(n.right);
}
verifyProperty2(n)
{
if (this.nodeColor(n) != Color.BLACK)
{
//  Fail case
process.stdout.write(" Fail case verifyProperty2 \n");
}
}
nodeColor(n)
{
if (n == null)
{
return Color.BLACK;
}
else
{
return n.color;
}
}
verifyProperty4(n)
{
if (n == null)
{
return;
}
if (this.nodeColor(n) == Color.RED)
{
if (this.nodeColor(n.left) != Color.BLACK || this.nodeColor(n.right) != Color.BLACK || this.nodeColor(n.parent) != Color.BLACK)
{
process.stdout.write("Fail Property of verifyProperty4\n");
process.stdout.write("\nNode "+n.key);
process.stdout.write("\tLeft Color "+this.nodeColor(n.left));
process.stdout.write("\tRight Color "+this.nodeColor(n.right));
process.stdout.write("\tparent Color "+this.nodeColor(n.parent)+"\n");
//  Fail case
//process.stdout.write("Fail Property of verifyProperty4\n"+this.nodeColor(n)+" "+this.nodeColor(n.right)+" "+this.nodeColor(n.left));
this.printTree();
}
}

this.verifyProperty4(n.left);
this.verifyProperty4(n.right);
}
verifyProperty5(root)
{
this.verifyProperty5Helper(root, 0, -1);
}
verifyProperty5Helper(n, blackCount, pathBlackCount)
{
if (this.nodeColor(n) == Color.BLACK)
{
blackCount++;
}
if (n == null)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
//  Fail case
process.stdout.write("Fail Property of verifyProperty5Helper\n");
}
return pathBlackCount;
}
pathBlackCount = this.verifyProperty5Helper(n.left, blackCount, pathBlackCount);
pathBlackCount = this.verifyProperty5Helper(n.right, blackCount, pathBlackCount);
return pathBlackCount;
}
findNode(key)
{
var n = this.root;
while (n != null)
{
if (key == n.key)
{
return n;
}
else if (key < n.key)
{
n = n.left;
}
else
{
n = n.right;
}
}
return n;
}
rotateLeft(n)
{
var r = n.right;
this.replaceNode(n, r);
n.right = r.left;
if (r.left != null)
{
r.left.parent = n;
}
r.left = n;
n.parent = r;
}
rotateRight(n)
{
var l = n.left;
this.replaceNode(n, l);
n.left = l.right;
if (l.right != null)
{
l.right.parent = n;
}
l.right = n;
n.parent = l;
}
insert(key)
{
var node = new TreeNode(key, Color.RED);
if (this.root == null)
{
this.root = node;
}
else
{
var n = this.root;
while (true)
{
if (key < n.key)
{
if (n.left == null)
{
n.left = node;
break;
}
else
{
n = n.left;
}
}
else if (key > n.key)
{
if (n.right == null)
{
n.right = node;
break;
}
else
{
n = n.right;
}
}
else
{
return;
}
}
node.parent = n;
}

this.insertCase1(node);
this.verifyProperties();
}
insertCase1(n)
{
if (n.parent == null)
{
n.color = Color.BLACK;
}
else
{
this.insertCase2(n);
}
}
insertCase2(n)
{
if (this.nodeColor(n.parent) == Color.BLACK)
{
//  Tree is still valid
return;
}
else
{
this.insertCase3(n);
}
}
insertCase3(n)
{

if (this.nodeColor(n.uncle()) == Color.RED)
{

n.parent.color = Color.BLACK;
n.uncle().color = Color.BLACK;
n.grandparent().color = Color.RED;
this.insertCase1(n.grandparent());
}
else
{

this.insertCase4(n);
}
}
insertCase4(n)
{
if (n == n.parent.right && n.parent == n.grandparent().left)
{
this.rotateLeft(n.parent);
n = n.left;
}
else if (n == n.parent.left && n.parent == n.grandparent().right)
{
this.rotateRight(n.parent);
n = n.right;
}
this.insertCase5(n);
}
insertCase5(n)
{
n.parent.color = Color.BLACK;
n.grandparent().color = Color.RED;
if (n == n.parent.left && n.parent == n.grandparent().left)
{
this.rotateRight(n.grandparent());
}
else
{
if (n == n.parent.right && n.parent == n.grandparent().right)
{
this.rotateLeft(n.grandparent());
}
else
{
//  Fail case
process.stdout.write("\n Fail insertCase5 \n");
}
}
}
inorderSuccessor(n)
{
if (n == null)
{
//  Fail case
process.stdout.write("\n Fail Inorder Successor is NULL\n");
return null;
}
while (n.right != null)
{
n = n.right;
}
return n;
}
replaceNode(oldn, newn)
{
if (oldn.parent == null)
{
this.root = newn;
if (this.root != null)
{
this.root.color = Color.BLACK;
}
}
else
{
if (oldn == oldn.parent.left)
{
oldn.parent.left = newn;
}
else
{
oldn.parent.right = newn;
}
}
if (newn != null)
{
newn.parent = oldn.parent;
}
}
deleteCase6(n)
{
n.sibling().color = this.nodeColor(n.parent);
n.parent.color = Color.BLACK;
if (n == n.parent.left)
{
if (this.nodeColor(n.sibling().right) == Color.RED)
{
n.sibling().right.color = Color.BLACK;
this.rotateLeft(n.parent);
}
else
{
//  Fail case
process.stdout.write("\n Fail delete case 6 : sibling right node is BLACK \n");
}
}
else
{
if (this.nodeColor(n.sibling().left) == Color.RED)
{
n.sibling().left.color = Color.BLACK;
this.rotateRight(n.parent);
}
else
{
//  Fail case
process.stdout.write("\n Fail delete case 6 : sibling left node is BLACK \n");
}
}
}
deleteCase5(n)
{
if (n == n.parent.left && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().left) == Color.RED && this.nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().left.color = Color.BLACK;
this.rotateRight(n.sibling());
}
else if (n == n.parent.right && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().right) == Color.RED && this.nodeColor(n.sibling().left) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().right.color = Color.BLACK;
this.rotateLeft(n.sibling());
}
this.deleteCase6(n);
}
deleteCase4(n)
{
if (this.nodeColor(n.parent) == Color.RED && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().left) == Color.BLACK && this.nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.parent.color = Color.BLACK;
}
else
{
this.deleteCase5(n);
}
}
deleteCase3(n)
{
if (this.nodeColor(n.parent) == Color.BLACK && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().left) == Color.BLACK && this.nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
deleteCase1(n.parent);
}
else
{
this.deleteCase4(n);
}
}
deleteCase2(n)
{
if (this.nodeColor(n.sibling()) == Color.RED)
{
n.parent.color = Color.RED;
n.sibling().color = Color.BLACK;
if (n == n.parent.left)
{
this.rotateLeft(n.parent);
}
else
{
this.rotateRight(n.parent);
}
}
this.deleteCase3(n);
}
deleteCase1(n)
{
if (n.parent == null)

{
//  Delete root node
return;
}
else
{
this.deleteCase2(n);
}
}
//  This is handle the request to delete node in tree
deleteNode(key)
{
// First find the deleted node
var n = this.findNode(key);
if (n == null)
{
//  When key node are not exists
return;
}
var child = null;
if (n.left != null && n.right != null)
{
child = this.inorderSuccessor(n.left);
n.key = child.key;
n = child;
}
if (n.left == null || n.right == null)
{
if (n.left == null)
{
child = n.right;
}
else
{
child = n.left;
}
}
if (this.nodeColor(n) == Color.BLACK)
{
n.color = this.nodeColor(child);
this.deleteCase1(n);
}
this.replaceNode(n, child);
this.verifyProperties();
process.stdout.write("\n\nAfter Delete TreeNode [" + key + "]");
this.printTree();
}
// Print tree elements in preorder traversal
preorder(n)
{
if (n == null)
{
return;
}
// display node key
process.stdout.write("  " + n.key);
//  recursively visiting left and right subtree
this.preorder(n.left);
this.preorder(n.right);
}
// Print tree elements in inorder traversal
inorder(n)
{
if (n == null)
{
return;
}
this.inorder(n.left);
// display node key
process.stdout.write("  " + n.key);
this.inorder(n.right);
}
// Print tree elements in preorder traversal
postorder(n)
{
if (n == null)
{
return;
}
//  recursively visiting left and right subtree
this.postorder(n.left);
this.postorder(n.right);
// display node key
process.stdout.write("  " + n.key);
}
//  Handles the request to print tree nodes
printTree()
{
if (this.root == null)
{
process.stdout.write("\nEmpty Tree\n\n");
return;
}
process.stdout.write("\nInorder\n");
this.inorder(this.root);
process.stdout.write("\nPreorder\n");
this.preorder(this.root);
process.stdout.write("\nPostOrder\n");
this.postorder(this.root);
}
}

function main()
{

var tree = new RBTree();
tree.insert(18);
tree.insert(5);
tree.insert(1);
tree.insert(11);
tree.insert(21);
tree.insert(6);
tree.insert(9);
tree.insert(7);
tree.insert(30);
tree.insert(40);
tree.printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
tree.deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
tree.deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
tree.deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
tree.deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
process.stdout.write("\n");
}
main();``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````#
#     Python 3 program for
#     Red Black tree node deletion

def constant(f):
def fset(self, value):
raise TypeError
def fget(self):
return f()
return property(fget, fset)

class _Color:
@constant
def RED():
return 0
@constant
def BLACK():
return 1

Color = _Color();

# Define Tree Node
class TreeNode :

def __init__(self, key, nodeColor) :
self.key = key
self.color = nodeColor
self.left = None
self.right = None
self.parent = None

def uncle(self) :
if (self.parent == None) :
#  Fail case
print("Fail Uncle has no parent\n", end = "")
return None

elif(self.parent.parent == None) :
#  Fail case
print("Fail Children of root have no uncle\n", end = "")
return None

return self.parent.sibling()

def sibling(self) :
if (self.parent == None) :
#  Fail case
print("Fail Subling has no parent\n", end = "")
return None
else :
if (self == self.parent.left) :
return self.parent.right
else :
return self.parent.left

def grandparent(self) :
if (self.parent == None or self.parent.parent == None) :
#  Fail case
print("Fail Grandparent has no parent\n", end = "")
return None

return self.parent.parent

class RBTree :

def __init__(self) :
self.root = None
self.verifyProperties()

def verifyProperties(self) :
self.verifyProperty1(self.root)
self.verifyProperty2(self.root)
self.verifyProperty4(self.root)
self.verifyProperty5(self.root)

def verifyProperty1(self, n) :
if (not(self.nodeColor(n) == Color.RED or self.nodeColor(n) == Color.BLACK)) :
#  Fail case
print(" Fail case verifyProperty1 \n", end = "")
return

if (n == None) :
return

self.verifyProperty1(n.left)
self.verifyProperty1(n.right)

def verifyProperty2(self, n) :
if (self.nodeColor(n) != Color.BLACK) :
#  Fail case
print(" Fail case verifyProperty2 \n", end = "")

def nodeColor(self, n) :
if (n == None) :
return Color.BLACK
else :
return n.color

def verifyProperty4(self, n) :
if (self.nodeColor(n) == Color.RED) :
if (self.nodeColor(n.left) != Color.BLACK or self.nodeColor(n.right) != Color.BLACK or self.nodeColor(n.parent) != Color.BLACK) :
#  Fail case
print("Fail Property of verifyProperty4\n", end = "")

if (n == None) :
return

self.verifyProperty4(n.left)
self.verifyProperty4(n.right)

def verifyProperty5(self, root) :
self.verifyProperty5Helper(root, 0, -1)

def verifyProperty5Helper(self, n, blackCount, pathBlackCount) :
if (self.nodeColor(n) == Color.BLACK) :
blackCount += 1

if (n == None) :
if (pathBlackCount == -1) :
pathBlackCount = blackCount

elif(blackCount != pathBlackCount) :
#  Fail case
print("Fail Property of verifyProperty5Helper\n", end = "")

return pathBlackCount

pathBlackCount = self.verifyProperty5Helper(n.left, blackCount, pathBlackCount)
pathBlackCount = self.verifyProperty5Helper(n.right, blackCount, pathBlackCount)
return pathBlackCount

def findNode(self, key) :
n = self.root
while (n != None) :
if (key == n.key) :
return n

elif(key < n.key) :
n = n.left
else :
n = n.right

return n

def rotateLeft(self, n) :
r = n.right
self.replaceNode(n, r)
n.right = r.left
if (r.left != None) :
r.left.parent = n

r.left = n
n.parent = r

def rotateRight(self, n) :
l = n.left
self.replaceNode(n, l)
n.left = l.right
if (l.right != None) :
l.right.parent = n

l.right = n
n.parent = l

def insert(self, key) :
insertedNode = TreeNode(key, Color.RED)
if (self.root == None) :
self.root = insertedNode
else :
n = self.root
while (True) :
if (key < n.key) :
if (n.left == None) :
n.left = insertedNode
break
else :
n = n.left

elif(key > n.key) :
if (n.right == None) :
n.right = insertedNode
break
else :
n = n.right

else :
return

insertedNode.parent = n

self.insertCase1(insertedNode)
self.verifyProperties()

def insertCase1(self, n) :
if (n.parent == None) :
n.color = Color.BLACK
else :
self.insertCase2(n)

def insertCase2(self, n) :
if (self.nodeColor(n.parent) == Color.BLACK) :
#  Tree is still valid
return
else :
self.insertCase3(n)

def insertCase3(self, n) :
if (self.nodeColor(n.uncle()) == Color.RED) :
n.parent.color = Color.BLACK
n.uncle().color = Color.BLACK
n.grandparent().color = Color.RED
self.insertCase1(n.grandparent())
else :
self.insertCase4(n)

def insertCase4(self, n) :
if (n == n.parent.right and n.parent == n.grandparent().left) :
self.rotateLeft(n.parent)
n = n.left

elif(n == n.parent.left and n.parent == n.grandparent().right) :
self.rotateRight(n.parent)
n = n.right

self.insertCase5(n)

def insertCase5(self, n) :
n.parent.color = Color.BLACK
n.grandparent().color = Color.RED
if (n == n.parent.left and n.parent == n.grandparent().left) :
self.rotateRight(n.grandparent())
else :
if (n == n.parent.right and n.parent == n.grandparent().right) :
self.rotateLeft(n.grandparent())
else :
#  Fail case
print("\n Fail insertCase5 \n", end = "")

def inorderSuccessor(self, n) :
if (n == None) :
#  Fail case
print("\n Fail Inorder Successor is NULL\n", end = "")
return None

while (n.right != None) :
n = n.right

return n

def replaceNode(self, oldn, newn) :
if (oldn.parent == None) :
self.root = newn
if (self.root != None) :
self.root.color = Color.BLACK

else :
if (oldn == oldn.parent.left) :
oldn.parent.left = newn
else :
oldn.parent.right = newn

if (newn != None) :
newn.parent = oldn.parent

def deleteCase6(self, n) :
n.sibling().color = self.nodeColor(n.parent)
n.parent.color = Color.BLACK
if (n == n.parent.left) :
if (self.nodeColor(n.sibling().right) == Color.RED) :
n.sibling().right.color = Color.BLACK
self.rotateLeft(n.parent)
else :
#  Fail case
print("\n Fail delete case 6 : sibling right node is BLACK \n", end = "")

else :
if (self.nodeColor(n.sibling().left) == Color.RED) :
n.sibling().left.color = Color.BLACK
self.rotateRight(n.parent)
else :
#  Fail case
print("\n Fail delete case 6 : sibling left node is BLACK \n", end = "")

def deleteCase5(self, n) :
if (n == n.parent.left and self.nodeColor(n.sibling()) == Color.BLACK and self.nodeColor(n.sibling().left) == Color.RED and self.nodeColor(n.sibling().right) == Color.BLACK) :
n.sibling().color = Color.RED
n.sibling().left.color = Color.BLACK
self.rotateRight(n.sibling())

elif(n == n.parent.right and self.nodeColor(n.sibling()) == Color.BLACK and self.nodeColor(n.sibling().right) == Color.RED and self.nodeColor(n.sibling().left) == Color.BLACK) :
n.sibling().color = Color.RED
n.sibling().right.color = Color.BLACK
self.rotateLeft(n.sibling())

self.deleteCase6(n)

def deleteCase4(self, n) :
if (self.nodeColor(n.parent) == Color.RED and self.nodeColor(n.sibling()) == Color.BLACK and self.nodeColor(n.sibling().left) == Color.BLACK and self.nodeColor(n.sibling().right) == Color.BLACK) :
n.sibling().color = Color.RED
n.parent.color = Color.BLACK
else :
self.deleteCase5(n)

def deleteCase3(self, n) :
if (self.nodeColor(n.parent) == Color.BLACK and self.nodeColor(n.sibling()) == Color.BLACK and self.nodeColor(n.sibling().left) == Color.BLACK and self.nodeColor(n.sibling().right) == Color.BLACK) :
n.sibling().color = Color.RED
self.deleteCase1(n.parent)
else :
self.deleteCase4(n)

def deleteCase2(self, n) :
if (self.nodeColor(n.sibling()) == Color.RED) :
n.parent.color = Color.RED
n.sibling().color = Color.BLACK
if (n == n.parent.left) :
self.rotateLeft(n.parent)
else :
self.rotateRight(n.parent)

self.deleteCase3(n)

def deleteCase1(self, n) :
if (n.parent == None) :
#  Delete root node
return
else :
self.deleteCase2(n)

#  This is handle the request to delete node in tree
def deleteNode(self, key) :
# First find the deleted node
n = self.findNode(key)
if (n == None) :
#  When key node are not exists
print("\n Delete TreeNode ", key ," Not Found \n", end = "")
return

child = None
if (n.left != None and n.right != None) :
child = self.inorderSuccessor(n.left)
n.key = child.key
n = child

if (n.left == None or n.right == None) :
if (n.left == None) :
child = n.right
else :
child = n.left

if (self.nodeColor(n) == Color.BLACK) :
n.color = self.nodeColor(child)
self.deleteCase1(n)

self.replaceNode(n, child)
self.verifyProperties()
print("\n\nAfter Delete TreeNode [", key ,"]", end = "")
self.printTree()

# Print tree elements in preorder traversal
def preorder(self, n) :
if (n == None) :
return

# display node key
print("  ", n.key, end = "")
#  recursively visiting left and right subtree
self.preorder(n.left)
self.preorder(n.right)

# Print tree elements in inorder traversal
def inorder(self, n) :
if (n == None) :
return

self.inorder(n.left)
# display node key
print("  ", n.key, end = "")
self.inorder(n.right)

# Print tree elements in preorder traversal
def postorder(self, n) :
if (n == None) :
return

#  recursively visiting left and right subtree
self.postorder(n.left)
self.postorder(n.right)
# display node key
print("  ", n.key, end = "")

#  Handles the request to print tree nodes
def printTree(self) :
if (self.root == None) :
print("\nEmpty Tree\n\n", end = "")
return

print("\nInorder\n", end = "")
self.inorder(self.root)
print("\nPreorder\n", end = "")
self.preorder(self.root)
print("\nPostOrder\n", end = "")
self.postorder(self.root)

def main() :
tree = RBTree()
tree.insert(18)
tree.insert(5)
tree.insert(1)
tree.insert(11)
tree.insert(21)
tree.insert(6)
tree.insert(9)
tree.insert(7)
tree.insert(30)
tree.insert(40)
tree.printTree()
#
#       Constructed Red-Black Tree
#             9
#          /     \
#         5       18
#        / \     /   \
#       1   6   11   30
#            \      /   \
#             7    21    40
#

tree.deleteNode(1)
#
#       After Delete Node 1
#       ---------------------
#             9
#           /   \
#          6     18
#        /  \    / \
#       5    7  11   30
#                   /  \
#                  21   40
#

tree.deleteNode(5)
#
#       After Delete Node 5
#       ---------------------
#             9
#           /    \
#          6     18
#           \    /  \
#            7  11   30
#                   /  \
#                  21   40
#

tree.deleteNode(9)
#
#       After Delete Node 9
#       ---------------------
#             7
#           /   \
#          6      18
#                /   \
#               11   30
#                   /   \
#                  21    40
#

tree.deleteNode(18)
#
#       After Delete Node 18
#       -------------------
#              7
#            /   \
#           6     30
#                /  \
#               11   40
#                 \
#                  21
#

print("\n", end = "")

if __name__ == "__main__":
main()``````

#### Output

``````Inorder
1   5   6   7   9   11   18   21   30   40
Preorder
9   5   1   6   7   18   11   30   21   40
PostOrder
1   7   6   5   11   21   40   30   18   9

After Delete TreeNode [ 1 ]
Inorder
5   6   7   9   11   18   21   30   40
Preorder
9   6   5   7   18   11   30   21   40
PostOrder
5   7   6   11   21   40   30   18   9

After Delete TreeNode [ 5 ]
Inorder
6   7   9   11   18   21   30   40
Preorder
9   6   7   18   11   30   21   40
PostOrder
7   6   11   21   40   30   18   9

After Delete TreeNode [ 9 ]
Inorder
6   7   11   18   21   30   40
Preorder
7   6   18   11   30   21   40
PostOrder
6   11   21   40   30   18   7

After Delete TreeNode [ 18 ]
Inorder
6   7   11   21   30   40
Preorder
7   6   30   11   21   40
PostOrder
6   21   11   40   30   7``````
``````#  Ruby program for
#  Red Black tree node deletion
class Color
RED = 0
BLACK = 1
end

# Define Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :key, :left, :right, :parent, :color
attr_accessor :key, :left, :right, :parent, :color

def initialize(key, nodeColor)
self.key = key
self.color = nodeColor
self.left = nil
self.right = nil
self.parent = nil
end

def uncle()
if (self.parent == nil)
#  Fail case
print("Fail Uncle has no parent\n")
return nil
elsif(self.parent.parent == nil)
#  Fail case
print("Fail Children of root have no uncle\n")
return nil
end

return self.parent.sibling()
end

def sibling()
if (self.parent == nil)
#  Fail case
print("Fail Subling has no parent\n")
return nil
else
if (self == self.parent.left)
return self.parent.right
else
return self.parent.left
end

end

end

def grandparent()
if (self.parent == nil || self.parent.parent == nil)
#  Fail case
print("Fail Grandparent has no parent\n")
return nil
end

return self.parent.parent
end

end

class RBTree
# Define the accessor and reader of class RBTree
attr_accessor :root

def initialize()
self.root = nil
self.verifyProperties()
end

def verifyProperties()
self.verifyProperty1(self.root)
self.verifyProperty2(self.root)
self.verifyProperty4(self.root)
self.verifyProperty5(self.root)
end

def verifyProperty1(n)
if (!(self.nodeColor(n) == Color::RED || self.nodeColor(n) == Color::BLACK))
#  Fail case
print(" Fail case verifyProperty1 \n")
return
end

if (n == nil)
return
end

self.verifyProperty1(n.left)
self.verifyProperty1(n.right)
end

def verifyProperty2(n)
if (nodeColor(n) != Color::BLACK)
#  Fail case
print(" Fail case verifyProperty2 \n")
end

end

def nodeColor(n)
if (n == nil)
return Color::BLACK
else
return n.color
end

end

def verifyProperty4(n)
if (self.nodeColor(n) == Color::RED)
if (self.nodeColor(n.left) != Color::BLACK || self.nodeColor(n.right) != Color::BLACK || self.nodeColor(n.parent) != Color::BLACK)
#  Fail case
print("Fail Property of verifyProperty4\n")
end

end

if (n == nil)
return
end

self.verifyProperty4(n.left)
self.verifyProperty4(n.right)
end

def verifyProperty5(root)
self.verifyProperty5Helper(root, 0, -1)
end

def verifyProperty5Helper(n, blackCount, pathBlackCount)
if (self.nodeColor(n) == Color::BLACK)
blackCount += 1
end

if (n == nil)
if (pathBlackCount == -1)
pathBlackCount = blackCount
elsif(blackCount != pathBlackCount)
#  Fail case
print("Fail Property of verifyProperty5Helper\n")
end

return pathBlackCount
end

pathBlackCount = self.verifyProperty5Helper(n.left, blackCount, pathBlackCount)
pathBlackCount = self.verifyProperty5Helper(n.right, blackCount, pathBlackCount)
return pathBlackCount
end

def findNode(key)
n = root
while (n != nil)
if (key == n.key)
return n
elsif(key < n.key)
n = n.left
else
n = n.right
end

end

return n
end

def rotateLeft(n)
r = n.right
self.replaceNode(n, r)
n.right = r.left
if (r.left != nil)
r.left.parent = n
end

r.left = n
n.parent = r
end

def rotateRight(n)
l = n.left
self.replaceNode(n, l)
n.left = l.right
if (l.right != nil)
l.right.parent = n
end

l.right = n
n.parent = l
end

def insert(key)
insertedNode = TreeNode.new(key, Color::RED)
if (self.root == nil)
self.root = insertedNode
else
n = root
while (true)
if (key < n.key)
if (n.left == nil)
n.left = insertedNode
break
else
n = n.left
end

elsif(key > n.key)
if (n.right == nil)
n.right = insertedNode
break
else
n = n.right
end

else
return
end

end

insertedNode.parent = n
end

self.insertCase1(insertedNode)
self.verifyProperties()
end

def insertCase1(n)
if (n.parent == nil)
n.color = Color::BLACK
else
insertCase2(n)
end

end

def insertCase2(n)
if (self.nodeColor(n.parent) == Color::BLACK)
#  Tree is still valid

return
else
self.insertCase3(n)
end

end

def insertCase3(n)
if (self.nodeColor(n.uncle()) == Color::RED)
n.parent.color = Color::BLACK
n.uncle().color = Color::BLACK
n.grandparent().color = Color::RED
self.insertCase1(n.grandparent())
else
self.insertCase4(n)
end

end

def insertCase4(n)
if (n == n.parent.right && n.parent == n.grandparent().left)
self.rotateLeft(n.parent)
n = n.left
elsif(n == n.parent.left && n.parent == n.grandparent().right)
self.rotateRight(n.parent)
n = n.right
end

self.insertCase5(n)
end

def insertCase5(n)
n.parent.color = Color::BLACK
n.grandparent().color = Color::RED
if (n == n.parent.left && n.parent == n.grandparent().left)
self.rotateRight(n.grandparent())
else
if (n == n.parent.right && n.parent == n.grandparent().right)
self.rotateLeft(n.grandparent())
else
#  Fail case
print("\n Fail insertCase5 \n")
end

end

end

def inorderSuccessor(n)
if (n == nil)
#  Fail case
print("\n Fail Inorder Successor is NULL\n")
return nil
end

while (n.right != nil)
n = n.right
end

return n
end

def replaceNode(oldn, newn)
if (oldn.parent == nil)
self.root = newn
if (self.root != nil)
self.root.color = Color::BLACK
end

else
if (oldn == oldn.parent.left)
oldn.parent.left = newn
else
oldn.parent.right = newn
end

end

if (newn != nil)
newn.parent = oldn.parent
end

end

def deleteCase6(n)
n.sibling().color = self.nodeColor(n.parent)
n.parent.color = Color::BLACK
if (n == n.parent.left)
if (self.nodeColor(n.sibling().right) == Color::RED)
n.sibling().right.color = Color::BLACK
self.rotateLeft(n.parent)
else
#  Fail case
print("\n Fail delete case 6 : sibling right node is BLACK \n")
end

else
if (self.nodeColor(n.sibling().left) == Color::RED)
n.sibling().left.color = Color::BLACK
self.rotateRight(n.parent)
else
#  Fail case
print("\n Fail delete case 6 : sibling left node is BLACK \n")
end

end

end

def deleteCase5(n)
if (n == n.parent.left && self.nodeColor(n.sibling()) == Color::BLACK && self.nodeColor(n.sibling().left) == Color::RED && self.nodeColor(n.sibling().right) == Color::BLACK)
n.sibling().color = Color::RED
n.sibling().left.color = Color::BLACK
self.rotateRight(n.sibling())
elsif(n == n.parent.right && self.nodeColor(n.sibling()) == Color::BLACK && self.nodeColor(n.sibling().right) == Color::RED && self.nodeColor(n.sibling().left) == Color::BLACK)
n.sibling().color = Color::RED
n.sibling().right.color = Color::BLACK
self.rotateLeft(n.sibling())
end

self.deleteCase6(n)
end

def deleteCase4(n)
if (self.nodeColor(n.parent) == Color::RED && self.nodeColor(n.sibling()) == Color::BLACK && self.nodeColor(n.sibling().left) == Color::BLACK && self.nodeColor(n.sibling().right) == Color::BLACK)
n.sibling().color = Color::RED
n.parent.color = Color::BLACK
else
self.deleteCase5(n)
end

end

def deleteCase3(n)
if (self.nodeColor(n.parent) == Color::BLACK && self.nodeColor(n.sibling()) == Color::BLACK && self.nodeColor(n.sibling().left) == Color::BLACK && self.nodeColor(n.sibling().right) == Color::BLACK)
n.sibling().color = Color::RED
self.deleteCase1(n.parent)
else
self.deleteCase4(n)
end

end

def deleteCase2(n)
if (self.nodeColor(n.sibling()) == Color::RED)
n.parent.color = Color::RED
n.sibling().color = Color::BLACK
if (n == n.parent.left)
self.rotateLeft(n.parent)
else
self.rotateRight(n.parent)
end

end

self.deleteCase3(n)
end

def deleteCase1(n)
if (n.parent == nil)
#  Delete root node
return
else
self.deleteCase2(n)
end

end

#  This is handle the request to delete node in tree
def deleteNode(key)
# First find the deleted node
n = self.findNode(key)
if (n == nil)
#  When key node are not exists
return
end

child = nil
if (n.left != nil && n.right != nil)
child = self.inorderSuccessor(n.left)
n.key = child.key
n = child
end

if (n.left == nil || n.right == nil)
if (n.left == nil)
child = n.right
else
child = n.left
end

end

if (self.nodeColor(n) == Color::BLACK)
n.color = self.nodeColor(child)
self.deleteCase1(n)
end

self.replaceNode(n, child)
self.verifyProperties()
print("\n\nAfter Delete TreeNode [", key ,"]")
self.printTree()
end

# Print tree elements in preorder traversal
def preorder(n)
if (n == nil)
return
end

# display node key
print("  ", n.key)
#  recursively visiting left and right subtree
self.preorder(n.left)
self.preorder(n.right)
end

# Print tree elements in inorder traversal
def inorder(n)
if (n == nil)
return
end

self.inorder(n.left)
# display node key
print("  ", n.key)
self.inorder(n.right)
end

# Print tree elements in preorder traversal
def postorder(n)
if (n == nil)
return
end

#  recursively visiting left and right subtree
self.postorder(n.left)
self.postorder(n.right)
# display node key
print("  ", n.key)
end

#  Handles the request to print tree nodes
def printTree()
if (root == nil)
print("\nEmpty Tree\n\n")
return
end

print("\nInorder\n")
self.inorder(root)
print("\nPreorder\n")
self.preorder(root)
print("\nPostOrder\n")
self.postorder(root)
end

end

def main()
tree = RBTree.new()
tree.insert(18)
tree.insert(5)
tree.insert(1)
tree.insert(11)
tree.insert(21)
tree.insert(6)
tree.insert(9)
tree.insert(7)
tree.insert(30)
tree.insert(40)
tree.printTree()
#
#       Constructed Red-Black Tree
#             9
#          /     \
#         5       18
#        / \     /   \
#       1   6   11   30
#            \      /   \
#             7    21    40
#

tree.deleteNode(1)
#
#       After Delete Node 1
#       ---------------------
#             9
#           /   \
#          6     18
#        /  \    / \
#       5    7  11   30
#                   /  \
#                  21   40
#

tree.deleteNode(5)
#
#       After Delete Node 5
#       ---------------------
#             9
#           /    \
#          6     18
#           \    /  \
#            7  11   30
#                   /  \
#                  21   40
#

tree.deleteNode(9)
#
#       After Delete Node 9
#       ---------------------
#             7
#           /   \
#          6      18
#                /   \
#               11   30
#                   /   \
#                  21    40
#

tree.deleteNode(18)
#
#       After Delete Node 18
#       -------------------
#              7
#            /   \
#           6     30
#                /  \
#               11   40
#                 \
#                  21
#

print("\n")
end

main()``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7
``````
``````/*
Scala program for
Red Black tree node deletion
*/
object Color
{
val RED = 0
val BLACK = 1
}
// Define Tree Node
class TreeNode(var key: Int , var left: TreeNode , var right: TreeNode , var parent: TreeNode , var color: Int)
{
def this(key: Int, nodeColor: Int)
{
this(key, null, null, null, nodeColor);
}
def uncle(): TreeNode = {
if (parent == null)
{
//  Fail case
print("Fail Uncle has no parent\n");
return null;
}
else if (parent.parent == null)
{
//  Fail case
print("Fail Children of root have no uncle\n");
return null;
}
return parent.sibling();
}
def sibling(): TreeNode = {
if (parent == null)
{
//  Fail case
print("Fail Subling has no parent\n");
return null;
}
else
{
if (this == parent.left)
{
return parent.right;
}
else
{
return parent.left;
}
}
}
def grandparent(): TreeNode = {
if (parent == null || parent.parent == null)
{
//  Fail case
print("Fail Grandparent has no parent\n");
return null;
}
return parent.parent;
}
}
class RBTree(var root: TreeNode)
{
def this()
{
this(null);
this.verifyProperties();
}
def verifyProperties(): Unit = {
verifyProperty1(root);
verifyProperty2(root);
verifyProperty4(root);
verifyProperty5(root);
}
def verifyProperty1(n: TreeNode): Unit = {
if (!(nodeColor(n) == Color.RED || nodeColor(n) == Color.BLACK))
{
//  Fail case
print(" Fail case verifyProperty1 \n");
return;
}
if (n == null)
{
return;
}
this.verifyProperty1(n.left);
this.verifyProperty1(n.right);
}
def verifyProperty2(n: TreeNode): Unit = {
if (nodeColor(n) != Color.BLACK)
{
//  Fail case
print(" Fail case verifyProperty2 \n");
}
}
def nodeColor(n: TreeNode): Int = {
if (n == null)
{
return Color.BLACK;
}
else
{
return n.color;
}
}
def verifyProperty4(n: TreeNode): Unit = {
if (this.nodeColor(n) == Color.RED)
{
if (this.nodeColor(n.left) != Color.BLACK
|| this.nodeColor(n.right) != Color.BLACK
|| this.nodeColor(n.parent) != Color.BLACK)
{
//  Fail case
print("Fail Property of verifyProperty4\n");
}
}
if (n == null)
{
return;
}
this.verifyProperty4(n.left);
this.verifyProperty4(n.right);
}
def verifyProperty5(root: TreeNode): Unit = {
verifyProperty5Helper(root, 0, -1);
}
def verifyProperty5Helper(n: TreeNode, black: Int, pathBlack: Int): Int = {
var blackCount: Int = black;
var pathBlackCount: Int = pathBlack;
if (this.nodeColor(n) == Color.BLACK)
{
blackCount += 1;
}
if (n == null)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
//  Fail case
print("Fail Property of verifyProperty5Helper\n");
}
return pathBlackCount;
}
pathBlackCount = this.verifyProperty5Helper(n.left, blackCount, pathBlackCount);
pathBlackCount = this.verifyProperty5Helper(n.right, blackCount, pathBlackCount);
return pathBlackCount;
}
def findNode(key: Int): TreeNode = {
var n: TreeNode = root;
while (n != null)
{
if (key == n.key)
{
return n;
}
else if (key < n.key)
{
n = n.left;
}
else
{
n = n.right;
}
}
return n;
}
def rotateLeft(n: TreeNode): Unit = {
var r: TreeNode = n.right;
replaceNode(n, r);
n.right = r.left;
if (r.left != null)
{
r.left.parent = n;
}
r.left = n;
n.parent = r;
}
def rotateRight(n: TreeNode): Unit = {
var l: TreeNode = n.left;
replaceNode(n, l);
n.left = l.right;
if (l.right != null)
{
l.right.parent = n;
}
l.right = n;
n.parent = l;
}
def insert(key: Int): Unit = {
var insertedNode: TreeNode = new TreeNode(key, Color.RED);
if (root == null)
{
root = insertedNode;
}
else
{
var n: TreeNode = root;
var status = true;
while (status)
{
if (key < n.key)
{
if (n.left == null)
{
n.left = insertedNode;
status = false;
}
else
{
n = n.left;
}
}
else if (key > n.key)
{
if (n.right == null)
{
n.right = insertedNode;
status = false;
}
else
{
n = n.right;
}
}
else
{
return;
}
}
insertedNode.parent = n;
}
insertCase1(insertedNode);
this.verifyProperties();
}
def insertCase1(n: TreeNode): Unit = {
if (n.parent == null)
{
n.color = Color.BLACK;
}
else
{
insertCase2(n);
}
}
def insertCase2(n: TreeNode): Unit = {
if (this.nodeColor(n.parent) == Color.BLACK)
//  Tree is still valid
{
return;
}
else
{
insertCase3(n);
}
}
def insertCase3(n: TreeNode): Unit = {
if (this.nodeColor(n.uncle()) == Color.RED)
{
n.parent.color = Color.BLACK;
n.uncle().color = Color.BLACK;
n.grandparent().color = Color.RED;
this.insertCase1(n.grandparent());
}
else
{
insertCase4(n);
}
}
def insertCase4(k: TreeNode): Unit = {
var n: TreeNode = k;
if (n == n.parent.right && n.parent == n.grandparent().left)
{
this.rotateLeft(n.parent);
n = n.left;
}
else if (n == n.parent.left && n.parent == n.grandparent().right)
{
this.rotateRight(n.parent);
n = n.right;
}
insertCase5(n);
}
def insertCase5(n: TreeNode): Unit = {
n.parent.color = Color.BLACK;
n.grandparent().color = Color.RED;
if (n == n.parent.left && n.parent == n.grandparent().left)
{
this.rotateRight(n.grandparent());
}
else
{
if (n == n.parent.right && n.parent == n.grandparent().right)
{
this.rotateLeft(n.grandparent());
}
else
{
//  Fail case
print("\n Fail insertCase5 \n");
}
}
}
def inorderSuccessor(k: TreeNode): TreeNode = {
var n: TreeNode = k;
if (n == null)
{
//  Fail case
print("\n Fail Inorder Successor is NULL\n");
return null;
}
while (n.right != null)
{
n = n.right;
}
return n;
}
def replaceNode(oldn: TreeNode, newn: TreeNode): Unit = {
if (oldn.parent == null)
{
this.root = newn;
if (this.root != null)
{
this.root.color = Color.BLACK;
}
}
else
{
if (oldn == oldn.parent.left)
{
oldn.parent.left = newn;
}
else
{
oldn.parent.right = newn;
}
}
if (newn != null)
{
newn.parent = oldn.parent;
}
}
def deleteCase6(n: TreeNode): Unit = {
n.sibling().color = this.nodeColor(n.parent);
n.parent.color = Color.BLACK;
if (n == n.parent.left)
{
if (this.nodeColor(n.sibling().right) == Color.RED)
{
n.sibling().right.color = Color.BLACK;
this.rotateLeft(n.parent);
}
else
{
//  Fail case
print("\n Fail delete case 6 : sibling right node is BLACK \n");
}
}
else
{
if (this.nodeColor(n.sibling().left) == Color.RED)
{
n.sibling().left.color = Color.BLACK;
this.rotateRight(n.parent);
}
else
{
//  Fail case
print("\n Fail delete case 6 : sibling left node is BLACK \n");
}
}
}
def deleteCase5(n: TreeNode): Unit = {
if (n == n.parent.left && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().left) == Color.RED && this.nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().left.color = Color.BLACK;
this.rotateRight(n.sibling());
}
else if (n == n.parent.right && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().right) == Color.RED && this.nodeColor(n.sibling().left) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.sibling().right.color = Color.BLACK;
this.rotateLeft(n.sibling());
}
this.deleteCase6(n);
}
def deleteCase4(n: TreeNode): Unit = {
if (this.nodeColor(n.parent) == Color.RED && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().left) == Color.BLACK && this.nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
n.parent.color = Color.BLACK;
}
else
{
this.deleteCase5(n);
}
}
def deleteCase3(n: TreeNode): Unit = {
if (this.nodeColor(n.parent) == Color.BLACK && this.nodeColor(n.sibling()) == Color.BLACK && this.nodeColor(n.sibling().left) == Color.BLACK && this.nodeColor(n.sibling().right) == Color.BLACK)
{
n.sibling().color = Color.RED;
deleteCase1(n.parent);
}
else
{
this.deleteCase4(n);
}
}
def deleteCase2(n: TreeNode): Unit = {
if (this.nodeColor(n.sibling()) == Color.RED)
{
n.parent.color = Color.RED;
n.sibling().color = Color.BLACK;
if (n == n.parent.left)
{
this.rotateLeft(n.parent);
}
else
{
this.rotateRight(n.parent);
}
}
this.deleteCase3(n);
}
def deleteCase1(n: TreeNode): Unit = {
if (n.parent == null)
//  Delete root node
{
return;
}
else
{
this.deleteCase2(n);
}
}
//  This is handle the request to delete node in tree
def deleteNode(key: Int): Unit = {
// First find the deleted node
var n: TreeNode = this.findNode(key);
if (n == null)
{
//  When key node are not exists
return;
}
var child: TreeNode = null;
if (n.left != null && n.right != null)
{
child = this.inorderSuccessor(n.left);
n.key = child.key;
n = child;
}
if (n.left == null || n.right == null)
{
if (n.left == null)
{
child = n.right;
}
else
{
child = n.left;
}
}
if (this.nodeColor(n) == Color.BLACK)
{
n.color = this.nodeColor(child);
this.deleteCase1(n);
}
this.replaceNode(n, child);
this.verifyProperties();
print("\n\nAfter Delete TreeNode [" + key + "]");
printTree();
}
// Print tree elements in preorder traversal
def preorder(n: TreeNode): Unit = {
if (n == null)
{
return;
}
// display node key
print("  " + n.key);
//  recursively visiting left and right subtree
this.preorder(n.left);
this.preorder(n.right);
}
// Print tree elements in inorder traversal
def inorder(n: TreeNode): Unit = {
if (n == null)
{
return;
}
this.inorder(n.left);
// display node key
print("  " + n.key);
this.inorder(n.right);
}
// Print tree elements in preorder traversal
def postorder(n: TreeNode): Unit = {
if (n == null)
{
return;
}
//  recursively visiting left and right subtree
this.postorder(n.left);
this.postorder(n.right);
// display node key
print("  " + n.key);
}
//  Handles the request to print tree nodes
def printTree(): Unit = {
if (root == null)
{
print("\nEmpty Tree\n\n");
return;
}
print("\nInorder\n");
this.inorder(root);
print("\nPreorder\n");
this.preorder(root);
print("\nPostOrder\n");
this.postorder(root);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: RBTree = new RBTree();
tree.insert(18);
tree.insert(5);
tree.insert(1);
tree.insert(11);
tree.insert(21);
tree.insert(6);
tree.insert(9);
tree.insert(7);
tree.insert(30);
tree.insert(40);
tree.printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
tree.deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
tree.deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
tree.deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
tree.deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
print("\n");
}
}``````

#### Output

``````Inorder
1  5  6  7  9  11  18  21  30  40
Preorder
9  5  1  6  7  18  11  30  21  40
PostOrder
1  7  6  5  11  21  40  30  18  9

After Delete TreeNode [1]
Inorder
5  6  7  9  11  18  21  30  40
Preorder
9  6  5  7  18  11  30  21  40
PostOrder
5  7  6  11  21  40  30  18  9

After Delete TreeNode [5]
Inorder
6  7  9  11  18  21  30  40
Preorder
9  6  7  18  11  30  21  40
PostOrder
7  6  11  21  40  30  18  9

After Delete TreeNode [9]
Inorder
6  7  11  18  21  30  40
Preorder
7  6  18  11  30  21  40
PostOrder
6  11  21  40  30  18  7

After Delete TreeNode [18]
Inorder
6  7  11  21  30  40
Preorder
7  6  30  11  21  40
PostOrder
6  21  11  40  30  7``````
``````/*
Swift 4 program for
Red Black tree node deletion
*/
class Color
{
class var RED: Int {return 0};
class var BLACK: Int {return 1};
}
// Define Tree Node
class TreeNode
{
var key: Int;
var left: TreeNode? ;
var right: TreeNode? ;
var parent: TreeNode? ;
var color: Int ;
init(_ key: Int, _ nodeColor: Int )
{
self.key = key;
self.color = nodeColor;
self.left = nil;
self.right = nil;
self.parent = nil;
}
func uncle()->TreeNode?
{
if (self.parent == nil)
{
//  Fail case
print("Fail Uncle has no parent\n", terminator: "");
return nil;
}
else if (self.parent!.parent == nil)
{
//  Fail case
print("Fail Children of root have no uncle\n", terminator: "");
return nil;
}
return self.parent!.sibling();
}
func sibling()->TreeNode?
{
if (self.parent == nil)
{
//  Fail case
print("Fail Subling has no parent\n", terminator: "");
return nil;
}
else
{
if (self === self.parent!.left)
{
return self.parent!.right;
}
else
{
return self.parent!.left;
}
}
}
func grandparent()->TreeNode?
{
if (self.parent == nil || self.parent!.parent == nil)
{
//  Fail case
print("Fail Grandparent has no parent\n", terminator: "");
return nil;
}
return self.parent!.parent;
}
}
class RBTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
self.verifyProperties();
}
func verifyProperties()
{
verifyProperty1(self.root);
verifyProperty2(self.root);
verifyProperty4(self.root);
verifyProperty5(self.root);
}
func verifyProperty1(_ n: TreeNode? )
{
if (!(nodeColor(n) == Color.RED || nodeColor(n) == Color.BLACK))
{
//  Fail case
print(" Fail case verifyProperty1 \n", terminator: "");
return;
}
if (n == nil)
{
return;
}
self.verifyProperty1(n!.left);
self.verifyProperty1(n!.right);
}
func verifyProperty2(_ n: TreeNode? )
{
if (nodeColor(n) != Color.BLACK)
{
//  Fail case
print(" Fail case verifyProperty2 \n", terminator: "");
}
}
func nodeColor(_ n: TreeNode? )->Int
{
if (n == nil)
{
return Color.BLACK;
}
else
{
return n!.color;
}
}
func verifyProperty4(_ n: TreeNode? )
{
if (self.nodeColor(n) == Color.RED)
{
if (self.nodeColor(n!.left) != Color.BLACK || self.nodeColor(n!.right) != Color.BLACK || self.nodeColor(n!.parent) != Color.BLACK)
{
//  Fail case
print("Fail Property of verifyProperty4\n", terminator: "");
}
}
if (n == nil)
{
return;
}
self.verifyProperty4(n!.left);
self.verifyProperty4(n!.right);
}
func verifyProperty5(_ root: TreeNode? )
{
let _ = self.verifyProperty5Helper(root, 0, -1);
}
func verifyProperty5Helper(_ n: TreeNode? , _ black :  Int, _ pathBlack:  Int)->Int
{
var pathBlackCount:  Int = pathBlack;
var blackCount :  Int = black;
if (self.nodeColor(n) == Color.BLACK)
{
blackCount += 1;
}
if (n == nil)
{
if (pathBlackCount == -1)
{
pathBlackCount = blackCount;
}
else if (blackCount != pathBlackCount)
{
//  Fail case
print("Fail Property of verifyProperty5Helper\n", terminator: "");
}
return pathBlackCount;
}
pathBlackCount = self.verifyProperty5Helper(n!.left, blackCount, pathBlackCount);
pathBlackCount = self.verifyProperty5Helper(n!.right, blackCount, pathBlackCount);
return pathBlackCount;
}
func findNode(_ key: Int)->TreeNode?
{
var n: TreeNode? = self.root;
while (n != nil)
{
if (key == n!.key)
{
return n;
}
else if (key < n!.key)
{
n = n!.left;
}
else
{
n = n!.right;
}
}
return n;
}
func rotateLeft(_ n: TreeNode? )
{
let r: TreeNode? = n!.right;
replaceNode(n, r);
n!.right = r!.left;
if (r!.left != nil)
{
r!.left!.parent = n;
}
r!.left = n;
n!.parent = r;
}
func rotateRight(_ n: TreeNode? )
{
let l: TreeNode? = n!.left;
replaceNode(n, l);
n!.left = l!.right;
if (l!.right != nil)
{
l!.right!.parent = n;
}
l!.right = n;
n!.parent = l;
}
func insert(_ key: Int)
{
let insertedNode: TreeNode? = TreeNode(key, Color.RED);
if (self.root == nil)
{
self.root = insertedNode;
}
else
{
var n: TreeNode? = self.root;
while (true)
{
if (key < n!.key)
{
if (n!.left == nil)
{
n!.left = insertedNode;
break;
}
else
{
n = n!.left;
}
}
else if (key > n!.key)
{
if (n!.right == nil)
{
n!.right = insertedNode;
break;
}
else
{
n = n!.right;
}
}
else
{
return;
}
}
insertedNode!.parent = n;
}
insertCase1(insertedNode);
self.verifyProperties();
}
func insertCase1(_ n: TreeNode? )
{
if (n!.parent == nil)
{
n?.color = Color.BLACK;
}
else
{
self.insertCase2(n);
}
}
func insertCase2(_ n: TreeNode? )
{
if (self.nodeColor(n!.parent) == Color.BLACK)
//  Tree is still valid
{
return;
}
else
{
self.insertCase3(n);
}
}
func insertCase3(_ n: TreeNode?)
{
if (self.nodeColor(n?.uncle()) == Color.RED)
{
n?.parent!.color = Color.BLACK;
n?.uncle()!.color = Color.BLACK;
n?.grandparent()!.color = Color.RED;
self.insertCase1(n?.grandparent());
}
else
{
self.insertCase4(n);
}
}
func insertCase4(_ node: TreeNode?)
{
var n: TreeNode? = node;
if (n === n?.parent!.right && n?.parent === n?.grandparent()!.left)
{
self.rotateLeft(n?.parent);
n = n?.left;
}
else if (n === n?.parent!.left && n?.parent === n?.grandparent()!.right)
{
self.rotateRight(n?.parent);
n = n?.right;
}
self.insertCase5(n);
}
func insertCase5(_ n: TreeNode?)
{
n?.parent!.color = Color.BLACK;
n?.grandparent()!.color = Color.RED;
if (n === n?.parent!.left && n?.parent === n?.grandparent()!.left)
{
self.rotateRight(n?.grandparent());
}
else
{
if (n === n?.parent!.right && n?.parent === n?.grandparent()!.right)
{
self.rotateLeft(n?.grandparent());
}
else
{
//  Fail case
print("\n Fail insertCase5 \n", terminator: "");
}
}
}
func inorderSuccessor(_ node: TreeNode? )->TreeNode?
{
var n: TreeNode? = node;
if (n == nil)
{
//  Fail case
print("\n Fail Inorder Successor is NULL\n", terminator: "");
return nil;
}
while (n!.right != nil)
{
n = n!.right;
}
return n;
}
func replaceNode(_ oldn: TreeNode? , _ newn : TreeNode? )
{
if (oldn!.parent == nil)
{
self.root = newn;
if (self.root != nil)
{
self.root!.color = Color.BLACK;
}
}
else
{
if (oldn === oldn!.parent!.left)
{
oldn!.parent!.left = newn;
}
else
{
oldn!.parent!.right = newn;
}
}
if (newn != nil)
{
newn!.parent = oldn!.parent;
}
}
func deleteCase6(_ n: TreeNode?)
{
n?.sibling()!.color = self.nodeColor(n?.parent);
n?.parent!.color = Color.BLACK;
if (n === n?.parent!.left)
{
if (self.nodeColor(n?.sibling()!.right) == Color.RED)
{
n?.sibling()!.right!.color = Color.BLACK;
self.rotateLeft(n?.parent);
}
else
{
//  Fail case
print("\n Fail delete case 6 : sibling right node is BLACK \n", terminator: "");
}
}
else
{
if (self.nodeColor(n?.sibling()!.left) == Color.RED)
{
n?.sibling()!.left!.color = Color.BLACK;
self.rotateRight(n?.parent);
}
else
{
//  Fail case
print("\n Fail delete case 6 : sibling left node is BLACK \n", terminator: "");
}
}
}
func deleteCase5(_ n: TreeNode?)
{
if (n === n?.parent!.left
&& self.nodeColor(n?.sibling()) == Color.BLACK
&& self.nodeColor(n?.sibling()!.left) == Color.RED
&& self.nodeColor(n?.sibling()!.right) == Color.BLACK)
{
n?.sibling()!.color = Color.RED;
n?.sibling()!.left!.color = Color.BLACK;
self.rotateRight(n?.sibling());
}
else if (n === n?.parent!.right
&& self.nodeColor(n?.sibling()) == Color.BLACK
&& self.nodeColor(n?.sibling()!.right) == Color.RED
&& self.nodeColor(n?.sibling()!.left) == Color.BLACK)
{
n?.sibling()!.color = Color.RED;
n?.sibling()!.right!.color = Color.BLACK;
self.rotateLeft(n?.sibling());
}
self.deleteCase6(n);
}
func deleteCase4(_ n: TreeNode?)
{
if (self.nodeColor(n?.parent) == Color.RED
&& self.nodeColor(n?.sibling()) == Color.BLACK
&& self.nodeColor(n?.sibling()!.left) == Color.BLACK
&& self.nodeColor(n?.sibling()!.right) == Color.BLACK)
{
n?.sibling()!.color = Color.RED;
n?.parent!.color = Color.BLACK;
}
else
{
self.deleteCase5(n);
}
}
func deleteCase3(_ n: TreeNode?)
{
if (self.nodeColor(n?.parent) == Color.BLACK
&& self.nodeColor(n?.sibling()) == Color.BLACK
&& self.nodeColor(n?.sibling()!.left) == Color.BLACK
&& self.nodeColor(n?.sibling()!.right) == Color.BLACK)
{
n?.sibling()!.color = Color.RED;
deleteCase1(n?.parent);
}
else
{
self.deleteCase4(n);
}
}
func deleteCase2(_ n: TreeNode?)
{
if (self.nodeColor(n?.sibling()) == Color.RED)
{
n?.parent!.color = Color.RED;
n?.sibling()!.color = Color.BLACK;
if (n === n?.parent!.left)
{
self.rotateLeft(n?.parent);
}
else
{
self.rotateRight(n?.parent);
}
}
self.deleteCase3(n);
}
func deleteCase1(_ n: TreeNode? )
{
if (n!.parent == nil)
//  Delete root node
{
return;
}
else
{
self.deleteCase2(n);
}
}
//  This is handle the request to delete node in tree
func deleteNode(_ key: Int)
{
// First find the deleted node
var n: TreeNode? = self.findNode(key);
if (n == nil)
{
//  When key node are not exists
return;
}
var child: TreeNode? = nil;
if (n!.left != nil && n!.right != nil)
{
child = self.inorderSuccessor(n!.left);
n!.key = child!.key;
n = child;
}
if (n!.left == nil || n!.right == nil)
{
if (n!.left == nil)
{
child = n!.right;
}
else
{
child = n!.left;
}
}
if (self.nodeColor(n) == Color.BLACK)
{
n!.color = self.nodeColor(child);
self.deleteCase1(n);
}
self.replaceNode(n, child);
self.verifyProperties();
print("\n\nAfter Delete TreeNode [", key ,"]", terminator: "");
printTree();
}
// Print tree elements in preorder traversal
func preorder(_ n: TreeNode? )
{
if (n == nil)
{
return;
}
// display node key
print("  ", n!.key, terminator: "");
//  recursively visiting left and right subtree
self.preorder(n!.left);
self.preorder(n!.right);
}
// Print tree elements in inorder traversal
func inorder(_ n: TreeNode? )
{
if (n == nil)
{
return;
}
self.inorder(n!.left);
// display node key
print("  ", n!.key, terminator: "");
self.inorder(n!.right);
}
// Print tree elements in preorder traversal
func postorder(_ n: TreeNode? )
{
if (n == nil)
{
return;
}
//  recursively visiting left and right subtree
self.postorder(n!.left);
self.postorder(n!.right);
// display node key
print("  ", n!.key, terminator: "");
}
//  Handles the request to print tree nodes
func printTree()
{
if (self.root == nil)
{
print("\nEmpty Tree\n\n", terminator: "");
return;
}
print("\nInorder\n", terminator: "");
self.inorder(self.root);
print("\nPreorder\n", terminator: "");
self.preorder(self.root);
print("\nPostOrder\n", terminator: "");
self.postorder(self.root);
}
}
func main()
{
let tree: RBTree = RBTree();
tree.insert(18);
tree.insert(5);
tree.insert(1);
tree.insert(11);
tree.insert(21);
tree.insert(6);
tree.insert(9);
tree.insert(7);
tree.insert(30);
tree.insert(40);
tree.printTree();
/*
Constructed Red-Black Tree

9
/     \
5       18
/ \     /   \
1   6   11   30
\      /   \
7    21    40
*/
tree.deleteNode(1);
/*
After Delete Node 1
---------------------

9
/   \
6     18
/  \    / \
5    7  11   30
/  \
21   40
*/
tree.deleteNode(5);
/*
After Delete Node 5
---------------------

9
/    \
6     18
\    /  \
7  11   30
/  \
21   40
*/
tree.deleteNode(9);
/*
After Delete Node 9
---------------------

7
/   \
6      18
/   \
11   30
/   \
21    40
*/
tree.deleteNode(18);
/*
After Delete Node 18
-------------------
7
/   \
6     30
/  \
11   40
\
21
*/
print("\n", terminator: "");
}
main();``````

#### Output

``````Inorder
1   5   6   7   9   11   18   21   30   40
Preorder
9   5   1   6   7   18   11   30   21   40
PostOrder
1   7   6   5   11   21   40   30   18   9

After Delete TreeNode [ 1 ]
Inorder
5   6   7   9   11   18   21   30   40
Preorder
9   6   5   7   18   11   30   21   40
PostOrder
5   7   6   11   21   40   30   18   9

After Delete TreeNode [ 5 ]
Inorder
6   7   9   11   18   21   30   40
Preorder
9   6   7   18   11   30   21   40
PostOrder
7   6   11   21   40   30   18   9

After Delete TreeNode [ 9 ]
Inorder
6   7   11   18   21   30   40
Preorder
7   6   18   11   30   21   40
PostOrder
6   11   21   40   30   18   7

After Delete TreeNode [ 18 ]
Inorder
6   7   11   21   30   40
Preorder
7   6   30   11   21   40
PostOrder
6   21   11   40   30   7``````

## Time Complexity

The time complexity of deleting a node in a Red-Black Tree is O(log n), ensuring efficient and balanced operations.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.