유니온 파인드 크기 기반 병합 편집하기

유니온 파인드 크기 기반 병합(Union-Find with Union by Size)은 병합-찾기 자료구조에서 두 집합을 병합할 때 각 집합의 원소 수를 기준으로 병합 방향을 결정하여 트리의 깊이를 최소화하는 최적화 기법이다.
==개요==
크기 기반 병합은 유니온 파인드(상호 배타적 집합 자료구조)에서 병합 연산의 성능을 높이기 위한 전략으로, 각 집합의 트리 구조가 지나치게 비대해지는 것을 방지한다. 집합 병합 시 두 집합의 원소 수(크기)를 비교하여, 더 작은 집합을 더 큰 집합에 병합함으로써 트리의 균형을 유지하고 Find 연산의 효율성을 높인다.
==원리==
*유니온 파인드 자료구조는 각 원소가 트리의 노드로 표현되며, 루트 노드는 집합의 대표이다.
*각 집합은 크기 정보를 따로 저장하며, 일반적으로 루트 노드에만 해당 정보를 유지한다.
*Union(x, y) 연산 시 각 원소의 루트 노드를 찾고, 두 루트의 크기를 비교하여 작은 쪽을 큰 쪽에 병합한다.
*병합이 완료되면 새로운 루트의 크기를 업데이트한다.
이러한 방식은 트리의 깊이를 억제하여 전체 자료구조의 연산 성능을 향상시키는 효과가 있다.
==크기의 정의==
크기(size)는 해당 집합(트리)에 포함된 원소의 총 개수를 의미한다. 초기에는 각 원소가 자신만 포함하는 단일 집합이므로 크기는 1로 시작한다. 두 집합이 병합될 때, 새로운 루트 노드는 두 집합의 크기를 합산한 값을 자신의 크기로 저장한다.
==구현 예시==
다음은 크기 기반 병합을 포함한 유니온 파인드의 구현 예시이다:<syntaxhighlight lang="python">
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]
</syntaxhighlight>
==시간 복잡도==
크기 기반 병합과 경로 압축을 함께 사용할 경우, 전체 연산의 시간 복잡도는 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.
==각주==
[[분류:알고리즘]]
[[분류:트리 이론]]