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!
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.
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.
Java
Ruby
Go
Javascript
C++
Python
Clojure