Disjoint-set data structure: Difference between revisions

Revision as of 08:36, 20 June 2025

Latest revision as of 12:42, 28 July 2025

(One intermediate revision by one other user not shown)

Line 120:

=== Merging two sets ===

{{multiple image

| direction = vertical

[[File:Dsu disjoint sets init.svg|thumb|360px|<code>MakeSet</code> creates 8 singletons.]]

| width =360

[[File:Dsu disjoint sets final.svg|thumb|360px|After some operations of <code>Union</code>, some sets are grouped together.]]

[[File: | image1=Dsu disjoint sets init.svg|thumb|360px|caption1=<code>MakeSet</code> creates 8 singletons.]]

[[File: | image2=Dsu disjoint sets final.svg|thumb|360px|caption2=After some operations of <code>Union</code>, some sets are grouped together.]]

}}

The operation <code>Union(''x'', ''y'')</code> replaces the set containing {{mvar|x}} and the set containing {{mvar|y}} with their union. <code>Union</code> first uses <code>Find</code> to determine the roots of the trees containing {{mvar|x}} and {{mvar|y}}. If the roots are the same, there is nothing more to do. Otherwise, the two trees must be merged. This is done by either setting the parent pointer of {{mvar|x}}'s root to {{mvar|y}}'s, or setting the parent pointer of {{mvar|y}}'s root to {{mvar|x}}'s.

The choice of which node becomes the parent has consequences for the complexity of future operations on the tree. If it is done carelessly, trees can become excessively tall. For example, suppose that <code>Union</code> always made the tree containing {{mvar|x}} a subtree of the tree containing {{mvar|y}}. Begin with a forest that has just been initialized with elements <math>1, 2, 3, \ldots, n,</math> and execute <code>{{math|Union(1, 2)}}</code>, <code>{{math|Union(2, 3)}}</code>, ..., <code>{{math|Union(''n'' - 1, ''n'')}}</code>. The resulting forest contains a single tree whose root is {{mvar|n}}, and the path from 1 to {{mvar|n}} passes through every node in the tree. For this forest, the time to run <code>Find(1)</code> is {{math|''O''(''n'')}}.

In an efficient implementation, tree height is controlled using '''union by size''' or '''union by rank'''. Both of these require a node to store information besides just its parent pointer. This information is used to decide which root becomes the new parent. Both strategies ensure that trees do not become too deep.

Line 187 ⟶ 190:

It is clear from the above implementations that the size and rank of a node do not matter unless a node is the root of a tree. Once a node becomes a child, its size and rank are never accessed again.

There is a variant of the <code>Union</code> operation in which the user determines the representative of the formed set. It is not hard to add this functionality to the above algorithms without losing efficiency.

== Time complexity ==