dsu-tree

A non-invasive implementation of a disjoint-set tree data structure, written in Rust.

Disjoint-Set Tree

Disjoint sets data structure, or DSU, or union-find data structure, or merge- find set, is a data structure that stores a collection of disjoint sets. It provides operations for adding new sets, merging sets (equivalent to replacing the sets with the union of them) and finding the representative member of a set. DSU is very useful in implementing algorithms like minimum spanning tree and more.

DSU can be implemented with its extreme efficiency by using disjoint-set trees. Disjoint-set trees are actually a forest in which each node represents a set and each tree represents the union of sets that are merged together. The three DSU operations can be implemented as follows:

• Adding new sets: Easy. Just add new nodes to the forest and it's done. The new nodes are themselves a tree in the forest to indicate that they have not been merged with other sets.
• Merging sets: To merge two sets whose corresponding nodes are A and B, respectively, we just change the parent node of A to B and it's done. In real implementations, some corner cases need to be considered, such as merging a set into itself.
• Finding the representative member of a set: Each tree within the disjoint-set trees represents a set. The representative member of a set can be chosen to be the representative member of the set corresponding to the root node of the tree.

This Crate

Rather than implementing a disjoint-set data structure, this crate provides the implementation of the underlying disjoint-set tree data structure.

For the usage of this library, please refer to the documentation.

License

This library is open-sourced under MIT License.