유니온 파인드 크기 기반 병합

유니온 파인드 크기 기반 병합(Union-Find with Union by Size)은 병합-찾기 자료구조에서 두 집합을 병합할 때 각 집합의 원소 수를 기준으로 병합 방향을 결정하여 트리의 깊이를 최소화하는 최적화 기법이다.

개요

크기 기반 병합은 유니온 파인드(상호 배타적 집합 자료구조)에서 병합 연산의 성능을 높이기 위한 전략으로, 각 집합의 트리 구조가 지나치게 비대해지는 것을 방지한다. 집합 병합 시 두 집합의 원소 수(크기)를 비교하여, 더 작은 집합을 더 큰 집합에 병합함으로써 트리의 균형을 유지하고 Find 연산의 효율성을 높인다.

원리

• 유니온 파인드 자료구조는 각 원소가 트리의 노드로 표현되며, 루트 노드는 집합의 대표이다.
• 각 집합은 크기 정보를 따로 저장하며, 일반적으로 루트 노드에만 해당 정보를 유지한다.
• Union(x, y) 연산 시 각 원소의 루트 노드를 찾고, 두 루트의 크기를 비교하여 작은 쪽을 큰 쪽에 병합한다.
• 병합이 완료되면 새로운 루트의 크기를 업데이트한다.

이러한 방식은 트리의 깊이를 억제하여 전체 자료구조의 연산 성능을 향상시키는 효과가 있다.

크기의 정의

크기(size)는 해당 집합(트리)에 포함된 원소의 총 개수를 의미한다. 초기에는 각 원소가 자신만 포함하는 단일 집합이므로 크기는 1로 시작한다. 두 집합이 병합될 때, 새로운 루트 노드는 두 집합의 크기를 합산한 값을 자신의 크기로 저장한다.

구현 예시

다음은 크기 기반 병합을 포함한 유니온 파인드의 구현 예시이다:

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)

    if root_x == root_y:
        return

    if size[root_x] < size[root_y]:
        parent[root_x] = root_y
        size[root_y] += size[root_x]
    else:
        parent[root_y] = root_x
        size[root_x] += size[root_y]

시간 복잡도

크기 기반 병합과 경로 압축을 함께 사용할 경우, 전체 연산의 시간 복잡도는 O(m α(n))으로 수렴하며, α(n)은 아커만 함수의 역함수이다. 이는 모든 실용적인 입력에 대해 상수에 가까운 성능을 보장한다.

특성 및 차이점

• 랭크 기반 병합이 트리의 높이를 근사한 수치에 의존하는 반면, 크기 기반 병합은 정확한 원소 수를 기준으로 병합 순서를 결정한다.
• 크기 기반 병합은 트리의 구조를 더욱 직관적으로 유지하며, 랭크 정보를 계산하는 복잡성을 줄인다.
• 실험적으로도 랭크 기반 병합과 유사한 수준의 성능을 제공한다.

같이 보기

• 유니온 파인드
• 최소 신장 트리
• 크루스칼 알고리즘

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Galil, Z., & Italiano, G. F. (1991). Data Structures and Algorithms for Disjoint Set Union Problems. ACM Computing Surveys, 23(3), 319–344.