UnionFind implementation

The Wikipedia article on the union find problem gives a very simple implementation, which I ported to C# and tested.

I know that the code should be, in the aggregate, asymptotically almost linear. But is it a practical implementation? Are there optimizations I should have used? Is there a way to cut down on the worst-case complexity of single operations?

```
using System;

///
/// A UnionFindNode represents a set of nodes that it is a member of.
///
/// You can get the unique representative node of the set a given node is in by using the Find method.
/// Two nodes are in the same set when their Find methods return the same representative.
/// The IsUnionedWith method will check if two nodes' sets are the same (i.e. the nodes have the same representative).
///
/// You can merge the sets two nodes are in by using the Union operation.
/// There is no way to split sets after they have been merged.
///
public class UnionFindNode {
private UnionFindNode _parent;
private uint _rank;

///
/// Creates a new disjoint node, representative of a set containing only the new node.
///
public UnionFindNode() {
_parent = this;
}

///
/// Returns the current representative of the set this node is in.
/// Note that the representative is only accurate untl the next Union operation.
///
public UnionFindNode Find() {
if (!ReferenceEquals(_parent, this)) _parent = _parent.Find();
return _parent;
}

///
/// Determines whether or not this node and the other node are in the same set.
///
public bool IsUnionedWith(UnionFindNode other) {
if (other == null) throw new ArgumentNullException("other");
return ReferenceEquals(Find(), other.Find());
}

///
/// Merges the sets represented by this node and the other node into a single set.
/// Returns whether or not the nodes were disjoint before the union operation (i.e. if the operation had an effect).
///
/

-
If I read the wikipedia article correctly then the algorithm should have amortized constant cost - and you have implemented it pretty much 1:1. Given that with your implementation you always start with disjoint nodes and any call to any of the public methods ends up calling Find which will automatically flatten the tree I doubt you can get much better.

-
UnionFindNode is not a particularly good name for the data structure: intermingles operations with the data structure in the name. Just Node or maybe DisjointSetNode would be better.

-
You could use == or != instead of ReferenceEquals which would make the code a bit easier to read.

-
Consider making your node class generic and add a T value property - right now your nodes are not all that useful as they don't hold any data.

StackExchange Code Review Q#42573, answer score: 5