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-22 19:32:17 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!deine.net!amsnews01.chello.com!news-hub.cableinet.net!blueyonder!cox.net!news2.east.cox.net.POSTED!53ab2750!not-for-mail Message-ID: <3CC4C800.10107@telepath.com> From: Ted Dennison User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.7) Gecko/20011221 X-Accept-Language: en-us MIME-Version: 1.0 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 <3CC48F34.5A474E0F@boeing.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Date: Tue, 23 Apr 2002 02:32:12 GMT NNTP-Posting-Host: 68.12.51.201 X-Complaints-To: abuse@cox.net X-Trace: news2.east.cox.net 1019529132 68.12.51.201 (Mon, 22 Apr 2002 22:32:12 EDT) NNTP-Posting-Date: Mon, 22 Apr 2002 22:32:12 EDT Organization: Cox Communications Xref: archiver1.google.com comp.lang.ada:22952 Date: 2002-04-23T02:32:12+00:00 List-Id: Jeffrey Carter wrote: > Trees also have the advantage that they do not waste space. ...which is something we are already agreeing to trade off when we make a structure bounded. > The trouble with a tree is that, if it is not balanced, operations can > be O(N) in the worst case. If the tree is balanced, searching is O(log > N), but insertion and deletion are slow, because the tree must be > rebalanced after every modification. Exactly. > This is why I use skip lists. They do not waste space, and operations > are O(log N) but no rebalancing is needed after modification. Hmmm. I'm unfamiliar with skip lists. (quick web search ensues) It looks like they are probability based, which means that in the worst case it could still behave like a linked-list.