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

유니온 파인드 랭크 기반 병합(Union-Find with Union by Rank)은 병합-찾기 자료구조에서 두 집합을 병합할 때 트리의 높이를 최소화하여 성능을 최적화하는 기법이다.
==개요==
랭크 기반 병합은 유니온 파인드(상호 배타적 집합 자료구조)의 핵심 최적화 기법 중 하나로, 집합 병합 시 트리 구조의 불균형을 방지하기 위해 사용된다. 각 집합은 트리 형태로 표현되며, 트리의 깊이를 추정하는 랭크(rank)를 기반으로 병합 순서를 결정한다. 

일반적으로 랭크는 트리의 실제 높이를 나타내기보다는 상대적인 깊이 수준을 나타내는 수치로 사용된다.
==랭크의 기준==
랭크는 각 트리의 루트 노드에 부여되는 정수 값으로, 해당 트리가 어느 정도 깊이를 갖고 있는지를 근사적으로 나타낸다. 초기에 모든 원소는 자신이 루트인 깊이 0의 트리이므로 랭크는 0으로 시작한다. 두 트리를 병합할 때, 랭크가 더 낮은 트리를 더 높은 트리에 붙이고, 두 트리의 랭크가 같다면 한쪽을 다른 쪽에 병합한 후 병합된 트리의 랭크를 1 증가시킨다. 이 방식은 트리의 깊이를 가능한 한 최소로 유지하며, Find 연산의 효율을 극대화한다. 실제로 랭크는 트리의 실질적 깊이를 정확히 반영하지 않지만, 병합 순서를 결정하기 위한 기준으로 충분히 유효하다.
==원리==
*각 원소는 자기 자신을 루트로 하는 독립적인 트리에서 시작하며, 모든 원소는 parent 배열로 부모 노드를 저장한다.
*각 집합의 루트 노드는 랭크 정보를 함께 가지고 있다. 이는 일반적으로 별도의 rank 배열에 저장된다.
*Union 연산 시 두 집합의 루트를 비교하고, 랭크가 더 작은 트리를 더 큰 트리에 병합한다.
*만약 두 루트의 랭크가 동일하다면, 둘 중 하나를 다른 쪽의 자식으로 만들고 병합된 트리의 랭크를 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 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
</syntaxhighlight>
==시간 복잡도==
랭크 기반 병합과 경로 압축을 함께 사용할 경우, 유니온 파인드 자료구조의 모든 연산의 평균 시간 복잡도는 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.
==각주==
[[분류:알고리즘]]
[[분류:트리 이론]]