Red Black tree node deletion

Here given code implementation process.

// 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   7


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







© 2021, kalkicode.com, All rights reserved