This post will outline the procedure for deleting an element from a Red-Black Tree. I have a separate post for insertion. This post will not focus on why all of the different cases are needed and why they work, but I may be following up with a separate post to further explain.

For a complete description of what a Red-Black tree is (including some terminology I will be using), see my **Red-Black Tree Introduction**.

You can view my complete C++ deletion code or the complete implementation of a Red-Black Tree on GitHub.

### Deletion

To delete a node, first determine the node that will be removed, and its child (or a black empty node if it doesn’t have a child) using standard BST deletion. Then, you will need to balance the tree.

If the removed node or its child is red, will just need to set the child that is replacing it to be black to rebalance the tree.

Otherwise, let the child be the current node, and it is now double black (due to merging the two black nodes together). This must be fixed with the **double black** rules:

**Node is the root:**change the node to just be black. Changing the root from double black to black will just reduce the number of black nodes to every leaf by 1.**Sibling of node is red:**rotate on the parent in the direction of the double black node. Then, color the sibling (which will now be the double black nodes grandparent)**black**, and the parent of node**red**. Then, you just need re-run the double black rules on the still double black node.**Sibling has one red child**Like insertion’s grandparent rotations, this is symmetric, based on the orientation of the sibling and its red child compared to the parent. Let**RedC**be the child of the sibling that is**red**. If both are, then it doesn’t matter which of the sibling’s children you choose.**Sibling is left child of parent:**Will ultimately do a**right rotation**on parent to shift it to the right side of the subtree.**RedC is right child of sibling:**RedC is to the**left right**of parent, so need to do a**left rotation**on sibling before a**right rotation**on parent:

**RedC is left child of sibling:**RedC is to the**left left**of parent, so just need to do a**right rotation**on the parent:

**Sibling is right child of parent:**Will ultimately do a**left rotation**on parent to shift it the left side of the tree.**RedC is left child of sibling:**RedC is to the**right left**of parent, so need to do a**right rotation**on sibling before a**left rotation**on parent:

**RedC is right child of sibling:**RedC is to the**right right**of parent, so just need to do a**left rotation**on parent:

Once the rotations are completed, change the color of the

**new subtree owner**(the new parent for the parent of the double black node) to the**color of the double black nodes parent**. Then, change the color of both children of the subtree owner to**black**.**Sibling and its children are black:**‘shift the black’ up from the sibling by changing the sibling to**red**.

If their parent is red set it to**black**.

Otherwise, will change the parent to be**double black**, and then recursively handle the double black case.

The original sources I looked at to find out how to implement deletion in a Red Black tree are at geeksforgeeks.org and a video on YouTube.

I have example code for deletion in C++, and the complete Red Black Tree C++ implementation is available on GitHub. I have also created a post on how to do insertion in a Red Black Tree.