Re: [boost] Union/find and splay trees

From: Michael S. Tsirkin (mtsirkin_at_[hidden])
Date: 2000-07-08 16:34:30

Hello, Dietmar!
Thank you for your insight.

Quoting r. Dietmar Kuehl (dietmar_kuehl_at_[hidden]) "Re: [boost] Union/find and splay trees":
> > Maybe the textbook that I used was not very good, but
> > 1- it gave a much more complex algorithm ( I do not understand
> > exactly what you write, but it took more than two lines :)  )
> > and there was more memory overhead than splay trees, where
> > you pay only for 3 pointers per value stored.
> 
> Maybe you want to do something different than union/find...? My
> understanding of union/find is that you want to determine whether two
> objects are in the same set. ... and this efficiently. 

I have to apologize that the terminology I used is not precise:
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.

Am I overlooking some simpler implementation with the same
memory overhead?

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)