From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,ac39a12d5faf5b14
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-04-23 23:43:05 PST
Newsgroups: comp.lang.ada
Subject: Re: Grace and Maps (was Re: Development process in the Ada community)
References: <3CB46975.90408@snafu.de> <3CBAFFEE.2080708@snafu.de>
 <4519e058.0204171036.6f0a7394@posting.google.com> <3CBDD795.4060706@snafu.de>
 <4519e058.0204180800.44fac012@posting.google.com> <3CBF0341.8020406@mail.com>
 <a9n0tk$6fs$1@nh.pace.co.uk>
 <4519e058.0204190529.559a47ae@posting.google.com>
 <a9p98h$8hn$1@nh.pace.co.uk> <3CC1C6B3.6060306@telepath.com>
 <3CC21747.5000501@telepath.com> <V+UgdHreGTJg@eisner.encompasserve.org>
 <x7vr8l871it.fsf@smaug.pushface.org> <4519e058.0204220534.2eb33730@posting.go
 <3CC4E9DA.E02BE0DA@san.rr.com> <x7vn0vv0z2r.fsf@smaug.pushface.org>
 <u3cxm2gff.fsf@ctwd0143.fitlinxx.com>
From: Jean-Marc Bourguet <jm@bourguet.org>
Date: 24 Apr 2002 08:42:53 +0200
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
NNTP-Posting-Host: cdssoph29.cadence.com
Message-ID: <3cc653f7$1@news.cadence.com>
X-Trace: news.cadence.com 1019630583 cdssoph29.cadence.com (23 Apr 2002
 23:43:03 -0800)
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!nntp.abs.net!uunet!dca.uu.net!news.cadence.com
Xref: archiver1.google.com comp.lang.ada:23035
Date: 2002-04-24T08:42:53+02:00
List-Id: <comp.lang.ada>

David Bolen <db3l@fitlinxx.com> writes:

> Simon Wright <simon@pushface.org> writes:
> 
> > Darren New <dnew@san.rr.com> writes:
> > 
> > Are red-black trees much better than AVL trees (which is what you get
> > in the BCs)?
> 
> I believe the primary difference is a better bound on the number of
> operations to perform to re-balance the tree.  In an AVL tree you may
> need to perform lg n rotations, whereas in an red-black tree you have
> a maximum of 2 rotations for insertion, and 3 for deletion.

Red-Black trees are a special case of B-Trees (consider a black node
with its red child and you have a B-Tree bucket).  So the maximum
number of operations needed on insertion and deletioon is of the order
of log n.

-- 
Jean-Marc