AVL versus Red-Black Trees

[Charles Richmond]

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

[Chris Uppal]

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

[Robert Wessel]

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.

[Ben Pfaff]

I wrote a paper about this: http://benpfaff.org/papers/libavl.pdf

[Chris Uppal]

Ben Pfaff wrote:

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

Thanks, that was illuminating.

-- chris