Re: [boost] Union/find and splay trees

From: Kevin Atkinson (kevina_at_[hidden])
Date: 2000-07-06 13:12:53

On Thu, 6 Jul 2000, Dietmar Kuehl wrote:

> 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). 

Which is about n log2*(n)

Where log2* is the iterative log function base 2.  That is the number of
times it is necessary to apply log2 to n to get it below 1.    This
function grows VERY slowly so it is considered to be nearly constant:

log2*(3)           = 2
log2*(8   = 2^3)   = 3
log2*(256 = 2^8)   = 4
log2*(2^256)       = 5

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

This won't give the above performance.  I will elaborate on the details
when I get home (so that I can look it up in my text book) if anyone is
interested.

-- 
Kevin Atkinson
kevina at users sourceforge net
http://metalab.unc.edu/kevina/