From: Michael S. Tsirkin (mtsirkin_at_[hidden])
Date: 2000-07-06 00:43:16
Does there exist a library for union/find type of problem?
I have written a simple library that uses a forest of
splay trees to solve this in O(NlogN), with low memory overhead.
[This is not optimal in terms of speed, AFAIK , but memory overhead
would have to be higher]
The forest of splay trees class migth have other uses
(e.g. as a replacement to "map": it has lower memory overhead
per node as compared to the standard RB tree implementation-
-does not need the "color" bit- while providing amortized
O(ln N) time for operations, as opposed to O(ln N) for one
operation in an RB tree - as usual speed/ memory tradeoff).
It might also be useful for teaching teh data structures course :)
My implementation is templated to allow keeping different
types of data in the nodes, and uses STL-like iterators for access,
to simplify the usage.
I would like to know:
- Does someone have another implementation , that I can compare
with in terms of memory/speed?
- Is someone interested in my implementation of this library?
If yes, I think I could publish the library to teh public domain.
-- This message content is not part of Intel's views or affairs Michael S. Tsirkin > Four things are to be strengthened: Torah,and good deeds, > prayer and one's good manners (Berachoth)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk