Class PathCompressionWeightedQuickUnionDisjointSet

A WeightedQuickUnionDisjointSet refinement which improves the performance of the data structure by performing a technique known as path compression.

Inheritance
System.Object
QuickUnionDisjointSet
WeightedQuickUnionDisjointSet
PathCompressionWeightedQuickUnionDisjointSet
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.DisjointSets
Assembly: MoreStructures.dll
Syntax
public class PathCompressionWeightedQuickUnionDisjointSet : WeightedQuickUnionDisjointSet, IDisjointSet
Remarks

This variant of WeightedQuickUnionDisjointSet introduces a refinement of the Find(Int32) method, inherited by its upper classes.
The Find(Int32) algorithm remains unchanged in its core.
However, it produces a flatter forest as side-effect, every time is executed on a value.
Check the documentation of Find(Int32) for further details.

Constructors

| Improve this Doc View Source

PathCompressionWeightedQuickUnionDisjointSet(Int32)


Initializes the ranks of all singleton trees to 0.

Declaration
public PathCompressionWeightedQuickUnionDisjointSet(int valuesCount)
Parameters
Type Name Description
System.Int32 valuesCount

Methods

| Improve this Doc View Source

Find(Int32)

Declaration
public override int Find(int value)
Parameters
Type Name Description
System.Int32 value
Returns
Type Description
System.Int32
Overrides
Remarks

ALGORITHM
- The algorithm is pretty much like Find(Int32), with one main difference.
- The difference lies in path compression: once the root of the tree is found, a second traversal, from the value up to its root, is performed.
- During the second traversal, each node in path is directly attached to the root.
- That keeps the disjoint set equivalent to its previous state, by transitivity of the equivalence relationship.
- However, it makes the tree much more flat, and the average height of all the nodes in the forest smaller.
- That means that future Find(Int32), but also Union(Int32, Int32) and AreConnected(Int32, Int32), will be much faster, since it's faster to reach the root of each tree.

COMPLEXITY
- Find the root takes a time proportional to the height of the tree, the item is in.
- Because path compression keeps trees very flat, incrementing the fan out, while the complexity is not constant and there is definitely a dependence over n, it is a sub-logarithmic dependency.
- More precisely, Time Complexity is O(log*(n)), which can be considered "pseudo-constant" for any "real world" value of n.
- Space Complexity remains O(1), since only a constant amount of additional space is required to run the algorithm.

Implements

Extension Methods