Class UnionFind

java.lang.Object
EDU.purdue.cs.bloat.util.UnionFind
public class UnionFind extends Object
Represents the union-find data structure.

Sometimes we need to group elements into disjoint sets. Two important operations of these sets are finding the set that contains a given element ("find") and uniting two sets ("union"). UnionFind provides an efficient implementation of a data structure that support these operations on disjoint sets of integers.

Each disjoint set is represented by a tree consisting of Nodes. (This Node is a class local to UnionFind and should not be confused with tree.Node.) Each Node knows its parent and child and has a rank associated with it. The parent node is always the root node of the set tree. A Node's rank is essentially the height of the (sub)tree rooted by that node. When the union of two trees is formed, the root with the smaller rank is made to point to the root with the larger rank. Naturally, each Node has an integer "value" associated with it.

A good description of union-find can be found in [Cormen, et. al. 1990].

  • Constructor Summary

    Constructors
    Constructor
    Description
    UnionFind()
    Constructor.
    UnionFind(int size)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    find(int a)
    Returns the integer value associated with the first Node in a set.
    EDU.purdue.cs.bloat.util.UnionFind.Node
    findNode(int a)
    Searches the disjoint sets for a given integer.
    boolean
    isEquiv(int a, int b)
    Returns true if a and b are in the same set.
    void
    union(int a, int b)
    Combines the set that contains a with the set that contains b.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • UnionFind

      public UnionFind()
      Constructor.

    • UnionFind

      public UnionFind(int size)
      Constructor. Make a UnionFind with a given number of disjoint sets.

  • Method Details

    • findNode

      public EDU.purdue.cs.bloat.util.UnionFind.Node findNode(int a)
      Searches the disjoint sets for a given integer. Returns the set containing the integer a. Sets are represented by a local class Node.

    • find

      public int find(int a)
      Returns the integer value associated with the first Node in a set.

    • isEquiv

      public boolean isEquiv(int a, int b)
      Returns true if a and b are in the same set.

    • union

      public void union(int a, int b)
      Combines the set that contains a with the set that contains b.