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 16:37:14 PST Newsgroups: comp.lang.ada Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!headwall.stanford.edu!newsfeed.utk.edu!washdc3-snf1!washdc3-snh1.gtei.net!cpk-news-hub1.bbnplanet.com!news.gtei.net!nntp.abs.net!uunet!dca.uu.net!ash.uu.net!xyzzy!nntp From: Jeffrey Carter Subject: Re: Grace and Maps (was Re: Development process in the Ada community) X-Nntp-Posting-Host: e246420.msc.az.boeing.com Content-Type: text/plain; charset=us-ascii Message-ID: <3CC73BF1.C08EAA89@boeing.com> Sender: nntp@news.boeing.com (Boeing NNTP News Access) Content-Transfer-Encoding: 7bit Organization: The Boeing Company X-Accept-Language: en 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 <3CC6EA85.CA2735B2@boeing.com> <3CC6F022.D0179BE2@san.rr.com> Mime-Version: 1.0 Date: Wed, 24 Apr 2002 23:12:49 GMT X-Mailer: Mozilla 4.73 [en]C-CCK-MCD Boeing Kit (WinNT; U) Xref: archiver1.google.com comp.lang.ada:23088 Date: 2002-04-24T23:12:49+00:00 List-Id: Darren New wrote: > > Jeffrey Carter wrote: > > With the recommended p=0.25, they take an average of 1.333 > > pointers/node. > > This would degrade performance, tho, yes? An average of two extra > link-follows per search? Or am I misunderstanding? (Maybe "p" should be > a parameter? Nah, too messy.) It increases the probability that a search path is longer than expected compared to p=0.5. But with N=256 and p=0.25, the probability of a search path of 3*log N (24) is about 0.001. > > A *little* more complicated? I've seen balanced tree deletion algorithms > > in texts that run to 4 pages; > > Nah. > http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/red_black.html > Not *that* complicated. I'll admit it's not *obvious*, but once given, > it's not *complicated*. On the other hand, skip-list implementations are > *obvious*, but whether they're efficient isn't obvious. Of course, the > paper shows they are. Let's see, the else part is just as long as the if part, so the insert is really nearly twice as long as shown, 1.5-2 pages in a text. Full code for both rotations is another page, and your basic tree insertion is another page, so that's getting on to 4 pages. At least it's not recursive. One of the advantages of skip lists is that there's really only 1 way to implement insert and delete. With most balanced trees the easier way is with recursion, and eliminating that recursion is complicated enough that most people don't try. > Fair enough. I'm convinced. :-) Add a backpointer to each node as well, > and you've got a doubly-linked list that you can search really, really > fast. :-) But now I'm starting to like red-black trees ... :) -- Jeffrey Carter