Disjoint-Set Data Structures

Overview

A disjoint-set data structure maintains a collection $S=\{S_1,S_2,\dots ,S_k\}$ of disjoint dynamic sets. Each set is identified by a representative, which is some member of the set. Generally speaking, a disjoint-set data structure supports the following operations:

• MAKE-SET(x)
  • Where x does not belong to some other set, creates a new singleton set containing x.
• UNION(x, y)
  • Unites two disjoint sets, dynamic sets containing x and y, into a new set that is the union of these two sets.
• FIND-SET(x)
  • Returns the representative of the set containing x.

Linked List

In a standard linked list representation, each disjoint set is represented by an object containing a linked list. The object has a head pointer to the first entry in the list and a tail pointer to the last. Each set member contains a pointer back to the object itself. The representative is the first entry in the list.

• MAKE-SET(x) constructs a new linked list containing just the x entry.
• FIND-SET(x) follows the pointer from x back to the linked list.
• UNION(x, y) moves the entries of y to the end of x.

The UNION operation can be improved via the weighted-union heuristic in which the shorter list is always appended to the longer list.

Disjoint-Set Forest

In a disjoint-set forest representation, each disjoint set is represented by a tree. The members of the set correspond to nodes in the tree. Each node points only to its parent, and the root node is its own parent. The representative of the set is the root of the tree.

• MAKE-SET(x) constructs a new tree containing just x as the root.
• FIND-SET(x) follows the parent pointers starting at x up to the root.
• UNION(x, y) updates the root of y to point to the root of x.

The UNION operation can be improved via two heuristics:

1. Union by rank. Each node maintains a rank corresponding to the upper bound on the height of the node. Roots with smaller rank point to roots with larger rank during a UNION operation.
2. Path compression. Each node on the find path, the path from a node up to its root, is updated to point to the root during a FIND-SET operation.