|
Union-Find Problem Given a set {1, 2, …, n} of n elements.
Initially each element is in a different set.
{1}, {2}, …, {n}
An intermixed sequence of union and find operations is performed.
A union operation combines two sets into one.
Each of the n elements is in exactly one set at any time.
A find operation identifies the set that contains a particular element.
Application of trees (not binary trees) and simulated pointers. Simple application of simulated pointers; one that does not require an explicit storage management system.
In this application we are concerned with the time taken to perform an intermixed sequence of operations rather than the time for an individual operation.
|
|