Re:Left-leaning red-black trees are hard to implement (2008)
by kcl on Monday December 01, 2014 @01:52PM
(#8682879)
I 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.
Re:Left-leaning red-black trees are hard to implement (2008)
by nz on Monday December 01, 2014 @09:24AM
(#8681059)
Well 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.
I also find b-trees much simpler to implement than either RB or AVL trees.