Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3315

Re: AVL versus Red-Black Trees

Show all headers | View raw

Charles Richmond wrote:

> Since an AVL tree actually keeps the tree in a little better balance than
> the Red-Black tree, and since the AVL code is *simpler* than the Red-Black
> code... why do we need the Red-Black tree at all???  Why *not* use the AVL
> tree in all such circumstances???

I [believe I] have noticed a general tendency for algorithms mentioned in:

    Introduction to Algorithms
    Cormen, Leiseron, Rivest, & Stein

to be used in contexts when there are other more natural seeming (at least, 
they seem so to me) algorithms that get passed over.  Even though they are 
described in other equally "elementary" texts (such as Sedgewick).

I suspect this is a North American thing -- that book isn't used particularly 
widely Over Here AFAIK.  I' m assuming that it /is/ used widely as "the" 
algorithms text in teaching Over There, hence the dominance of the algorithms 
it mentions, and the neglect of the others.

I have no particular sense of the costs and benefits of the trees you mention 
(I avoid balanced trees if I possibly can), so I can only take your word for it 
that AVL is superior.  But if it is, then I postulate educational bias as part 
of the story.

    -- chris

P.S.  (glad I double checked before posting this!)  C L R & S /does/ mention 
AVL trees, but only as a half-page of exercises, whereas R/B trees get a whole 
15-page chapter ;-) 

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

AVL versus Red-Black Trees "Charles Richmond" <numerist@aquaporin4.com> - 2013-05-15 22:33 -0500
  Re: AVL versus Red-Black Trees "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-16 05:58 +0100
  Re: AVL versus Red-Black Trees Robert Wessel <robertwessel2@yahoo.com> - 2013-05-16 02:42 -0500
  Re: AVL versus Red-Black Trees Ben Pfaff <blp@cs.stanford.edu> - 2013-05-18 15:41 -0700
    Re: AVL versus Red-Black Trees "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-05-20 08:25 +0100

csiph-web