Об’єднання-знаходження: Об’єднання множин майже за постійний час

Дві операції, одна лісова структура

Диз’єднана множина (union-find) – це структура даних, яка зберігає колекцію елементів, розділену на непересічні групи та відповідає двом запитанням швидко: find(x) - до якої групи належить x? - і union(x, y) - об’єднати групу x з групою y. Всередині кожної групи є дерево, і кожен елемент зберігає лише покажчик на свого батька. Корінь дерева – це представник групи-кантону: два елементи знаходяться в одній групі тоді й тільки коли їх корені збігаються.

Алгоритм Мінімального Спрощення Крил (Kruskal's) є класичним випадком використання: сортувати ребра за вагою, потім проходити по них у порядку зростання та додавати ребро до дерева, якщо його два кінці не з’єднані – питання, яке відповідає union-find за час ходу двох коротких ланцюгів до їхніх коренів. Та сама структура відстежує зв'язані компоненти при поступленні ребер один за одним, виявляє цикли в графі та об’єднує області в сегментації зображень.

The naive version, and why it degrades

A first attempt makes find walk parent pointers to the root, and union attach one root under the other arbitrarily. That works, but nothing stops a tree from becoming a long chain - union elements in increasing order, always attaching the new root under the previous one, and you get a straight line of n nodes. Find then costs O(n) instead of the O(log n) or better you actually want.

function find(x) {
  while (parent[x] !== x) x = parent[x];
  return x;
}
function union(x, y) {
  const rx = find(x), ry = find(y);
  if (rx !== ry) parent[rx] = ry;   // arbitrary attachment - can chain badly
}

Union by Rank

The fix is to always attach the shallower tree under the deeper one. Track either an exact size or an upper-bound rank (roughly, tree height) per root; when merging, the root with the smaller rank becomes a child of the root with the larger rank, and ties bump the winner's rank by one. This alone caps every tree's height at O(log n), because a tree of rank r can only be built by merging two trees of rank r minus 1, so it takes at least 2 to the power r elements to reach rank r.

Path compression: flattening as you go

Union by rank bounds the height, but you can do much better by rewriting history every time you walk to a root. Path compression makes every node visited during a find() point directly at the root once that root is known, so the next find from any of those nodes is O(1).

function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); // point straight at the root return parent[x]; } Tarjan and van Leeuwen proved that combining union by rank with path compression drives the amortized cost of any sequence of m operations on n elements down to O(m · alpha(n)), where alpha is the inverse of the fast-growing Ackermann function. For every practical n, alpha(n) is at most 4 or 5, so the structure behaves as if each operation were O(1) - a rare case where a genuinely non-constant bound is indistinguishable from constant time on real inputs.

function find(x) {
  if (parent[x] !== x) parent[x] = find(parent[x]);   // point straight at the root
  return parent[x];
}

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Union-Find і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.