Red-Black Trees Part 3 - Remove

By John Lenz. December 27, 2015.

This page is part three of the article series You could have invented red-black trees!.

Recall from the first section the goal of red-black trees: store a balanced binary search tree such that each node is colored red or black to satisfy the following properties. A root-to-nil path is a sequence of \(L\) or \(R\) such that starting from the root and descending left or right according to the sequence, you end at nil. That is, the last step in the sequence descends in a direction for which there does not exist a child.

(black-height property) Every root-to-nil path has the same number of black nodes.
(no-red-edge property) For each node \(v\), it is not the case that both \(v\) and \(v\)'s parent are red.

We want to remove a value from the tree, maintaining the red-black properties. Our procedure will start just like normal binary search tree remove. Once we remove a node, it could violate a property so we will then add code to fix up the property.

BST Remove

Say we are trying to remove element with key \(k\). First, we use the normal binary search tree find procedure to locate the node \(v\) with \(v.key\) equal to \(k\). If \(v\) is a leaf or has a single child, we can directly remove \(v\). If \(v\) has two children, \(v\) cannot be directly removed. Instead, we will locate a node \(u\) such that:

\(u\) is a leaf or has only one child,
if the element stored at \(v\) is replaced by the element stored at \(u\) then the BST property is still satisfied.

Once we have located such a node \(u\), we can move \(u.key\) and \(u.val\) to be stored at \(v\) and then remove the node \(u\) from the tree. This effectively removes the element stored at \(v\) which is the element we originally wanted to remove. How to find such a node \(u\)? Well, to be able to be stored at \(v\) the element must be larger than everything in the left subtree of \(v\) and smaller than everything in the right subtree of \(v\). That means we have two candidates: we can take the largest element from the left subtree of \(v\) or the smallest element from the right subtree of \(v\). Either will work, but I decided to take the smallest element from the right subtree of \(v\). Finding the smallest element in a binary search tree is easy: go left until left is nil. Therefore, from \(v\) to find \(u\) we will go right and then go left until left is nil. This will produce a node \(u\) with \(u.key\) the smallest element from the right subtree of \(v\), so moving \(u.key\) and \(u.val\) to be stored at \(v\) and removing \(u\) still produces a valid binary search tree. Once we find the minimum, we need to copy this minimum to \(v\) so the bst_extract_min recursive method takes \(v\) as a parameter and just passes it along.

def bst_extract_min(u, v):
    # Find and remove the minimum element.  We are currently searching at a node u.  Once we find
    # the minimum, the key and value are copied to be stored at v.  Returns the new root of the
    # subtree.
    if u.left == nil:
        # We have found the minimum element so copy the key and value to v.
        v.key = u.key
        v.val = u.val
        # Return u.right as the new root of the subtree, effectively splicing u out of the tree.
        return u.right
    else:
        # Recurse to the left, passing along v
        u.left = bst_extract_min(u.left, v)

        # TODO: add code to fix any color violations

        return u

def bst_remove(v, k):
    # removes k from the subtree rooted at v. Returns the new root of the subtree.

    if v == nil:
        # k was never found so nothing needs to be removed
        return nil

    if v.key == k:
        # We have found the element to remove

        # If v has a nil left or right child, return the other as the new root effectively removing v
        if v.left = nil:
            return v.right
        if v.right = nil:
            return v.left
            
        # v has two children so find and remove the minimum from the right.  To do so, we start
        # searching at u = v.right, and pass in v itself so when the minimum is found it is copied
        # to this node.
        v.right = bst_extract_min(v.right, v)

    elif k < v.key:
        v.left = bst_remove(v.left, k)
    else:
        v.right = bst_remove(v.right, k)

    # TODO: add code to fix any color violations

    return v

Red-Black Properties

The above procedure will remove an element preserving the binary search tree property, but what about the red-black properties? If the node that is removed is red, then the black-height and no-red-edge properties are still satisfied. Indeed, removing a red node will not effect the number of black nodes on a root-to-nil path. Also, since there were no red-edges before removing, both the parent and child of a red node are black so removing the red node will not produce a red-edge.

What about removing a black node? This will certainly cause the black-height property to be violated, since any root-to-nil path passing through the removed node will have one fewer black node. We must add some code to fix a black-height violation into the above procedures to replace the TODOs.

There are two types of nodes we remove: either we remove the node \(v\) with \(v.key\) equal to the key we are removing or we remove the minimum node \(u\) from \(v.right\) after copying the element stored at \(u\) to be stored at \(v\). In either case, fixing the black-height violation will be identical since the red-black properties care only about the colors of nodes. Therefore, below we will consider removing a node and not care why it is being removed, just that it must come out of the tree.

Call the node we remove \(w\). As we saw above, if \(w\) is red nothing needs to be done. Therefore, assume that \(w\) has at most one child and \(w\) is black. There are two possible cases: either \(w\) is a leaf or \(w\) has a single red child and the red child is a leaf. Any other situation is disallowed by the red-black properties because of the root-to-nil path which ends at the missing child of \(w\). The latter of these two cases is the easiest to deal with.

Removing a black node with a red leaf child

This case is very easy to fix. We just remove the node and change the color of the child from red to black. Consider removing the node labeled 11 from the following tree (there are nodes above 7, I just haven't drawn them).

Figure: A black node with a red leaf child

Removing a black leaf node

When removing a black leaf, we can't get away with such an easy trick and it seems that removing the node will violate the black-height property. The black-height property is a difficult one to reason about fixing because it is a global property: we need to consider all root-to-nil paths in the entire tree. This hampers our ability to take advantage of the power of recursion and induction to reason only about a few nodes in the tree at once. (Contrast this with insert where we only considered a red-edge which was a local violation.) There is a general trend in all branches of mathematics that converting a global property to an equivalent local property is very powerful.

Therefore, we want to convert a black-height violation from a global violation to a local one, which we can do by adding a new color called double-black. This color double-black will not be a valid color on any node in the tree, since our final red-black tree must have only red or black on each node. During remove we might temporarily have one node colored double-black. The advantage this gives us is that we can consider a double-black node as counting for two when we count the total number of black nodes on a root-to-nil path, allowing us to maintain the black-height property throughout the entire removal process. Unfortunately, this is complicated by the presence of nil nodes.

Consider removing a black leaf, such as removing 9 from the following tree. Also, recall that while not stored in memory, we can consider each leaf to have two nil black children. (Since 9 is a black leaf, the black-height property forces 13 to also be black.)

Figure: Tree right before removing a black leaf

If we directly remove 9, the root-to-nil path which goes left from 11 will have one fewer black node than all other root-to-nil paths. We therefore want to add a double-black nil node as the left child of 11. This node will only temporarily be stored in memory since our goal is to remove the double-black node, but for now it will need to be added.

Figure: A double-black nil node is created after removing a black leaf

Counting the double-black node as two, each root-to-nil path now has the same number of black nodes so the black-height property is preserved. Converting this to pseudocode, we obtain the following method which splices a node out of the tree. It uses a temporary value doubleBlackNilNode instead of nil to signal a double-black nil node when removing a black leaf.

splice(w):
    # Remove node w which cannot have two children.  Returns the
    # root of the tree with w removed.

    if w.color == RED:
        assert(w.left == nil and w.right == nil)
        return nil
    else:
        if w.left != nil:
            assert(w.left.color == RED)
            w.left.color = BLACK
            return w.left

        elif w.right != nil:
            assert(w.right.color == RED)
            w.right.color = BLACK
            return w.right

        else:
            return doubleBlackNilNode

Fixing the double-black node

We will now write code to fix the double-black violation (i.e. make each node colored red or black) by operations such as rotations, flips, and color changes reasoning only locally about the violation. As long as these operations preserve the black-height property and don't introduce any red-edges, we can successfully remove from a red-black tree.

Our strategy will be similar to insert; our goal is to either change colors so no node is colored double-black or move the double-black node closer to the root. If the double-black node moves all the way to the root, the color of the root can just be changed to black. As long as these operations to fix this double-black violation preserve the black-height property and the no red edge property we will successfully remove from a red-black tree.

More specifically, say the recursive removal procedure is currently at node \(z\). This could either be \(v\) during remove or \(u\) during extract_min, but both are fixed the same with respect to the double-black violation. Assume we recurse to one of our children and while recursing to our child the child becomes double-black. We want to modify the tree to either remove the double-black color or move the double-black color up the tree. Also, we must preserve the black-height and no-red-edge properties.

Throughout this discussion, it is easier to reason about the colors if we assign numbers to them which represent the amount the node increases the black-height. Red will be assigned number 0, black will be assigned 1, and double-black assigned 2.

enum Color {
    RED = 0,
    BLACK = 1,
    DOUBLE_BLACK = 2,
}

Also, in the diagrams below I will show a fragment of the tree. Nodes which are drawn in solid black are colored double-black, nodes drawn with a black circle border are black, and nodes drawn with a red circle border are red.

There are now several cases depending on the color of \(z\) and \(z\)'s children. Since for the color properties left and right are symmetric, we will focus on the situation when \(z.right\) is double-black. Once we figure that out, we will just reflect the solution to solve the case when \(z.left\) is double-black.

When \(z.right\) is double-black, we have three subcases to consider depending on the color of \(z\) and \(z.left\).

\(z\) is black and \(z.left\) is black.
\(z\) is red and \(z.left\) is black.
\(z\) is black and \(z.left\) is red.

Note that \(z\) and \(z.left\) cannot both be red since that would be a red-edge. We will consider each of the three cases in order.

\(z.right\) is double-black, \(z\) is black, and \(z.left\) is black.

We want to move the double-black color up the tree while preserving the black-height, which we can do by increasing the color on \(z\) by one from black to double-black, and decrementing the color on both of the children of \(z\).

When moving the double-black color up the tree, we also want to deal with the doubleBlackNilNode. When decrementing the color on the double-black node, if it is doubleBlackNilNode it should be converted to nil. That leads to the following code

def pull_black(z):
    # Red is 0, Black is 1, and Double-Black is 2
    z.color += 1
    if z.left == doubleBlackNilNode:
        z.left = nil
    else:
        z.left.color -= 1
    if z.right == doubleBlackNilNode:
        z.right = nil
    else:
        z.right.color -= 1

It is straightforward to verify that the black-height property is maintained by this operation since each root-to-nil path has the same black-height as before (recall that this is only a fragment of the tree).

But there is a problem: 3 changed from black to red so a red-edge could have been created if 1 or 5 are red. The good news is that we already thought about how to remove the red-edge in these situations when we were developing insert! Looking back at insert, if 5 is red and 1 is black, we rotate left at 3 to get a situation where z.left and z.left.left are both red. We then flip right at z to remove the red-edge. The only thing we did not think about during insert is when both 1 and 5 are red. In this situation, let's still flip right at z.

Figure: Both left grandchildren of z are red — Figure: Both left grandchildren of \(z\) are red

We still have a red-edge between 7 and 5. Thinking back to insert, such a red-edge was fixed by pushing black since both children of 3 are red.

def push_black(z):
    z.color -= 1
    z.left.color += 1
    z.right.color += 1

In fact, even if there isn't a red-edge it is a good idea to push_black, since pushing black will remove the double-black node completely. We can always push_black if we flip since after flipping it is guaranteed that both children are red (see the following figures).

In summary, we will first pull_black. If after pulling, both left grandchildren of \(z\) are black we do nothing. If at least one of the left grandchildren of \(z\) are red, we fix this using either of the following two sequences of operations:

Figure: z.left.left is red and z.left.right can be either color. — Figure: \(z.left.left\) is red and \(z.left.right\) can be either color.

Figure: z.left.left is black and z.left.right is red — Figure: \(z.left.left\) is black and \(z.left.right\) is red

Turning this into code, we get the following:

if z.color == black and z.right.color == double-black and z.left.color == black:
    pull_black(z)
    if z.left.right.color == red and z.left.left.color == black:
        z.left = rotate_left(z.left)
    if z.left.left.color == red:
        z = flip_right(z)
        push_black(z)
    return z

You should verify that the black-height is preserved by these operations, which you can do by looking the figures above and considering all root-to-nil paths that pass through these fragments of the tree. Also, you should verify that no red-edge is created.

\(z.right\) is double-black, \(z\) is red, and \(z.left\) is black.

In this case, we can pull_black to turn \(z\) from red to black and decrement the color on both children of \(z\), removing the double-black node completely!

Again we could have created a red-edge between 3 and 1 or 5, but this is fixed the same as the previous case. If both left grandchildren are black, nothing else needs to be done. Otherwise, we have one of the following two figures:

Note that the final push_black turns the root from black to red and we should always be worried about creating red-edges when we turn nodes red. We are safe in this situation because \(z\) was originally red so the parent of \(z\) cannot also be red since we start with a red-black tree. Therefore, when we return the new red root after flipping and pushing black, we do not create any red-edges. Also, you should verify similar to before that the black-height property is preserved.

Since the operations are the same no matter if \(z\) starts red or black, the same code can be used to cover both cases. To do so, we can wrap up the fixes into the following utility function.

def fix_right_doubleblack_left_black(z):
    assert(z.right.color == double-black and z.left.color == black)
    pull_black(z)
    if z.left.right.color == red and z.left.left.color == black:
        z.left = rotate_left(z.left)
    if z.left.left.color == red:
        z = flip_right(z)
        push_black(z)
    return z

\(z.right\) is double-black, \(z\) is black, and \(z.left\) is red.

The next case on the chopping block is when \(z.right\) is double-black and \(z.left\) is red. In this situation, \(z\) itself and both children of \(z.left\) must be black since otherwise there would be a red-edge. Before starting to investigate in detail this case, we always ask ourselves if it can be converted into a case we have already solved. We try a few different possible flips and when we do so, discover that flipping right at \(z\) gets us to a previous case!

Figure: z.right is double-black and z.left is red — Figure: \(z.right\) is double-black and \(z.left\) is red

We can now call the utility function fix_right_doubleblack_left_black with the node 7. This removes the double-black node completely (check the above diagrams for when 7 is red) so we are in great shape! We can therefore fix the situation when \(z.right\) is double-black as follows:

def fix_right_doubleblack(z):
    assert(z.right.color == double-black)
    if z.left.color == red:
        z = flip_right(z)
        z.right = fix_right_doubleblack_left_black(z.right)
        return z
    else:
        return fix_right_doubleblack_left_black(z)

\(z.left\) is double-black

When \(z.left\) is double-black, we can just reflect everything we did above and change each right and left. When doing so, we get the following utility functions:

def fix_left_doubleblack_right_black(z):
    assert(z.left.color == double-black and z.right.color == black)
    pull_black(z)
    if z.right.left.color == red and z.right.right.color == black:
        z.right = rotate_right(z.right)
    if z.right.right.color == red:
        z = flip_left(z)
        push_black(z)
    return z

def fix_left_doubleblack(z):
    assert(z.left.color == double-black)
    if z.right.color == red:
        z = flip_left(z)
        z.left = fix_left_doubleblack_right_black(z.left)
        return z
    else:
        return fix_left_doubleblack_right_black(z)

Red-Black Remove

We now want to combine the above fixing code with the binary search tree removal. One thing we haven't thought about yet is missing nodes or nil nodes. But similar to insert, everything will work out fine if we consider a nil value as black. Throughout the above discussions, a black node in any of the diagrams could be missing and the operations will still correctly operate.

The unoptimized pseudocode becomes the following. Note that there are several micro-optimizations that are possible. For example, some if statements are redundent (if we recurse to the left it is impossible for the right child to be double-black). Also, when performing multiple rotations and flips, we could merge the procedures and directly set the tree into the correct state. But we will consider these kinds of optimizations later, for now we are focused on correctness.

def is_red(n):
    return n != nil and n.color = red
def is_black(n):
    return n = nil or n.color = black
def is_double_black(n):
    return n != nil and (n = doubleBlackNilNode or n.color = double-black)

# Copy the fix utilities above but use is_red and is_black

def fix_doubleblack(z):
    if is_double_black(z.left):
        return fix_left_doubleblack(z)
    elif is_double_black(z.right):
        return fix_right_doubleblack(z)
    else:
        return z

def extract_min(u, v):
    # Remove the minimum element from the tree rooted at u.  The removed element is stored on v.
    # The return value is the root of the tree with the minimum element removed

    if u.left == nil:
        # Copy element from u to v, overwriting what used to be at v
        v.x = u.x
        # Remove the node u from the tree
        return splice(u)

    else:
        # Go left, passing v along
        u.left = extract_min(u.left, v)

        # Fix any double-black violation
        return fix_doubleblack(u)

def remove_helper(v, x):
    # Remove x from the subtree rooted at v.  The return value is the new root of the subtree

    if v == nil:
        return nil
    
    if x == v.x:
        # We have found the element to remove
        if (v.left == nil or v.right == nil):
            # Remove v itself
            return splice(v)
        else:
            # extract the minimum from the right.  Pass v in so the removed element replaces the
            # element stored at v
            v.right = extract_min(v.right, v)

    elif x < v.x:
        v.left = remove_helper(v.left, x)
    else:
        v.right = remove_helper(v.right, x)

    return fix_doubleblack(v)

def remove(k):
    this.root = remove_helper(this.root, k)
    if is_double_black(this.root):
        if this.root = doubleBlackNilNode:
            this.root = nil
        else:
            this.root.color = black

Definition A red-black-doubleblack tree is a binary search tree where in addition each node is colored red, black, or double-black. There are no adjacent red nodes (the no-red-edge property). Let the black-height of a root-to-nil path be the sum of the colors on the path, where red counts \(0\), black counts \(1\) and double-black counts \(2\). In a red-black-doubleblack tree, each root-to-nil path has the same black-height (called the black-height property).

Fixing lemma

Lemma 1 Let \(z\) be the root of a red-black-doubleblack tree where there is at most one double-black node and if it exists it is either \(z.left\) or \(z.right\). Let \(z' = fix\_doubleblack(z)\). Then \(z'\) is the root of a red-black-doubleblack tree with the same black-height as before. In addition, there is at most one double-black node and if a double-black node exists it is \(z\) itself.

I encourage you to think about the proof of this statement. I have already explained all the pieces, but you should think about why we have covered each possibility and why the transformations end up with a red-black-doubleblack tree. Forcing us to do this verification is a main beneifit of writing these lemmas. The final proof would then include the discussion on why all cases are covered and the above figures and actions showing that a red-black-doubleblack tree is produced.

Extract min lemma

Lemma 2 Let \(u\) be the root of a red-black tree and let \(v\) be any tree node. Let \(u' = extract\_min(u, v)\). Then \(u'\) is the root of a red-black-doubleblack tree with the same black-height as before. In addition, the tree rooted at \(u'\) consists of all elements from the tree rooted at \(u\) except the element with smallest value, and there is at most one double-black node and if such a double-black node exists it is \(u'\) itself. Finally, after \(extract\_min\) returns, the smallest element from among the subtree rooted at \(u\) is copied to be stored at \(v\).

Proof The proof works by induction on the size of the tree rooted at \(u\).

Base case: \(u\) is a leaf (we don't allow extract_min on nil nodes). If \(u\) is a leaf then \(u.left\) is nil and \(u\) itself is the smallest element. We correctly copy \(u.key\) and \(u.val\) to \(v\). We then return \(u' = nil\) if \(u\) itself was red or \(u' = doubleBlackNilNode\) if \(u\) itself was black, correctly maintaining the black-heights.
Base case when \(u.left\) is nil. In this case, \(u\) itself is the smallest element since everything in the right subtree of \(u\) is larger than \(u.key\), so \(u.key\) and \(u.val\) are copied to \(v\). By the black-height property, \(u\) must itself be black and the right child of \(u\) is a red leaf. We then return u' = splice(u) which returns the right child of \(u\) with its color turned from red to black. This preserves the black-height property so we are returning a red-black-doubleblack tree (which happens to be a singleton node).
Inductive case when \(u.left\) is not nil. Let \(r' = extract\_min(u.left, v)\). By induction, \(r'\) is the root of a red-black-doubleblack tree with the same black-height as \(u.left\) and possibly \(r'\) double-black. We set \(u.left = r'\) so that \(u\) is now the root of a red-black-doubleblack tree with the same black-height as before. The right child of \(u\) could be double-black, so by Lemma 1 \(u' = fix\_doubleblack(u)\) satisfies all the properties we want of the return value.

Remove lemma

Lemma 3 Let \(v\) be the root of a red-black tree and let \(k\) be any element. Let \(v' = remove\_helper(v, k)\). Then \(v'\) is the root of a red-black-doubleblack tree consisting of all elements from the tree rooted at \(v\) except the element \(k\). In addition, the black-heights of \(v\) and \(v'\) are the same and there is at most one double-black node and if such a double-black node exists it is \(v\) itself.

Proof The proof is by induction on the size of the tree rooted at \(v\).

Base case: \(v\) is nil. In this case, \(v' = nil\) is correct since the element \(k\) does not exist.
Inductive case when \(k < v.key\). If \(k\) exists it is in the left subtree of \(v\) so let \(t' = remove\_helper(v.left, k)\). By induction, \(t'\) is the root of a red-black-doubleblack tree so setting \(v.left = t'\) makes \(v\) the root of a red-black-doubleblack tree with the same black-height as before. Then returning \(v' = fix\_doubleblack(v)\) returns a node with all the correct properties by Lemma 1.
Inductive case when \(k > v.key\). If \(k\) exists it is in the right subtree of \(v\). By induction, setting \(v.right = remove\_helper(v.right, k)\) produces a red-black-doubleblack tree. Returning \(v' = fix\_doubleblack(v)\) returns a node with all the correct properties by Lemma 1.
Inductive case when \(k = v.key\). In this case, the element we want to remove is stored at \(v\). If \(v\) has zero or one child, we can remove \(v\) by returning splice(v). Splice correctly maintains the black-heights and returns the root of a red-black-doubleblack tree with only possibly the root double-black. If \(v\) has two children, then let \(r' = extract\_min(v.right, v)\). By Lemma 2, \(r'\) is the root of a red-black-doubleblack tree with the same black-height as before but the smallest element removed. This smallest element has been copied to \(v\) which maintains the BST property while removing the element stored at \(v\). Now \(v\) is the root of a red-black-doubleblack tree with potentially one of its children double-black so by Lemma 1 returning \(v' = fix\_doubleblack(v)\) properly returns a node with the correct properties.

C++11

I have directly translated the above unoptimized pseudocode to C++11 red-black-with-remove.cpp. To see just what changed between insert and remove, here is the diff.