[boost] Union/find and splay trees

From: jsiek_at_[hidden]
Date: 2000-07-07 19:52:37

Hi Michael,

The GGCL library has an implementation of the disjoint set algorithm
with the union by rank and path compression optimizations (see the
distjoint_set class).  The algorithm used is the one described in
"Introduction to Algorithms" by Cormen, Leiserson, Rivest.

I'm currently trying to catch up with a backlog of email... so
it will take some time to catch up with the rest of the discussion
between Michael and Deitmar...

Cheers,

Jeremy

Michael S. Tsirkin writes:
 > 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)
 > 
 > ------------------------------------------------------------------------
 > Where do sports heroes like Derek Jeter, Mia Hamm,
 > Vince Carter and Peyton Manning hang out? Where else?
 > Click now and find ‘em all here!
 > http://click.egroups.com/1/6211/4/_/9351/_/962862200/
 > ------------------------------------------------------------------------
 > 
 > 
 >