This is a valuable article that I read thoroughly when I was re-reviewing search trees. Nobody wants to spend 60 hours learning a new tree only to have it fail to live up to its promise. I'll summarize what I know (or think I know) about trees here, since it may be of use to anyone who had enough of an interest to check out the above article.

Sedgewick claims that LLRB trees are simpler, but this is hotly contested. Most of the sources I read said that LLRB trees were more complicated, often a lot more, than regular RB trees. All of the timings I found suggested that LLRB trees were slower than RB trees. Looking at the code, and at the detailed timings, I tend to agree that LLRB trees are slower and more complicated. If there is an explanation/implementation which realizes Sedgewick's promise of simplicity I have not seen it, and it isn't in the published LLRB material.

If you need a tree that is slower and simpler than an RB tree, with a similar implementation, you could look at AA trees instead.

My opinion however is that, in terms of practical applications, there is no reason to learn RB trees today instead of AVL trees. If you do research in data structures, RB trees may be worth knowing. I think the prevalence of RB trees is due to several factors:

1. RB trees are featured in the common Cormen algorithms book in lieu of AVL trees (a mistake). RB trees are also featured in the Sedgewick book.

2. The Cormen book shows how to implement delete for RB trees. Knuth's AVL description, and indeed most AVL descriptions, omit the delete method, which is a serious oversight. This has caused many tree implementations to avoid deletes or avoid AVL altogether. You can verify this via Google or GitHub. While Knuth initially had good reason, ultimately omitting delete was a mistake.

3. Plenty of theoretical conjecture predicts RB trees are faster. Actual benchmarks show that AVL trees perform better, or at worst, about the same. (If anyone has data that shows scenarios where this is not the case, I would be interested to see it.)

This is an unfortunate state of affairs, as the AVL tree appears to be a strictly better tree than the RB tree. The height is bounded at about 1.5x optimal instead of 2x optimal. You could argue the AVL tree is roughly as difficult to understand and code, though I would say it is simpler and more natural. The AVL tree performs generally better in actual benchmarks, and substantially better in certain important cases (sorted inserts).