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 22:35:23 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!kibo.news.demon.net!news.demon.co.uk!demon!pogner.demon.co.uk!zap!not-for-mail
From: Simon Wright <simon@pushface.org>
Newsgroups: comp.lang.ada
Subject: Re: Grace and Maps (was Re: Development process in the Ada community)
Date: 23 Apr 2002 06:21:48 +0100
Organization: Pushface
Message-ID: <x7vn0vv0z2r.fsf@smaug.pushface.org>
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>
 <a9n0tk$6fs$1@nh.pace.co.uk>
 <4519e058.0204190529.559a47ae@posting.google.com>
 <a9p98h$8hn$1@nh.pace.co.uk> <3CC1C6B3.6060306@telepath.com>
 <3CC21747.5000501@telepath.com> <V+UgdHreGTJg@eisner.encompasserve.org>
 <x7vr8l871it.fsf@smaug.pushface.org> <4519e058.0204220534.2eb33730@posting.go
 <3CC4E9DA.E02BE0DA@san.rr.com>
NNTP-Posting-Host: localhost
X-NNTP-Posting-Host: pogner.demon.co.uk:158.152.70.98
X-Trace: news.demon.co.uk 1019540088 nnrp-08:16686 NO-IDENT
 pogner.demon.co.uk:158.152.70.98
X-Complaints-To: abuse@demon.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
NNTP-Posting-Date: 23 Apr 2002 05:21:48 GMT
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1
Xref: archiver1.google.com comp.lang.ada:22966
Date: 2002-04-23T05:21:48+00:00
List-Id: <comp.lang.ada>

Darren New <dnew@san.rr.com> writes:

> I'm not sure why a hashtable wouldn't have a worst-case time of O(N)
> (if all the elements hash to the same value) or how you'd guarantee
> any particular limit on execution time of inserting a value (for
> example, in the same case). In contrast, a red-black tree is *never*
> going to see O(N) time in any operation.

I would have expected a hash table to have O(N) anyway, at least for
searching; it's just that the multiplier is reduced by the number of
hash buckets.

This is certainly the case for the BCs, now you all come to mention
it! Insertion is constant time, though.

Are red-black trees much better than AVL trees (which is what you get
in the BCs)?