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 average depth than the other one (which doesn't really say much of how the tree will behave in real programs.)
That being said, is there a particular reason why Red-black trees are being used everywhere, when based on what is said above, B-trees should be outperforming them? (as the only benchmark I could find also shows http://lh3lh3.users.sourceforge.net/udb.shtml, but it might just be a matter of the specific implementation). Or is the reason why everyone uses Red-black trees because they're rather easy to implement, or to put it in different words, hard to implement poorly?
Also, how does this change when one moves to the realm of functional languages? It seems that both Clojure and Scala use Hash array mapped tries, where Clojure uses a branching factor of 32.