This page demonstrates how to remove and then fix the violations caused by removing a node from a Red Black Tree

0 Children (Double-Black accounting)

• Perform standard BST remove algorithm.
• If the node being removed is red, simply remove it
• If the node being removed is black, temporarily count it as double black (black height of two):

• Black Sibling (+Null/Black Niece(s))

• Red Parent
• Subtract 1 from both the double black and its sibling. Then add 1 to the parent of the double black.
• Black Parent
• Subtract 1 from both the double black and its sibling. Then add 1 to the parent of the double black.
• Notice that the parent has now become a double black. Since we only made the problem move higher up in the tree, we must use the appropiate case described on this page to fix the new problem.

• Black Sibling (+Red Niece(s))

• If the red niece forms a line with the double black's parent and sibling (sibling and niece are on the same side):
• Rotate and swap colors of double black's parent and sibling.
• Change double black to black and change the red node to black.
• If the red niece forms a zig-zag with the double black's parent and sibling (sibling and niece are not on the same side):
• Rotate and swap the colors of the sibling and niece first to form a line
• Then, rotate and swap colors of double black's parent and sibling.
• Change double black to black and change the red node to black.

• Red Sibling (-Parent must be black)

• Rotate and swap the colors of the double black's parent and sibling.
• Notice that the rotation has made double black's sibling black, you can fix this by using one of the above cases.
• If necessary, change the root to black.

This is an image you can refer to for removing a black node with no children from a Red Black Tree:

1 Child

• Perform standard BST remove algorithm.
• Since this can only happen if the node being removed is black and its one child is red, simply remove the black node by replacing the red child node with the black node and change the child's color to black.
• If necessary, change the root to black.

2 Children

• Perform standard BST remove algorithm.
• The node deleted is replaced by its successor or predecessor, keeping the node being removed's color intact.

(Note: After you replace the node with its successor/predecessor you remove the sucessor/prdecessor from its old location. Since you might be removing a node with a children or without, you will need to make sure you are not violating the red black tree properties by using one of the appropiate cases described above.

• If necessary, change the root to black.

If you would like to learn more about Red Black Tree's Remove Algorithm, you can read more about it here.