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 15:21:25 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!arclight.uoregon.edu!newsfeed.mathworks.com!nntp.abs.net!uunet!dca.uu.net!ash.uu.net!spool0900.news.uu.net!reader0902.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> <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> <3cc7b2fc@news.cadence.com> From: David Bolen Date: 25 Apr 2002 18:23:17 -0400 Message-ID: Organization: Fitlinxx, Inc. - Stamford, CT X-Newsreader: Gnus v5.7/Emacs 20.6 NNTP-Posting-Host: 208.247.212.3 X-Trace: 1019773283 reader2.ash.ops.us.uu.net 4894 208.247.212.3 Xref: archiver1.google.com comp.lang.ada:23122 Date: 2002-04-25T18:23:17-04:00 List-Id: Jean-Marc Bourguet writes: > David Bolen writes: (...) > > 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. Hmm, this may just be a terminology issue, and I'm far from an expert on these algorithms, but I did take a quick double check in Cormen's Intro to Algorithms before that last reply and sections 13.3 and 13.4 cover insertion and deletion and the analysis of only 2 and 3 rotations respectively. Note that I'm not suggesting that the running time is anything other than O(lg n), which is definitely true for both operations; just that the actual number of rotations performed (adjustment of location within the tree of internal nodes) as the tree is traversed during the rebalancing is more limited with red-black trees. Of course, during the overall process nodes may be re-colored without being rotated, but while such color changes are part of re-balancing, I don't consider them a "rotation". > 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. I tried a quick test of this using the RB implemention in the GNU libavl library, and in this particular case never found more than a single rotation per insertion/deletion: I found (R=rotation, r=red, b=black): Insertion: 1,2,3R,4,5R,6,7R,8R,9R,10,11R,12R,13R,14,15R,16R,17R 1: 1b 2: 1b(,2r) R 3: 2b(1r,3r) 4: 2b(1b,3b(,4r)) R 5: 2b(1b,4b(3r,5r)) 6: 2b(1b,4r(3b,5b(,6r))) R 7: 2b(1b,4r(3b,6b(5r,7r))) R 8: 4b(2r(1b,3b),6r(5b,7b(,8r))) R 9: 4b(2r(1b,3b),6r(5b,8b(7r,9r))) 10: 4b(2b(1b,3b),6b(5b,8r(7b,9b(,10r)))) R 11: 4b(2b(1b,3b),6b(5b,8r(7b,10b(9r,11r)))) R 12: 4b(2b(1b,3b),8b(6r(5b,7b),10r(9b,11b(,12r)))) R 13: 4b(2b(1b,3b),8b(6r(5b,7b),10r(9b,12b(11r,13r)))) 14: 4b(2b(1b,3b),8r(6b(5b,7b),10b(9b,12r(11b,13b(,14r))))) R 15: 4b(2b(1b,3b),8r(6b(5b,7b),10b(9b,12r(11b,14b(13r,15r))))) R 16: 4b(2b(1b,3b),8r(6b(5b,7b),12b(10r(9b,11b),14r(13b,15b(,16r))))) R 17: 4b(2b(1b,3b),8r(6b(5b,7b),12b(10r(9b,11b),14r(13b,16b(15r,17r))))) +----------- 4b ----------+ +-- 2b --+ +------- 8r -------+ 1b 3b +-- 6b --+ +---- 12b ----+ 5b 7b +- 10r -+ +- 14r -+ 9b 11b 13b +- 16b -+ 15r 17r Deletion: 1R,2R,3R,4R,5R,6R,7R,8R R 1: 8b(4b(2b(,3r),6r(5b,7b)),12b(10r(9b,11b),14r(13b,16b(15r,17r)))) R 2: 8b(4b(3b,6r(5b,7b)),12b(10r(9b,11b),14r(13b,16b(15r,17r)))) R 3: 8b(6b(4b(,5r),7b),12b(10r(9b,11b),14r(13b,16b(15r,17r)))) R 4: 8b(6b(5b,7b),12b(10r(9b,11b),14r(13b,16b(15r,17r)))) R 5: 12b(8b(6b(,7r),10r(9b,11b)),14b(13b,16b(15r,17r))) R 6: 12b(8b(7b,10r(9b,11b)),14b(13b,16b(15r,17r))) R 7: 12b(10b(8b(,9r),11b),14b(13b,16b(15r,17r))) R 8: 12b(10b(9b,11b),14b(13b,16b(15r,17r))) +---- 12b ----+ +- 10b -+ +- 14b -+ 9b 11b 13b +- 16b -+ 15r 17r -- -- David -- /-----------------------------------------------------------------------\ \ David Bolen \ E-mail: db3l@fitlinxx.com / | FitLinxx, Inc. \ Phone: (203) 708-5192 | / 860 Canal Street, Stamford, CT 06902 \ Fax: (203) 316-5150 \ \-----------------------------------------------------------------------/