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 40We'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:
- Identify the node to be deleted.
- If the node has two children, replace it with its inorder successor (a node with the smallest key in its right subtree).
- Determine the color of the replacement node.
- 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:
print "Node not found"
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
deleteNodefunction identifies the node to be deleted and proceeds with the deletion process, maintaining properties. - The
deleteCase1function handles the initial case when the node to be deleted is the root. - The subsequent
deleteCasefunctions 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
printf("\n Delete TreeNode %d Not Found \n",key);
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();
// Add tree element
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
System.out.print("\n Delete TreeNode " + key + " Not Found \n");
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();
//Add tree element
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();
// Add tree element
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
Console.Write("\n Delete TreeNode " + key + " Not Found \n");
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();
// Add tree element
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
echo "\n Delete TreeNode ". $key ." Not Found \n";
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();
// Add tree element
$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
process.stdout.write("\n Delete TreeNode " + key + " Not Found \n");
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();
// Add tree element
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()
# Add tree element
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_reader :root
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
print("\n Delete TreeNode ", key ," Not Found \n")
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()
# Add tree element
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
print("\n Delete TreeNode " + key + " Not Found \n");
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();
// Add tree element
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
print("\n Delete TreeNode ", key ," Not Found \n", terminator: "");
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();
// Add tree element
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 7Time Complexity
The time complexity of deleting a node in a Red-Black Tree is O(log n), ensuring efficient and balanced operations.
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.
New Comment