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=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no 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-23 11:57:58 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!cyclone.bc.net!newsfeed.online.be!news.algonet.se!algonet!newsfeed1.bredband.com!bredband!newsfeed.bahnhof.se!newsfeed.sunet.se!news01.sunet.se!news.chalmers.se!legolas!nobody From: anders@legolas.gidenstam.org (Anders Gidenstam) Newsgroups: comp.lang.ada Subject: Re: Grace and Maps (was Re: Development process in the Ada community) Date: Tue, 23 Apr 2002 20:57:44 +0200 Organization: Chalmers University of Technology Message-ID: <8ra4aa.ea3.ln@legolas> 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> <3CC48F34.5A474E0F@boeing.com> <3CC49C50.485AE213@san.rr.com> Reply-To: anders@gidenstam.org (Anders Gidenstam) NNTP-Posting-Host: hotlips.cs.chalmers.se Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: nyheter.chalmers.se 1019588271 17874 129.16.225.36 (23 Apr 2002 18:57:51 GMT) X-Complaints-To: abuse@chalmers.se NNTP-Posting-Date: 23 Apr 2002 18:57:51 GMT X-Newsreader: knews 1.0b.1 Xref: archiver1.google.com comp.lang.ada:23001 Date: 2002-04-23T18:57:51+00:00 List-Id: In article <3CC49C50.485AE213@san.rr.com>, Darren New writes: > 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. > > 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). > Just to add one more possible implementation data structure, there is also the random treap, which at least is a bit easier to implement than an AVL tree. The random treap is a search tree w.r.t the element keys and a heap w.r.t an extra field that is assigned a random (uniformly distributed) value when the element is inserted in the tree. This will, with a high probability, keep the tree well balanced. All operations are (amortized) O(log N). I read about them in a course and have a simple implementation on my (old) homepage: http://www.dtek.chalmers.se/~d96andgi/Ada/ /Anders -- -------------------------------------------- "A well-written program is its own heaven; a poorly-written program is its own hell." - The Tao of Programming