# Re: Red-black trees?

*From*: CBFalconer <cbfalconer@xxxxxxxxx>*Date*: Mon, 17 Nov 2008 17:28:10 -0500

Jon Harrop wrote:

CBFalconer wrote:.... snip ...

Several times I have referenced my published hashlib library. The

published code include all you want. To ease access, see:

<http://cbfalconer.home.att.net/download/hashlib.zip>

which can also be accessed by following my page, in the sig below.

Your "organize" function is O(n) so insertion via "hshinsert" is

O(n). So operations on your hash table implementation are not all

O(1) as you claimed.

Balanced trees are only O(log n).

Are you really that slow? That function develops a linked list

from the hashtable contents. The hashtable operation is O(1). The

O(n) operation happens after all the O(1) insertions, so the net

cost of an insertion and inclusion in the list remains as O(1).

It is easy to develop an input mechanism that doesn't use the hash

table, but simply forms a linked list of all input strings.

--

[mail]: Chuck F (cbfalconer at maineline dot net)

[page]: <http://cbfalconer.home.att.net>

Try the download section.

.

**Follow-Ups**:**Re: Red-black trees?***From:*Jon Harrop

**References**:**Re: Red-black trees?***From:*Mark Wooding

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*Mark Wooding

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*Mark Wooding

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

**Re: Red-black trees?***From:*CBFalconer

**Re: Red-black trees?***From:*Jon Harrop

- Prev by Date:
**Re: fast stable sort** - Next by Date:
**Re: fast stable sort** - Previous by thread:
**Re: Red-black trees?** - Next by thread:
**Re: Red-black trees?** - Index(es):