Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.linkpendium.com!news.linkpendium.com!news.snarked.org!newsfeed.news.ucla.edu!usenet.stanford.edu!not-for-mail
From: Ben Pfaff <blp@cs.stanford.edu>
Newsgroups: comp.programming
Subject: Re: AVL versus Red-Black Trees
Date: Sat, 18 May 2013 15:41:09 -0700
Lines: 13
Message-ID: <87mwrrnc6y.fsf@blp.benpfaff.org>
References: <kn1jqt$qab$1@dont-email.me>
Reply-To: blp@cs.stanford.edu
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: usenet.stanford.edu 1368916869 2511 127.0.0.1 (18 May 2013 22:41:09 GMT)
X-Complaints-To: action@cs.stanford.edu
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)
Cancel-Lock: sha1:dCFnZBnoF/4vLtYn6/2SrPjhWI4=
Xref: csiph.com comp.programming: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