Red Black Trees Vs Avl Trees

Okay. What's the deal with RedBlackTrees? They're, like, everywhere! Universities are teaching them instead of AvlTree?s. They're showing up in the kernel. They seem to have become the BalancedTree of choice. Why?

Back "in my day" we all used AvlTree?s 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, TwoThreeTree?s, TwoThreeFourTree?s, and AvlTree?s. 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 TwoThreeFourTree?s.

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 TwoThreeFourTree?s, 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 AvlTree?s? What is so cool about them that they have all but replaced AvlTree?s in programming land?

Not having learned AvlTree?s in school, I can't say for sure :), but a Google search ("avl-tree vs red-black") turns up some interesting discussions. In summary: AvlTree?s 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 AvlTree?s.

TheArtOfComputerProgramming explains them all I think (thus they are all not that new anyway). If I remember correctly RedBlackTrees are isomorphic to TwoThreeTree?s 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