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

Groups > comp.programming > #3314 > unrolled thread

AVL versus Red-Black Trees

Back to article view | Back to comp.programming

Contents

  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

#3314 — AVL versus Red-Black Trees

AVL trees and Red-Black Trees are both types of self-balancing binary search 
trees.  AVL trees were developed in the early 1960's by two Russians. 
Red-Black trees were developed in the 1970's.  My question is this:

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???

--
numerist at aquaporin4 dot com 

[toc] | [next] | [standalone]

#3315

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 ;-) 

[toc] | [prev] | [next] | [standalone]

#3318

On Wed, 15 May 2013 22:33:22 -0500, "Charles Richmond"
<numerist@aquaporin4.com> wrote:

>AVL trees and Red-Black Trees are both types of self-balancing binary search 
>trees.  AVL trees were developed in the early 1960's by two Russians. 
>Red-Black trees were developed in the 1970's.  My question is this:
>
>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???


The rotations needed to rebalance an RB tree after an insertion or
deletion are significantly less work than for an AVL tree (largely the
extra work is required to maintain the better balance of an AVL tree
after a tree modification).  So while maximally unbalanced RB trees
tend to be about 40% taller than maximally unbalanced AVL trees, and
thus have somewhat slower searches than AVL trees, insertions and
deletions are faster.

So for trees with a high number of insertions and deletions*, RB trees
can be better than AVL trees.

Most of the time it doesn't matter, and one should use the simpler to
implement AVL trees.


*And there are applications where searches (other than those that are
part of the insertion or deletion process), are relatively rare. Those
often involve streams of items that have a finite lifetime, but need,
occasionally, to be quickly found.

[toc] | [prev] | [next] | [standalone]

#3332

"Charles Richmond" <numerist@aquaporin4.com> writes:

> AVL trees and Red-Black Trees are both types of self-balancing binary
> search trees.  AVL trees were developed in the early 1960's by two
> Russians. Red-Black trees were developed in the 1970's.  My question
> is this:
>
> 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 wrote a paper about this: http://benpfaff.org/papers/libavl.pdf

[toc] | [prev] | [next] | [standalone]

#3356

Ben Pfaff wrote:

> I wrote a paper about [AVL,RB & Splay trees]: 
> http://benpfaff.org/papers/libavl.pdf

Thanks, that was illuminating.

    -- chris 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web