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

유니온 파인드 랭크 기반 병합(Union-Find with Union by Rank)은 병합-찾기 자료구조에서 두 집합을 병합할 때 트리의 높이를 최소화하여 성능을 최적화하는 기법이다.

개요

랭크 기반 병합은 유니온 파인드(상호 배타적 집합 자료구조)의 핵심 최적화 기법 중 하나로, 집합 병합 시 트리 구조의 불균형을 방지하기 위해 사용된다. 각 집합은 트리 형태로 표현되며, 트리의 깊이를 추정하는 랭크(rank)를 기반으로 병합 순서를 결정한다.

일반적으로 랭크는 트리의 실제 높이를 나타내기보다는 상대적인 깊이 수준을 나타내는 수치로 사용된다.

랭크의 기준

랭크는 각 트리의 루트 노드에 부여되는 정수 값으로, 해당 트리가 어느 정도 깊이를 갖고 있는지를 근사적으로 나타낸다. 초기에 모든 원소는 자신이 루트인 깊이 0의 트리이므로 랭크는 0으로 시작한다. 두 트리를 병합할 때, 랭크가 더 낮은 트리를 더 높은 트리에 붙이고, 두 트리의 랭크가 같다면 한쪽을 다른 쪽에 병합한 후 병합된 트리의 랭크를 1 증가시킨다. 이 방식은 트리의 깊이를 가능한 한 최소로 유지하며, Find 연산의 효율을 극대화한다. 실제로 랭크는 트리의 실질적 깊이를 정확히 반영하지 않지만, 병합 순서를 결정하기 위한 기준으로 충분히 유효하다.

원리

• 각 원소는 자기 자신을 루트로 하는 독립적인 트리에서 시작하며, 모든 원소는 parent 배열로 부모 노드를 저장한다.
• 각 집합의 루트 노드는 랭크 정보를 함께 가지고 있다. 이는 일반적으로 별도의 rank 배열에 저장된다.
• Union 연산 시 두 집합의 루트를 비교하고, 랭크가 더 작은 트리를 더 큰 트리에 병합한다.
• 만약 두 루트의 랭크가 동일하다면, 둘 중 하나를 다른 쪽의 자식으로 만들고 병합된 트리의 랭크를 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 rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x
        rank[root_x] += 1

시간 복잡도

랭크 기반 병합과 경로 압축을 함께 사용할 경우, 유니온 파인드 자료구조의 모든 연산의 평균 시간 복잡도는 O(α(n))이 된다. 여기서 α(n)은 아커만 함수의 역함수로, 실용적인 모든 입력 크기에 대해 상수에 가까운 값을 갖는다.

장점

• 트리의 높이를 제한하여 Find 연산의 시간 복잡도를 낮춘다.
• 구조적 균형을 유지하므로 대량의 Union 및 Find 연산이 반복되는 알고리즘에서 매우 효과적이다.
• Kruskal 알고리즘 등 그래프 기반 알고리즘에서 성능 향상에 결정적이다.

같이 보기

• 유니온 파인드
• 경로 압축
• 최소 신장 트리
• Kruskal 알고리즘
• 자료구조

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM, 22(2), 215-225.