1 of 6

CSE525 Lec14

Disjoint-set

Debajyoti Bera (M19)

https://sites.google.com/a/iiitd.ac.in/cse525-m19

​

2 of 6

Disjoint-Set data structure

Maintain a collection of disjoint-sets and support the following operations. Every set has a unique identifier - for this lecture, identifier must be a “leader” element in the set. Leader implicitly indicates a set.

{ 3 , 19 , 10 , -2 } { 12 , 5 , AB , 7 } { 43, 12, 51, Q }

  • MakeSet(x): Create a new set {x}. Leader is x.
  • Find(x): Return the leader of the set containing x.
  • Union(A,B) or Union(x,y): Replaces two sets A & B (or Find(x) and Find(y)) by their union. Return leader of the new set.
  • No duplicates.

3 of 6

Disjoint-Set using reversed trees

Complexity of …

  • Makeset
  • Find
  • Union

Give a technique to generate a sequence of ops. on n elements so that Find(x) takes Ө(n) time.

4 of 6

Reversed-Trees + Union-by-depth

During union, join the shorter tree to the root of the deeper tree (not the other way).

Q: How to know “shorter” and “deeper” ?

Lemma: For any set A, |A| >= 2depth(A). [ ⇒ depth(A) <= log(#elements of A) ]

Proof:

Q: How are the complexities affected?

  • … of MakeSet
  • … of Find
  • … of Union

O(1)

Ө(log n)

Ө(log n)

Let x = leader of A. Induction on the size of the set with x as leader.

5 of 6

Shallow Reversed Trees + Threading

Complexity of …

  • Makeset
  • Find
  • Union

Give a technique to generate a sequence of ops. on n elements so that Union(x) takes Ө(n) time on average.

6 of 6

Shallow Reversed Trees + Threading + Wtd Union

During union, join the smaller tree to the root of the larger tree (not the other way).

Q: How to know “smaller” and “larger” ?

Complexity of MakeSet? Find? WtdUnion?

Lemma: The leader/root-pointer of any element changes at most log(n) times.

Lemma: t MakeSet & s WtdUnion takes O(t + s log s) time.