Before we talk about that deletion procedure, we need to figure out how to delete a node in the general case.


So anyway, suppose we have this awkward binary search tree which probably can't be exactly expressed on a computer unless you've got symbolic manipulation and very intelligent comparison features. There are essentially three cases.

1. Delete the green node, , with 0 children. Since it's a leaf node, no problem. Just remove it, and replace with nil if necessary.
2. Delete the blue node, , with 1 child. This is pretty easy, too: just take it out and reconnect its child with its parent, in this case, and .
3. Delete the red node, , with 2 children. (It also happens to be the root, but that's not important.) We instead overwrite it with its predecessor, , and delete the old node. This reduces to case 2 or 1, since the predecessor can't have a right child. Yay.

Yep, so that's how you delete.

Righty then, on to the red-black deletion procedure. So first we do what we outlined above, of course, and figure out how badly we messed up the Red-Black Rules, and try to fix it.

Okay. Case 1 is actually a special case of Case 2, when the part below the deleted node consists of nothing. Case 3 also ends up in Case 2, given that the overwrite keeps the host's original color, so the color configuration there don't change. So we just have to deal with a spliced-out node, maybe in this instance.

Suppose was red. Then both parts that were originally had to be connected to were black, so splicing them together won't break the no-reds-together rule. Also, the equal-black-paths aren't broken either (annoying meticulous two-column casework left to the reader). It works, just that way.

Suppose was black. We've now gotten rid of a black node in one of those paths, and possibly made two reds touch as well. Ouch.

Let's see what we can do to fix this. We know that whatever node we spliced out, , only had one child (or none). Here that would be . Well, every path that went through and still exists now must go through , and we need to readd a black node to each of those paths. Let's make black! We're done!

Dammit. might have already been black. If it's red, we're done, so let's see what happens if was black. Let's pretend we can make DOUBLE-BLACK. That works, but we don't allow that kind of color, so we'll have to figure out how to fix it. Hmm...

(Also, to prevent us somehow using as a variable later, we'll just call the DOUBLY-BLACK node . And we'll color it a bright magenta, which is what DOUBLY-BLACK looks like in cartoons. Or maybe, I don't know.)

Okay, let's look at 's sibling.

Suppose it's red. We don't want that, because they're siblings, and they're so far (read (no pun intended (depending on whether you read "read" in such a situation as "red" or as "reed" (read: whatever ( (invalid reference to xkcd 541 (which I saw used in the Python documentation SOMEWHERE (don't overuse caps, guys (Python rocks)))))))): two black-levels) apart! Let's fix it for them, by left-rotating and , so that becomes 's brother. Crunch. (Picture left to the reader as an exercise.)


Otherwise, 's sibling is black. You'll notice the other nodes are gray, which isn't a color, but I don't like using other people's storage for these images even though certain other people *cough* really like it, so I'm going to smoosh all these other cases into one.

Suppose and are both black. Then we can take away one black-level from and and give it to . If is now DOUBLY-BLACK, we can use RECURSION. Whee.

Suppose is red, is black. Then we can right-rotate and , swap their colors, and reduce to the next case.

Suppose is red. Then we can left-rotate and , take away the extra blackness from , and give it to . No recursion necessary!

Yay, we're done!