Design and Analysis of Algorithms: Red-Black Trees

What is a red-black tree?

The colors (indeed, using any color at all -- we could call them 0 and 1 trees!) are arbitrary. One story from one of the creators is that they had red and black pens handy!

Red-black properties

  1. Every node is red or black.
  2. The root is black.
  3. Every leaf (T.nil) is black.
  4. If a node is red, then both of its children are black. (Never two reds in a row while descending!)
  5. For each node, all paths from the node to its descendant leaves contain the same number of black nodes.

And so, a simple way to get an intuition as to why no leaf is further than twice as far from the root as the nearest leaf: The nearest leaf is B levels from the root. Since there is never more than one R-node between any two B-nodes, at most, the furthest node can be 2B - 1 levels away from the root.

Operations on red-black trees

Remember: This is a binary search tree.
So, non-modifying operations such as minimum(), maximum(), successor(), predecessor(), and search() run in O(height) time, and so for red-black trees, in O(lg n) time.

But what about insert and delete? They are obviously trickier. In fact, they are the whole trick: the red-black properties are just a way of keeping the tree roughly balanced.

Source Code

Java
Ruby
Go
Javascript
C++
Python
Clojure

For Further Study

Homework