Re: [boost] Union/find and splay trees

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2000-07-06 08:05:40

Hi,

--- "Michael S. Tsirkin" <mtsirkin_at_[hidden]> wrote:
> Does there exist a library for union/find type of problem?

I don't have a current implementation but the union/find algorithm is
very simple and very powerful. But before sketching the "correct"
algorithm, let me point out how union/find should be view!

A typical approach is to use a special data structure (eg. a collection
of trees) where the elements are registered. This is, IMO, the wrong
approach. It is superior to consider the representative of set as a
property of an element where the elements are identified by the same
kind of entities used to represent the representative. Maybe this sound
familiar to some people on the list: Use a property accessor to access
the representative of an element. In principle uniting two sets can
also be done via the normal property accessor methods but probably
using a special function, eg. 'unit()', instead.

Some information on property accessors can be found in the graph
directory where this stuff is kind of essential. However, eg. for the
union/find stuff it is also applicable for other uses.

> I have written a simple library that uses a forest of
> splay trees to solve this in O(NlogN), with low memory overhead.

I think the best algorithm (which also happens to be *much* simpler
than a splay tree) uses O(n * inverse(Ackermann(n))) or something like
this (don't nail me down on the details). The algorithm is rather
simple: Individual elements, ie. set containing only on element, are
represented by themselves and simply store a "pointer" to themselves.
When uniting two sets, the pointer in one of the representives is
replaced by the pointer to the other representative. When looking for
a representative for a given element, the chain is walked up and the
current pointers in the nodes encountered are replaced by a pointer to
the representative (there are some variations on this and I don't know
exactly which is theoretically or practically best approach; as far as
I remember, these differ...). That's all.

I can probably dig up some old implementation or hack a new one if
there is interest...

Regards,
  Dietmar

=====
<mailto:dietmar_kuehl_at_[hidden]>
<http://www.dietmar-kuehl.de/>

__________________________________________________
Do You Yahoo!?
Send instant messages & get email alerts with Yahoo! Messenger.
http://im.yahoo.com/