According to the lecture of Richard Karp, a Union-Find data structure maintains a partition of a set X of size n. For each set A in the partition it maintains a representative S(A) contained in A. The initial partition has each element in a set by itself. An union find algorithm is a kind of algorithm that performs two kinds of useful operations on such a data structure. In analyzing the Union-Find data structure, a node in the Union-Find data-structure is a leader if it is the root of a (reversed) tree.
- Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set.
- Union: Combine or merge two sets into a single set.
There are also trees in Union-Find algorithms:
Reversed Trees
One of the easiest ways to store sets is using trees, in which each node represents a single element of the set. Each node points to another node, called its parent, except for the leader of each set, which points to itself and thus is the root of the tree. MAKESET is trivial. FIND traverses parent pointers up to the leader. UNION just redirects the parent pointer of one leader to the other. Unlike most tree data structures, nodes do not have pointers down to their children.
Shallow Threaded Trees
Alternately, we could just have every object keep a pointer to the leader of its set. Thus, each set is represented by a shallow tree, where the leader is the root and all the other elements are its children. With this representation, MAKESET and FIND are completely trivial. Both operations clearly run in constant time. UNION is a little more difficult, but not much. Our algorithm sets all the leader pointers in one set to point to the leader of the other set. To do this, we need a method to visit every element in a set; we will ‘thread’ a linked list through each set, starting at the set’s leader. The two threads are merged in the UNION algorithm in constant time.
References:
compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/.../10-unionfind.pdf
www.cs.duke.edu/courses/cps100e/fall09/notes/UnionFind.pdf
www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN6.pdf
