Re: Red-black trees?



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.
.