Union by Rank

1정의#

랭크 기반 합치기(Union by Rank)는 두 집합을 합칠 때 항상 랭크가 낮은 트리를 높은 트리 아래에 붙이는 기법이다.

랭크(rank)는 트리 높이다.

2구현#

int parent[N], rnk[N];

void init(int n) {
    for (int i = 0; i < n; i++) parent[i] = i, rnk[i] = 0;
}

int find(int x) {
    if (parent[x] == x) return x;
    return find(parent[x]);
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    parent[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
}

• 랭크가 다르면 낮은 쪽 루트를 높은 쪽 루트의 자식으로 붙인다. 이때 높은 쪽 루트의 랭크는 변하지 않는다.
• 랭크가 같으면 한쪽을 다른 쪽 아래에 붙이고, 새 루트의 랭크를 1 올린다.

3시간 복잡도#

find의 최악 시간 복잡도는 O(log n)이다.

4증명#

4.1보조 정리#

랭크가 k인 노드를 루트로 하는 서브트리의 크기는 2^k 이상이다.

k에 대한 귀납법을 사용한다.

기저 (k = 0): 초기 상태에서 모든 노드의 랭크는 0이고 자기 자신만을 포함하므로 크기 = 1 = 2⁰이다.

귀납 (k → k+1): 랭크 k+1이 되는 경우는 랭크가 같은 두 트리가 합쳐질 때뿐이다. 귀납 가설에 의해 각 트리의 크기는 2^k 이상이므로, 합친 트리의 크기는 2^k + 2^k = 2^k+1 이상이다. ■

---

결론: n개의 원소가 있으므로 어떤 서브트리의 크기도 n을 넘지 않는다. 2^k ≤ n이므로 k ≤ ⌊log₂ n⌋이고, 모든 노드의 랭크는 ⌊log₂ n⌋ 이하다.

랭크 = 트리 높이이므로, 트리 높이 ≤ ⌊log₂ n⌋이다. find는 루트까지 올라가므로 O(log n)이다.