6. Delete

Deletion in B.S.T. is hard; deletion in red-black tree is really a pain in the butt. No kidding. Pull yourself together and get moving!

The idea is same as in insertion: first proceed as in a normal binary search tree, and then do some recolor and rotations until the rules are restored. The steps are as follows:

(1) Apply the same deletion method in B.S.T. But let’s pause after node x is swapped but before it is deleted or spliced out. To make the problem more general, let’s suppose x has one child r, and r may be null.

(2) Depending on the color of x and r, we have many different cases. If x is red and r is black, this is easy. We simply delete x and let r assume x’s position. Since x is red, taking out x won’t affect the number of black nodes in root-null path. Done. If x is black and r is red, this is also easy. Simply taking out x and paint r black. Now this root-null path passes the same number of black nodes. Done.

(3) The hard case is when x and r are both black. No matter what you do, taking out x will surely decrease the number of black nodes in this root-null path by one. This problem is called double black. To solve it we need to consider x’s sibling s and parent p. Depending on the color of s and p, we have four cases. Yes, FOUR cases! That’s why deletion in red-black tree is painful.

Case I: s is black, and has at least one red child t. If this is the case, we do some rotations to bring s to p’s position, paint t red and let s assume p’s color. See the demonstration below.

(P’s color is unknown, shown as blue.)

Let’s check if Rule #4 is broken.

Before the deletion from subtree A, B and C to root pass one black node s and node p. From r (r may be null) to root pass two black nodes r and x, and node p.

After the deletion from subtree A and B to root pass one black node t and node s. From subtree C to root passes one black node p and node s. From r (maybe r is null) to root pass two black nodes r and p, and node s. The number of black nodes for each path hasn’t changed. Rule #4 maintained.

Case II: s is black, and has two black children. P is red. If this is the case, we just need to swap the color of s and p. See the demonstration below.

Before and after deletion, from subtree A and B to root pass one black node, from r to root passes 2 black nodes. Rule #4 maintained.

Case III: s is red, which means p is black, and has two black children. If this is the case, we right/left rotate p and swap the color of s and p. See the demonstration below.

Now you should wonder: the problem continues! What’s the meaning of these steps? Something has changed after all. Subtree B’s root is black, as it is a black child of s, and p is red. Combing these two changes, we have actually changed case III to either case I or case II or the simplest case: just splice out x. We can use the same method to solve this problem.

Case IV: s is black and has two black children. P is also black. If this is the case, we paint s red and see what will happen. See the demonstration below.

What happened is that the number of black nodes from both subtrees and r to root has decreased by one. Rule #4 is restored, locally. But we may have propagated the double black problem upward. In the worst case it may reach to root. This may take O(logn) fixes. During the process we either end up with case I, II and III, or continue to encounter case IV. The lucky thing is we have to do at most O(logn) recoloring.

Burdened with four different cases, you must be confused by now. Let’s look at a concrete example. As usual, let’s summon the big red-black tree again.

Suppose we want to delete node 2. Upon closer inspection we can find that this belongs to case I. See the notations above. In this specific case r is null. We lift s to p’s position and paint it the same color as p, and then paint p and t black. After that we delete node 2. The outcome is this.

I’ll be sloppy and won’t list the paths here. Check whether Rule #4 is maintained yourself.

Let’s continue to delete node 48 this time. This belongs to case III, as noted above. To solve double black problem, we need to right rotate p and swap the color o s and p. The outcome is like this.

We haven’t solved the double black problem. No surprising. The good news is we have changed case III to case I, as noted above. Using we same method we can solve the problem now. The outcome is this.

Rule #4 is restored, indeed. Check it for yourself.

Now let’s still try to delete node 66. This belongs to the simple case. Node x is black and only has a red child. We simple splice node 66 and paint node 60 black, done.

Now for something cool. Let’s try to delete node 60 this time. Upon inspection we find that this belongs to case IV, as noted above. To solve it, we paint node s red and delete x. We get this tree.

We’ve surely fixed the double black problem in the subtree 58. Unfortunately we have propagated the double black problem upward. Now the problematic node is 58. From here we can find that this belongs to case II, as noted above. To deal with it, we simply swap the color between p and s. Finally we get this tree.

Problem solved! I hope you get some ideas about deletion operation in red-black tree throughout these demonstrations. I racked my brains to come up with all these four cases, plus a simple case. I would be sad if you didn’t get anything from this.

Finally, efficiency. Summarizing all four cases, we can have at most O(logn) recoloring and O(1) topological changes in deletion operation, as promised.

7. Conclusion

We’ve come a long way to conclusion, and it’s time to reap the benefit. Red-black tree is a powerful data structure. It can promise O(logn) for search, insert and delete operations. Besides, all dynamic changes will only result in at most O(1) topological changes. Tough the implementation is really difficult, many programming languages have built-in data structure of red-black tree, and there’re many online libs to use. We can use this powerful weapon without a painful time. Isn’t this wonderful?