There are other kinds of binary tree with simpler rebalancing procedures, most notably the AVL tree mentioned by cousin_it. I think red-black tends to dominate for some combination of these reasons:
Tradition. Some influential sources (e.g., Sedgwick’s algorithms book[1], SGI’s STL implementation) used, or gave more visibility to, red-black trees, and others copied them.
Fewer rotations in rebalancing. In some circumstances (certainly deletion; I forget whether it’s true for insertion too) AVL trees may need to do Theta(log n) rotations, whereas red-black never need more than O(1).
Does this mean an actual advantage in performance? Maaaaybe. Red-black trees are, in the worst case at least, worse-balanced, which may actually matter more. Such benchmarks as I’ve seen don’t suggest a very big advantage for either red-black or AVL over the other.
Persistence. If you want to make a persistent data structure out of a binary tree, whether for practical reasons or just to show your students in Haskell, it’s easier with a red-black tree.
Metadata requirements. A red-black tree needs one bit per node, to store the redness/blackness. An AVL tree needs one and a half bits :-) to store the −1/0/+1 height difference. Perhaps in some implementations it’s OK to “waste” one bit per node but not two.
[1] I think. I don’t have a copy myself. Surely it must at least mention AVL trees too, but my hazy recollection is that the balanced-tree algorithm Sedgwick gives most space to is red-black.
I expect it is—I haven’t looked. But AIUI the usual way of making this sort of structure persistent amounts to remembering a log of everything you did, so the requirement for more rotations means that a persistent AVL tree ends up less space-efficient than a persistent red-black tree. Something like that, anyway, I haven’t attempted to build either.
In Haskell, or any GC language really, you don’t need a log to make a tree data structure persistent. Just always allocate new nodes instead of changing old ones, so all operations will return a new version of the whole tree. That’s O(log n) allocations per operation, because most subtrees can be shared between the old and new versions, only the nodes along one path down the tree need to be new. Anyone who kept a reference to an old version’s root can keep accessing the entire old version, because nodes never change. And if nobody kept a reference, GC picks it up. That way it’s also easy to have branching history, which seems impossible with a log.
Good analysis, thanks. I buy the first two points. I’d be shocked to see an implementation that actually makes use of the lower metadata requirements. Are there languages that provide a boolean primitive that uses a single bit of memory instead of a full byte? Also I don’t understand what you mean by persistence.
Suppose you’re making tree structures in a pure functional language, where there is no mutable state. Then what you need is functions that e.g. take a tree and a new element and return a new tree, sharing as much of its structure as possible with the old for efficiency’s sake, that has the new element in it. These are sometimes called persistent data structures because the old versions stick around (or at least might; they might get garbage-collected once the runtime can prove nothing will ever use them).
There are other kinds of binary tree with simpler rebalancing procedures, most notably the AVL tree mentioned by cousin_it. I think red-black tends to dominate for some combination of these reasons:
Tradition. Some influential sources (e.g., Sedgwick’s algorithms book[1], SGI’s STL implementation) used, or gave more visibility to, red-black trees, and others copied them.
Fewer rotations in rebalancing. In some circumstances (certainly deletion; I forget whether it’s true for insertion too) AVL trees may need to do Theta(log n) rotations, whereas red-black never need more than O(1).
Does this mean an actual advantage in performance? Maaaaybe. Red-black trees are, in the worst case at least, worse-balanced, which may actually matter more. Such benchmarks as I’ve seen don’t suggest a very big advantage for either red-black or AVL over the other.
Persistence. If you want to make a persistent data structure out of a binary tree, whether for practical reasons or just to show your students in Haskell, it’s easier with a red-black tree.
Metadata requirements. A red-black tree needs one bit per node, to store the redness/blackness. An AVL tree needs one and a half bits :-) to store the −1/0/+1 height difference. Perhaps in some implementations it’s OK to “waste” one bit per node but not two.
[1] I think. I don’t have a copy myself. Surely it must at least mention AVL trees too, but my hazy recollection is that the balanced-tree algorithm Sedgwick gives most space to is red-black.
Hm, my implementation of AVL trees seems persistent enough?
I expect it is—I haven’t looked. But AIUI the usual way of making this sort of structure persistent amounts to remembering a log of everything you did, so the requirement for more rotations means that a persistent AVL tree ends up less space-efficient than a persistent red-black tree. Something like that, anyway, I haven’t attempted to build either.
In Haskell, or any GC language really, you don’t need a log to make a tree data structure persistent. Just always allocate new nodes instead of changing old ones, so all operations will return a new version of the whole tree. That’s O(log n) allocations per operation, because most subtrees can be shared between the old and new versions, only the nodes along one path down the tree need to be new. Anyone who kept a reference to an old version’s root can keep accessing the entire old version, because nodes never change. And if nobody kept a reference, GC picks it up. That way it’s also easy to have branching history, which seems impossible with a log.
Good analysis, thanks. I buy the first two points. I’d be shocked to see an implementation that actually makes use of the lower metadata requirements. Are there languages that provide a boolean primitive that uses a single bit of memory instead of a full byte? Also I don’t understand what you mean by persistence.
Suppose you’re making tree structures in a pure functional language, where there is no mutable state. Then what you need is functions that e.g. take a tree and a new element and return a new tree, sharing as much of its structure as possible with the old for efficiency’s sake, that has the new element in it. These are sometimes called persistent data structures because the old versions stick around (or at least might; they might get garbage-collected once the runtime can prove nothing will ever use them).