Disjoint-set data structure
Keywords: | union-find, union find, graphs, undirected graph, data structures |
Date: |
- 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
, aparent pointer
, and optionalsize
/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 of0
, 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 whenFind
is invokedfunction 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