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-25 00:40:45 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> <4519e058.0204190529.559a47ae@posting.google.com> <3CC1C6B3.6060306@telepath.com> <3CC21747.5000501@telepath.com> <4519e058.0204220534.2eb33730@posting.go <3CC4E9DA.E02BE0DA@san.rr.com> <3cc653f7$1@news.cadence.com> From: Jean-Marc Bourguet Date: 25 Apr 2002 09:40:33 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii NNTP-Posting-Host: cdssoph29.cadence.com Message-ID: <3cc7b2fc@news.cadence.com> X-Trace: news.cadence.com 1019720444 cdssoph29.cadence.com (25 Apr 2002 00:40:44 -0800) Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!sunqbc.risq.qc.ca!nntp.abs.net!uunet!dca.uu.net!news.cadence.com Xref: archiver1.google.com comp.lang.ada:23098 Date: 2002-04-25T09:40:33+02:00 List-Id: David Bolen writes: > Jean-Marc Bourguet writes: > > > David Bolen 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. There is an isomorphism between Red-Black trees and B-Trees (if this is not clear, look for 2-3 and 2-3-4 trees in the litterature, if memory serves Aho's books on algorithms is a good place) and rotation with color change are the equivalent of bucket split/merge. As on insertion or deletion in a B-Tree, the number of bucket split/merge is O(lg n) -- I think this is easier to see --, it is true also of the number of rotation in a Red-Black trees when rebalancing after an insertion/deletion. Examples: insert numbers from 1 to 17 in this order in a red-black trees. delete the numbers from 1 to 8 in this order in the resulting tree. Yours, -- Jean-Marc