[cheepin]

Interestingly, a red-black tree can be viewed as a BTree [0].

Another case where caching plays a huge role in determining the most efficient data structure (See vector vs list [1]).

[0]: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_...

[1]: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector...

[nonsens3]

Robert Sedgewick gives a very good analogy of a red-black tree to a 2-3 tree on his Coursera course (Algorithms, Part I) [0] - a bit different to what is discussed in Wikipedia, but very easy to understand and implement.

[0]: https://class.coursera.org/algs4partI-004