4 ms·
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
by kcl 12y ago
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).
- nz 12y agoIf you're interested in this stuff, you might want to check out the draft paper linked below. It benchmarks performance and memory efficiency of various logarithmic time sorting data structures. It's a work in progress, and feedback is always welcome :) http://nickziv.files.wordpress.com/2014/02/vis_ds.pdf http://nickziv.files.wordpress.com/2014/02/vis_ds.pdf
- adrianN 12y agoThis seems to confirm my hunch that there is no reason to use anything but b-trees on modern computers, at least for single threaded code. Storing more values in the nodes and increasing the branching factor is better because you do more of your work inside the cache and avoid random memory access. I also find b-trees much simpler to implement than either RB or AVL trees.
- nz 12y agoWell if you're storing integers or other other small (8-byte) elements, then sure. But if you are storing pointers to objects, then you'll have the overhead of a load (in the comparison function). If you are embedding the objects, then the larger it is the more "copy-overhead" you will have as you move these large elements around when re-balancing and so on. But I don't have the numbers for this, so it might be insignificant overhead. I have it on my todo-list to benchmark embedded-larger-elements and pointers to those elements. Anyway, just something to consider.
- kcl 12y agoI stop short of recommending B-trees as the only tree structure you need to know. I think if it matters at all what kind of tree you're using, you're deep enough in the guts that it pays to know the differences between B-trees and basic trees. To me, this is especially relevant today, since if you need a "B-tree", you probably need a standard relational database (MySQL/PostgreSQL/SQLite), and if that doesn't work for you, you'd be advised to know what the tradeoffs are with a regular tree. There are scenarios where B-trees are suboptimal. Cache-obliviousness, which is still new, is also changing how we look at trees, since in one sense a B-tree is a hack on the basic tree structure to exploit locality. Representation matters more today as well. This is a longer conversation. Suffice to say I think this is an area of active and useful research, and wouldn't rule out either class of tree.
- userbinator 12y agoPlenty of theoretical conjecture predicts RB trees are faster. Actual benchmarks show that AVL trees perform better, or at worst, about the same. That's really odd - there's probably some assumption that isn't true. It reminds me of the saying, "In theory, there's no difference between theory and practice. In practice, there is."