Re: [boost] Union/find and splay trees

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2000-07-08 16:53:51

Hi,

--- "Michael S. Tsirkin" <mtsirkin_at_[hidden]> wrote:
> the problem that I am solving is: have an implementation for
> set container, that also allows efficient union/find.
> 
> That is, after doing some union/finds, I want to get all
> elements in a specific set, etc
> Lookup of elements by value is also possible (although I am
> not using it at the moment).
> 
> To implement this with data structure from CLR I would need
> to add pointers from parent to children.
> I estimate that this doubles the memory overhead.

Actually, I got the union/find algorithm slightly wrong: To get the
excellent performance, some auxiliary data called "rank" also has to be
maintained. That is, the overhead for the union/find algorithm would be
two words (a pointer and a rank). To find all elements in a set
efficiently another pointer would be necessary. Thus, the total
memory overhead would be three words per element. ... but the
implementation would still be rather simple. If you need to find an
element in this data structure by some key, the performance would
basically be linear. Thus, if you need to find elements with a key,
this is probably not the right data structure...

Regards,
  Dietmar

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

__________________________________________________
Do You Yahoo!?
Get Yahoo! Mail – Free email you can access from anywhere!
http://mail.yahoo.com/