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-24 11:17:07 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!cpk-news-hub1.bbnplanet.com!news.gtei.net!nntp.abs.net!uunet!dca.uu.net!ash.uu.net!spool0901.news.uu.net!spool0900.news.uu.net!reader0901.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>
 <u3cxm2gff.fsf@ctwd0143.fitlinxx.com> <3cc653f7$1@news.cadence.com>
From: David Bolen <db3l@fitlinxx.com>
Date: 24 Apr 2002 14:18:56 -0400
Message-ID: <ulmbdhsdr.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: 1019672226 reader1.ash.ops.us.uu.net 14973 208.247.212.3
Xref: archiver1.google.com comp.lang.ada:23071
Date: 2002-04-24T14:18:56-04:00
List-Id: <comp.lang.ada>

Jean-Marc Bourguet <jm@bourguet.org> writes:

> David Bolen <db3l@fitlinxx.com> writes:
(...)
> > 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.

Yes, total operations for insertion/deletion is lg n - but the
question was the difference between red-black and AVL (both of which
are balanced trees with O(lg n)), and the difference there is how many
actual rotations you perform while re-balancing the tree.

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