Balanced ternary tree

Andrew J Bromage ajb@spamcop.net
Wed, 11 Sep 2002 10:10:17 +1000


G'day all.

oOn Tue, Sep 10, 2002 at 03:39:26PM -0400, Sengan.Baring-Gould@nsc.com wrote:

> I was wondering if anyone has implemented a Balanced Ternary Tree
> module for haskell.

Odd you mention that.  Just about finished one myself:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/hfl/hfl/edison/Assoc/

Note in particular TernaryTrie.hs.  The basic operations all work, but
some of the advanced operations (e.g. intersect, subset, unionWithKey)
are not optimised yet.

I'd appreciate it if you'd let me know how well it works for you,
especially performance-wise.

> (DDJ's code does not balance the tree)

This one does.

Cheers,
Andrew Bromage