From: Michael S. Tsirkin (mtsirkin_at_[hidden])
Date: 2000-07-08 16:34:30
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
-- 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)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk