Union/find and splay trees

From: Michael S. Tsirkin (mtsirkin_at_[hidden])
Date: 2000-07-06 00:43:16

Hello!
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.
 
Thank you,
    MST

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