Okay. What's the deal with RedBlackTree''''''s? 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 BeeTree''''''s, 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 RedBlackTree''''''s, 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 RedBlackTree''''''s? 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 RedBlackTree''''''s (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 RedBlackTree''''''s 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 RedBlackTree''''''s.  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, RedBlackTree''''''s 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 RedBlackTree''''''s are isomorphic to TwoThreeTree''''''s expanded into one or two nodes. -- GunnarZarncke''

The second edition of volume 3 mentions RedBlackTree''''''s 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 RedBlackTree''''''s (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