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 15:32:10 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!uunet!sea.uu.net!ash.uu.net!spool0901.news.uu.net!spool0900.news.uu.net!reader0900.news.uu.net!not-for-mail
Sender: DB3L@CTWD0143
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>
From: David Bolen <db3l@fitlinxx.com>
Date: 23 Apr 2002 18:33:56 -0400
Message-ID: <u3cxm2gff.fsf@ctwd0143.fitlinxx.com>
Organization: Fitlinxx, Inc. - Stamford, CT
X-Newsreader: Gnus v5.7/Emacs 20.6
NNTP-Posting-Host: 208.247.212.3
X-Trace: 1019601129 reader0.ash.ops.us.uu.net 21876 208.247.212.3
Xref: archiver1.google.com comp.lang.ada:23019
Date: 2002-04-23T18:33:56-04:00
List-Id: <comp.lang.ada>

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.

How much of an improvement this is would depend on the cost of
performing the rotation.

--
-- David
-- 
/-----------------------------------------------------------------------\
 \               David Bolen            \   E-mail: db3l@fitlinxx.com  /
  |             FitLinxx, Inc.            \  Phone: (203) 708-5192    |
 /  860 Canal Street, Stamford, CT  06902   \  Fax: (203) 316-5150     \
\-----------------------------------------------------------------------/