Okay. What's the deal with
RedBlackTrees? They're, like,
everywhere! Universities are teaching them instead of
AvlTrees. They're showing up in the kernel. They seem to have become the
BalancedTree of choice. Why?
Back "in my day" we all used
AvlTrees when we needed a
BalancedTree. They made sense, they used fairly obvious rotations, and well, I understood them. Now I fancy myself competent in computer land. I grok
BeeTrees,
TwoThreeTrees,
TwoThreeFourTrees, and
AvlTrees. But I don't get these new
RedBlackTree things. I see how to statically map a
RedBlackTree into a
TwoThreeFourTree, but I don't see how any of the insertion or deletion algorithms I can find for
RedBlackTrees, with all their color flips, map into those for
TwoThreeFourTrees.
So, I've got two questions for you wiki masters:
- Where can I find a good description of RedBlackTrees? Not just some froofy, here's how they map into TwoThreeFourTrees, not one that just gives some algorithms without any explanation, but one that walks through the algorithms and explains what they're doing?
Wikipedia has a nice article on RedBlackTrees (http://en.wikipedia.org/wiki/Red-Black_tree). It explains how each of the rotation algorithms serves to restore the tree's invariants.
- What do RedBlackTrees have over AvlTrees? What is so cool about them that they have all but replaced AvlTrees in programming land?
Not having learned AvlTrees in school, I can't say for sure :), but a Google search ("avl-tree vs red-black") turns up some interesting discussions. In summary: AvlTrees are slightly better balanced than RedBlackTrees. Both trees take O(log n) time overall for lookups, insertions, and deletions, but for insertion and deletion the former requires O(log n) rotations, while the latter takes only O(1) rotations. Since rotations mean writing to memory, and writing to memory is expensive, RedBlackTrees are in practice faster to update than AvlTrees.
TheArtOfComputerProgramming explains them all I think (thus they are all not that new anyway). If I remember correctly RedBlackTrees are isomorphic to TwoThreeTrees expanded into one or two nodes. -- GunnarZarncke
The second edition of volume 3 mentions
RedBlackTrees but does not explain them. I believe that is the most current edition at this time (May 23, 2005).
You are right. Wrong reference (and wrong statement too, oops). I shouldn't trust my memory on such things. Correct: AlgorithmsFromPtoNp explains on page 165, that RedBlackTrees (are not isomorphic but) correspond very closely to 2,4-trees. -- .gz
Here's a comparative test -
http://radius-server.livejournal.com/598.html
See:
BalancedTree DataStructures
CategoryDataStructure