Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary in C#, etc.)

Having just covered (a,b), red-black & AVL trees in my algorithms class, here's what I got out (also from asking around professors, looking through a few books and googling a bit):

• AVL trees have smaller average depth than red-black trees, and thus searching for a value in AVL tree is consistently faster.

• Red-black trees make less structural changes to balance themselves than AVL trees, which could make them potentially faster for insert/delete. I'm saying potentially, because this would depend on the cost of the structural change to the tree, as this will depend a lot on the runtime and implemntation (might also be completely different in a functional language when the tree is immutable?)

There are many benchmarks online that compare AVL and Red-black trees, but what struck me is that my professor basically said, that usually you'd do one of two things:

• Either you don't really care that much about performance, in which case the 10-20% difference of AVL vs Red-black in most cases won't matter at all.

• Or you really care about performance, in which you case you'd ditch both AVL and Red-black trees, and go with B-trees, which can be tweaked to work much better (or (a,b)-trees, I'm gonna put all of those in one basket.)

The reason for that is because a B-tree stores data more compactly in memory (one node contains many values) there will be much fewer cache misses. You could also tweak the implementation based on the use case, and make the order of the B-tree depend on the CPU cache size, etc.

The problem is that I can't find almost any source that would analyze real life usage of different implementations of search trees on real modern hardware. I've looked through many books on algorithms and haven't found anything that would compare different tree variants together, other than showing that one has smaller ave

To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question


For some kinds of binary search trees, including red-black trees but
not AVL trees, the "fixes" to the tree can fairly easily be predicted
on the way down and performed during a single top-down pass, making
the second pass unnecessary. Such insertion algorithms are typically
implemented with a loop rather than recursion, and often run slightly
faster in practice than their two-pass counterparts.

So a RedBlack tree insert can be implemented without recursion, on some CPUs recursion is very expensive if you overrun the function call cache (e.g SPARC due to is use of Register window)

(I have seen software run over 10 times as fast on the Sparc by removing one function call, that resulted in a often called code path being too deep for the register window. As you don't know how deep the register window will be on your customer's system, and you don't know how far down the call stack you are in the "hot code path", not using recursion make like more predictable.)

Also not risking running out of stack is a benefit.

StackExchange Computer Science Q#41969, answer score: 16