The abstract data type Union-Find
The ADT Union-Find (also known as "Disjoint Sets" and
"Dynamic Equivalence Relation") keeps track of a partition
of a set of elements (which may grow with time) into pairwise disjoint
and nonempty equivalence classes (which may change through
a merger of two classes into one from time to time); it is specified
by
- one access function, namely,
uf_name uf_find(uf_object *object)
-
that, given a pointer to an object held in the ADT
returns the name of the equivalence class to which the object belongs;
- two manipulator functions, namely,
void uf_make_set(uf_object *new_object)
-
that, given a pointer to an object not held in the ADT,
adds the new object to the data structure as a single-element
equivalence class;
void uf_union(uf_name class1, uf_name class2)
-
that, given given names of two equivalence classes,
merges these two classes into one.
The data type uf_object is provided by the ADT user; the
data type uf_name is chosen by the designer of the data
structure that implements the ADT. In implementing Union-Find, we
will assume that the data type uf_object is a structure
and that the ADT designer may choose to include additional elements in
this structure.
Implementing Union-Find as disjoint in-trees
In this implementation, each structure of type uf_object
includes an element parent that points to a
uf_object; each equivalence class is a tree and its
"name" is a pointer to the root of the tree. The roots point
to themselves (which is just a convention; they could as well point to
NULL).
uf_name uf_find(uf_object *object)
{
uf_object *root;
for(root=object; root->parent!=root; root=root->parent);
return root;
}
void uf_make_set(uf_object *new_object)
{
new_object->parent=new_object;
}
void uf_union(uf_name class1, uf_name class2)
{
class1->parent=class2;
}
Implementing Union-Find as disjoint in-trees with collapsing find
and union by rank
A remarkably efficient implementation of Union-Find uses disjoint
in-trees with two simple enhancements, which are designed to keep
the trees shallow. The first of them is collapsing find:
after we have found the root of the tree that holds *object,
we retrace the path from *object to *root once
more and suspend all of its nodes directly (rather than indirectly) below
*root:
uf_name uf_find(uf_object *object)
{
uf_object *root, *next;
for(root=object; root->parent!=root; root=root->parent);
for(next=object->parent; next!=root; object=next, next=object->parent)
object->parent=root;
return root;
}
The other enhancement is an informed choice of the new root in
uf_union: ideally, we would like the new root to come
from the deeper of the two trees. Unfortunately, keeping track of the
depth (which may change with each collapsing find) could be an
expensive proposition; fortunately, the choices suggested by depth are
well approximated by choices based on the notion of rank that
is defined as follows. Initially, each of the one-point equivalence
classes has rank 0; when two roots of an equal rank compete (fair
fight) for the distinction of becoming the root of the union, the
winner is chosen arbitrarily and its rank is then incremented by one;
when two roots of unequal rank compete (unfair fight) for the
distinction of becoming the root of the union, the root of the higher
rank wins. (A summary: your rank is the number of fair fights that you
have won.) This enhancement requires maintaing rank as an
extra element in the structure uf_object.
void uf_make_set(uf_object *new_object)
{
new_object->parent=new_object, new_object->rank=0;
}
void uf_union(uf_name class1, uf_name class2)
{
if(class1->rank < class2->rank)
class1->parent=class2;
else
{
class2->parent=class1;
if(class1->rank==class2->rank)
(class1->rank)++;
}
}