Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : Googmeister
Date : Sat Sep 10 2005 03:55 pm


A. Bolmarcich wrote:

> Elegance may be in the eye of the beholder.  To me the rebalancing
> algorithm of binary B-trees is more elegant than that of AVL trees
> which is are more elegant than that of Red-Black trees.
>
> This may be affected by the algorithm description that I have used:
>
>   Red-Black trees: Thomas H. Cormen, Charles E. Leiserson, and Ronald
>   L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990

Yes, I agree. CLR is a fine textbook, but they don't do a great
job of motivating or red-black trees and their implementation
isn't the most direct.

If you want to see the elegance of red-black trees, you should
view them as an efficient implementation of 2-3-4 trees. That's
how they were discovered. E.g., see Sedgewick, Algorithms in *
for this viewpoint.

.