# Disjoint-set data structure

• The disjoint-set data structure is also commonly known as union-find or a merge-find set
• “disjoint-set forest”:
• represented as a set of N elements where:
• each element stores an `id`, a `parent pointer`, and optional `size`/`rank` values
• the parent pointers of the elements are arranged to form one or more trees (each tree is a “set”)
• if an element’s parent pointer is `null` or self-referencing, that element is the root element of a tree/set and represents the entire set
• single, non-connected elements are considered sets
• union-find data structure:
• a multiway tree structure composed of elements partitioned into independent subsets, which can be thought of as connected components
• provides a “`MakeSet`” operation:
• initializes a new set by creating a new element with `id`, rank of `0`, and a self-referencing parent pointer (denotes a root element)
``````function MakeSet(x)
if x doesn't exist yet,
x.parent` := x
x.rank    := 0
x.size    := 1
``````
• provides a “`Find`” operation to determine which set an element belongs to:
• traverses upwards along the chain of parent pointers until it finds the root element for the set, which is the answer to `find`
• path compression:
• flattens the disjoint-set tree by changing every element’s `parent pointer` to point to the root element of its set when `Find` is invoked
``````function Find(x)
if x.parent != x
x.parent := Find(x.parent)
return x.parent
``````
• path halving:
• makes every other node on the path point to its grandparent
``````function Find(x)
while x.parent != x
x.parent := x.parent.parent
x := x.parent

return x
``````
• path splitting:
• makes every node on the path pooint to its grandparent
``````function Find(x)
while x.parent != x
next := x.parent
x.parent := next.parent
x := next

return x
``````
• provides a “`Union`” operation to connect internal elements into components:
• used `Find` to determine the roots of the input elements and check whether they have the same root
• if roots are not the same, the trees are merged at the root by attaching the root of one tree to the root of the other
• union by rank:
• attaches the shorter tree to the root of the taller tree
``````function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)

if xRoot == yRoot,
return

if xRoot.rank < yRoot.rank,
temp := xRoot
xRoot := yRoot
yRoot := temp

yRoot.parent := xRoot

if xRoot.rank == yRoot.rank,
xRoot.rank := xRoot.rank + 1
``````
• union by size:
• attaches the tree with fewer elements to the root of the tree with more elements
``````function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)

if xRoot == yRoot,
return

if xRoot.size < yRoot.size,
temp := xRoot
xRoot := yRoot
yRoot := temp

yRoot.parent := xRoot
xRoot.size := xRoot.size + yRoot.size
``````