Data Structures for Disjoint
Set
Data Structures and Algorithms
1
DSaA 2012/2013
Data Structures for Disjoint Set
Data Structures for Disjoint Set:
" linked-list
" disjoint-set forests
2
DSaA 2012/2013
Disjoint-set data structure
S =ð{ðS1, S2,Kð, Sk}ð
A disjoint-set data structure maintains a collection
of disjoint dynamic sets. Each set is identified by a representative, which is
some member of the set. In some applications, it doesn't matter which
member is used as the representative; we only care that if we ask for the
representative of a dynamic set twice without modifying the set between the
requests, we get the same answer both times. In other applications, there
may be a prespecified rule for choosing the representative, such as choosing
the smallest member in the set (assuming, of course, that the elements can
be ordered).
As in the other dynamic-set implementations we have studied, each element of
a set is represented by an object. Letting x denote an object, we wish to
support the following operations:
" Make_Set(x) creates a new set whose only member (and thus
representative) is x. Since the sets are disjoint, we require that x not already
be in some other set.
" Union(x, y) unites the dynamic sets that contain x and y, say Sx and Sy,
into a new set that is the union of these two sets. The two sets are assumed
to be disjoint prior to the operation. The representative of the resulting set is
any member of SxUSy, although many implementations of Union specifically
choose the representative of either Sx or Sy as the new representative. Since
we require the sets in the collection to be disjoint, we "destroy" sets Sx and
Sy, removing them from the collection S.
" Find_Set(x) returns a pointer to the representative of the (unique) set
containing x.
3
DSaA 2012/2013
Linked-list representation
" A simple way to implement a disjoint-set data structure is to
represent each set by a linked list.
" The first object in each linked list serves as its set's representative.
Each object in the linked list contains a set member, a pointer to the
object containing the next set member, and a pointer back to the
representative. Each list maintains pointers head, to the
representative, and tail, to the last object in the list
c h e b f g d
c h e b f g d
Union(e,g)
4
DSaA 2012/2013
Simple implementation
" Make_Set(): O(1)
" Find_Set(): O(1)
" Union(): amortized time = Åš(m) for
each of m=Åš(n) operations
q-ð1
q-ð1
operation Number of actualized objects
Make_Set(x1) 1
åði =ð Qð(ðq2)ð
åði =ð Qð(ðq2)ð
i=ð1
i=ð1
Make_Set(x2) 1
& &
Make_Set(xn) 1
Qð(n +ð q2)
Union(x2,x1) 1
Union(x3,x2) 2
Union(x4,x3) 3
Qð(m2)
m operations
& &
Union(xq-1,xq) q-1
1 operation Qð(m)
5
DSaA 2012/2013
Weighted-union heuristic
Each list also includes the length of the list (which
is easily maintained) and that we always append
the smaller list onto the longer.
For m=Åš(n) operations, n of which are
Make_Set operations, amortized time for
all operation is equal Åš(m + n log n)
6
DSaA 2012/2013
Disjoint-set forests
In a disjoint-set forest each member points only
to its parent. The root of each tree contains the
representative and is its own parent.
f
c f
c
h e d
d
h e
b g
g
b
Union(e,g)
7
DSaA 2012/2013
Heuristics
" union by rank
" path compression during Find_Set()
f
e
f
d
a b c d e
c
path compression during
b
Find_Set(a)
a
8
DSaA 2012/2013
Disjoint-set forests - codes
Make_Set(x)
{ 1} p[x]:=x
{ 2} rank[x]:=0
Union(x,y)
{ 1} Link(Find_Set(x),Find_Set(y))
Link(x,y)
{ 1} if rank[x]>rank[y] then
{ 2} p[y]:=x
{ 3} else
{ 4} p[x]:=y
{ 5} if rank[x]=rank[y] then
{ 6} rank[y]:=rank[y]+1
Find_Set(x)
{ 1} if x!=p[x] then
{ 2} p[x] := Find_Set(p[x])
{ 3} return p[x]
9
DSaA 2012/2013
Disjoint-set forests - complexity
" If, in m operations, there are n Make_Set operations
(and hence at most n  1 Union operations) the path-
compression and rank heuristic together gives a worst-
case running time of O(m Ä…(m,n)), where Ä…(m,n) is a very
slowly growing function (Ackermann function). In any
conceivable application of a disjoint-set data structure,
Ä…(m,n) d" 4; thus, we can view the running time as linear
in m in all practical situations.
10
DSaA 2012/2013