Painless Red-Black Tree Implementation – Deletion

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.
Just change the child to be red.

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:

  1. 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.
  2. 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 is red and the left child of the parent. Will do a right rotate on parent, then change the original siblings color to black while changing color of original parent to red. Still need to handle double black node.

    Sibling is red and the right child of the parent. Will do a left rotate on parent, then change the original siblings color to black while changing color of original parent to red. Still need to handle double black node.

  3. 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:
        Left rotate on sibling for the intermediate step of Left Right case. Will have RedC be the child of parent, with the original sibling becoming the left child of RedC.
        Right rotate on parent for the final step of Left Right case. Will end up with RedC being the root of the subtree (keeping the color of what was originally the parent) while the sibling is its left child and parent is its right child.
      • 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:
        Right shift on parent for Left Left case. Will have the sibling as the new root of the subtree, with its color being that of the original parent, while the parent and RedC become its black children.
    • 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:
        Right rotate on sibling for the intermediate step of Right Left case. Will have RedC be the child of parent, with the original sibling becoming the right child of RedC.
        Left rotate on parent for the final step of Right Left case. Will end up with RedC being the root of the subtree (keeping the color of what was originally the parent) while the sibling is its right child and parent is its left child.
      • RedC is right child of sibling: RedC is to the right right of parent, so just need to do a left rotation on parent:
        Left shift on parent for Right Right case. Will have the sibling as the new root of the subtree, with its color being that of the original parent, while the parent and RedC become its black children.
    • 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.

  4. 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.
    Sibling and its children are black, but parent is red. Will set the sibling to red, and the parent to black.
    Otherwise, will change the parent to be double black, and then recursively handle the double black case.
    Sibling and its children are black, but parent is black. Will set the sibling to red, and the parent to double black.

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.

Categories: Uncategorized |

Leave a Reply

Your email address will not be published. Required fields are marked *

[TOP]