I was wondering if anyone has implemented a Balanced Ternary Tree module for haskell. According to http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm this would be a better datastructure for symbol tables than the binary tree I am currently using: * Each string is a key, which makes for O(n/2 * log m) comparisons where n is the average string length and m is the number of string in the table, * A balanced ternary tree would be O(n + log m). (DDJ's code does not balance the tree) Sengan
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
participants (2)
-
Andrew J Bromage -
Sengan.Baring-Gould＠nsc.com