BST deletion

Suppose we want to delete a targetted value $t$ from a red-black tree $T$. Let's consider first the deletion algorithm for a (regular/plain/vanilla) Binary Search Tree: Let $n_t$ be the node that stores the targetted key. + if $n_t$ has at most one child, delete it, replacing it with either its lone child or a terminal node. + if $n_t$ has two children, replace its value with that of its immediate successor (which we'll denote $s(t)$), then delete $s(t)$ as in the above case ($s(t)$ is guaranteed to have at most one child) Recall we insist, for red black trees, that for all nodes, the number of black nodes along any path to a descendant leaf is fixed. Deleting a node outright would shorten at least one simple path from root to leaf. If the node we deleted was red, we will not have disturbed this property, however if we delete a black node we will destroy this property.

The Approach

Ok, so how do we fix this? Here's our strategy: If the node to be deleted was red, just delete it as in the BST case. If the to-be-deleted node is black, we empty of its value and associate the now valueless but still coloured node with whatever node comes to take its place (which could be a terminal node). If we allow the empty but coloured node to be counted when measuring the black-node-length of a simple path, we will have retained the original black height of the tree. Our goal is to remove this empty black node from the tree.

Note that we can discard the extra black node if this extra node

• sits on the root of the tree (as it is counted as an extra black node for every path)
• sits on a red node of the tree (as this node could be recoloured black)

Let's try then, to either move this valueless black node up towards the root or arrange for the empty black carrier to have a red ancestor all the while retaining the properties of the red-black tree.

Some particular cases

Let's look at some easy examples. Suppose we're in the following situation:

Here we can, in one move, eliminate the empty black node. Do you see how? Since C and E are both black, we can have B absorb A's empty black and push B's redness down to D. i.e.

To convince yourself that this move is valid, consider that any child of A the first tree has the same number of black parents in the second tree; the same is true for any node, and so we haven't disturbed the black-height property with this move.

Another Case

What if B wasn't red? e.g.

Here we can't finish in one move, but we can push the extra black up the tree with the same strategy:

The extra black node at B, which now counts against all paths going through D, is counteracted by that D is now red; the recolouring of D is valid since D has neither a black nor red child. Again, while we haven't eliminated the extra black, we have managed to push it closer to the root, which is progress (since if it gets to the root, we can simply remove it from the tree).

Another Case

Ok; so what if B is red, but E is also red? Like this:

We can't apply the logic of our first case, of pushing B's redness onto it's child, since that would violate the requirement that red nodes have black children. However we can eliminate the double black in single move if we're a little more tricky. Consider the following redrawing:

By rotating D up the tree, C pivots to become B's extra child, and now B can absorb the extra black. Since D takes B's former colour (red), E must now become black.

Given that this rearrangement is more complicated, it is important to check that we have preserved the black-height. Check for yourself that children of A have the same number of black parents in each example, and the same is true for the other leaves of the tree (C and E).

The General Algorithm

We've developed a methodology for deletion - vanilla BST deletion plus a 'double-black' elimination routine. We've defined the basic goal of double-black elimination (pushing the extra-black to the root or to a red node), and worked out a few simple cases for how this goes. This are all the ingredients of the algorithm. While there are more cases than outlined above, no matter the state of the RBtree, it's possible to either move the extra black up the tree, or rotate a neighbouring red node above the double-black (for eventual elimination).