# 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

- each element stores an

- represented as a set of N elements where:
**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, add x to the disjoint-set x.parent` := x x.rank := 0 x.size := 1`

- initializes a new set by creating a new element with
- 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`

- flattens the disjoint-set tree by changing every element’s
**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`

- makes every other node on the path point to its grandparent
**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`

- makes every node on the path pooint to its grandparent

- traverses upwards along the chain of parent pointers until it finds the root element for the set, which is the answer to
- 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`

- attaches the shorter tree to the root of the taller tree
**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`

- attaches the tree with fewer elements to the root of the tree with more elements

- used