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-Thread: 11232c,2769c8e90db887c7,start X-Google-Attributes: gid11232c,public X-Google-ArrivalTime: 2002-04-22 23:26:49 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.tele.dk!small.news.tele.dk!212.177.105.133!news.mailgate.org!mygate.mailgate.org!198.207.153.205!not-for-mail From: "Kent Paul Dolan" Newsgroups: comp.lang.ada,misc.misc Subject: Re: Grace and Maps (was Re: Development process in the Ada community) Date: Tue, 23 Apr 2002 06:26:48 +0000 (UTC) Organization: Mailgate.ORG Server - http://www.Mailgate.ORG Message-ID: 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> <3CC48F34.5A474E0F@boeing.com> <3CC49C50.485AE213@san.rr.com> <3CC4B5C0.4D16077C@acm.org> NNTP-Posting-Host: 198.207.153.205 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: news.mailgate.org 1019531020 29175 198.207.153.205 (Tue Apr 23 08:26:48 2002) X-Complaints-To: abuse@mailgate.org NNTP-Posting-Date: Tue, 23 Apr 2002 06:26:48 +0000 (UTC) Injector-Info: news.mailgate.org; posting-host=198.207.153.205; posting-account=48257; posting-date=1019531020 User-Agent: Mailgate Web Server X-URL: http://mygate.mailgate.org/mynews/comp/comp.lang.ada/ff8eeb5cb4fbaa66bf03c0e070ad4622.48257%40mygate.mailgate.org Xref: archiver1.google.com comp.lang.ada:22971 misc.misc:6818 Date: 2002-04-23T06:26:48+00:00 List-Id: "Jeffrey Carter" wrote: > Darren New wrote: > > Jeffrey Carter wrote: > > > 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. No, the balance need only be _checked_ after every modification; many insertions or deletions leave the tree in balance, and rebalancing is still a cheap operation. It's been a while, but I thought that for many, the amortized cost of insertion and deletion was still order log N? The TreeSet that I used in Java derived from a class with that software contract. > > Well, that's why you use something a little more sophisticated, like a > > red-black tree, or a B-tree if your memory I/O works in blocks (like a > > disk). > Maybe my memory is faulty, but I seem to recall that these trees still > need rebalancing to maintain O(log N) search times. Yes, you are correct; free lunches are still scarce. xanthian. -- Posted via Mailgate.ORG Server - http://www.Mailgate.ORG