Home

Awesome

Learning union-find data structure (for sets)

Just one of the things I'm learning. https://github.com/hchiam/learning

AKA disjoint-set data structure or merge–find set

Why

Implement sets with fast set membership checks (O(log n) or near O(1)) and fast set unions/intersections (near O(1)).

How

Children point to parents. Root parent represents the set. When combining sets, always merge into the taller tree (to guarantee logarithmic height). Use path compression to flatten the tree on each find (along the search path), to speed up traversal from O(log n) to O(1).

Example

node example.js

Option comparison summary

This is my attempt to better summarize my earlier notes:

Set implementationGet all in setIntersection / unionFind which set x is inIn 1 set, find xMove x to another set
{:}O(n)O(n)O(kn) or O(k log n) *O(n) or O(log n) *O(1)
bits [,,]O(n)O(n)O(k)O(1)O(1)
binary tree root as setO(n)O(n) ?O(k log n)O(log n)O(log n) ?
root as set, but children point to parents?O(~1)O(~k) **O(~1) **?

My earlier notes

Using the union-find data structure is motivated by the disadvantages with other ways to implement sets:

Meanwhile for the union-find data structure:

Reference

Read the section on union-find data structure in "The Algorithm Design Manual" by Steven Skiena.

Further reading

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

https://en.wikipedia.org/wiki/Disjoint-set_data_structure