You could have invented red-black trees!

By John Lenz. December 27, 2015.

Textbook presentations of red-black trees define the color properties and then concisely describe the insert and remove operations. While this explains red-black trees, it seems like magic that the properties keep the tree balanced and that it is possible to insert and remove maintaining the properties. As an alternative, I present here a discussion in the style of you could have invented... articles which introduce the problem (in our case balanced trees), introduce an easy to understand insight (described in part 1), and work out the details (in our case, insert in part 2, remove in part 3, and various final optimizations in part 4).

The required background is a basic knowledge of unbalanced trees as well as familiarity with recursion.

A discussion similar to this presentation has also been written by Eternally Confuzzled. The reason I wrote these notes is that these notes were originally companion notes for my data structures course at UIC, and the textbook we used describes left-leaning red-black trees while Externally Confuzzled uses non-left-leaning trees. In the course of developing these notes and teaching the course, I now dislike left-leaning red-black trees; while they reduce slightly the cases you have to consider, the left and right cases are no longer symmetric. Especially during remove, the left-leaning property does not reduce the complexity of understanding at all. But, these pages were originally heavily influenced by the discussion in the Open Data Structures Textbook.