Re: [boost] Union/find and splay trees

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-07-06 06:52:51

John Potter and I have been working on a kind of "generalized associative
container" framework. The implementations we've done are based on linear
containers (e.g. vector), which are often faster and almost always smaller
than their more "theoretically efficient" counterparts. We got to the point
of postulating that we might be able to use the common (hidden) rb_tree
interface as a common substrate with a bunch of adapters to make it look
like set, multimap, etc. If your splay trees look anything like that, it
might be useful here. See associative.zip in the files section.

-Dave

----- Original Message -----
From: "Michael S. Tsirkin" <mtsirkin_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, July 06, 2000 1:43 AM
Subject: [boost] Union/find and splay trees

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