Red-Black Tree Deletion

After a lot of hard work, you’ve seen how a red-black tree’s insertion operation works. But wait, there’s more! Don’t forget that there’s also an algorithm for deleting a node from a red-black tree. As complex as insertion was, deletion involves even more steps and more subcases. However, this chapter is already too long, so you’ve been saved by the bell.

For completeness, you can find a description of the deletion algorithm on the book’s web page. So, the choice is yours. If you’re ready to move on from red-black trees, no problem. But if you need to learn this stuff for a college exam, the material is right there for you. (And good luck!)

In any case, I do recommend glancing through the deletion algorithm if only to appreciate its complexity because in the next chapter, we are going to contrast the complexity of red-black trees with the simplicity of another self-balancing tree called a treap.