유니온 파인드 경로 분할 편집하기

유니온 파인드 경로 분할(Union-Find with Path Splitting)은 병합-찾기 자료구조에서 Find 연산의 효율을 높이기 위한 경로 압축 기법 중 하나로, 루트 노드를 찾는 동안 경로 상의 각 노드를 그 부모의 부모로 연결하는 방식이다.
==개요==
경로 분할(path splitting)은 유니온 파인드에서 트리의 깊이를 줄이고 Find 연산을 빠르게 만들기 위한 최적화 기법이다. 경로 압축(path compression), 경로 반결합(path halving)과 함께 대표적인 세 가지 경로 평탄화 전략 중 하나로, 각 노드를 루트와 더 가까운 위치로 옮김으로써 다음 연산에서의 접근 시간을 줄인다. 이 방법은 특히 반복적인 Find 연산이 많은 경우에 전체 자료구조의 효율성을 향상시킨다.
==원리==
*Find 연산 도중, 루트 노드를 찾기 위해 탐색하는 각 노드에 대해, 해당 노드의 부모를 그 부모의 부모로 설정한다.
*이 작업은 탐색 경로의 노드를 한 단계 위로 끌어올리는 효과를 가지며, 전체 트리의 평균 높이를 낮춘다.
*경로 분할은 재귀나 반복적인 방식으로 구현될 수 있으며, 경로 압축과 달리 모든 중간 노드가 업데이트된다.
==구현 예시==
다음은 경로 분할을 사용하는 Find 연산의 반복적 구현 예시이다:<syntaxhighlight lang="python">
def find(x):
    while parent[x] != x:
        parent[x], x = parent[parent[x]], parent[x]
    return x
</syntaxhighlight>위 코드는 x에서 루트까지 올라가는 과정에서 x의 부모를 x의 조부모로 갱신하는 방식이다. 이 과정은 트리의 깊이를 간접적으로 줄여주는 효과를 가진다.
==경로 분할 vs 경로 압축==
*경로 압축은 탐색 후 경로상의 모든 노드를 루트에 직접 연결하는 반면, 경로 분할은 경로상의 각 노드를 그 부모의 부모로 설정한다.
*경로 분할은 반복 구조에 적합하고 구현이 단순하며, 메모리 접근 패턴이 더 고르게 분산되는 장점이 있다.
*경로 압축은 더 강력한 평탄화를 제공할 수 있으나, 재귀적 구현에 의존하는 경우가 많다.
==시간 복잡도==
경로 분할은 경로 압축, 경로 반결합과 마찬가지로 유니온 파인드 자료구조의 시간 복잡도를 O(α(n))으로 줄인다. 이때 α(n)은 아커만 함수의 역함수이며, 대부분의 실용적인 입력에 대해 상수에 가까운 시간 성능을 제공한다.
==활용==
*Kruskal 알고리즘과 같은 그래프 기반 알고리즘에서의 Find 연산 최적화
*네트워크 연결성 확인
*사이클 검출 및 군집화 문제 등 반복적인 집합 조회가 필요한 경우
==같이 보기==
*[[유니온 파인드]]
*[[경로 압축]]
*[[경로 반결합]]
*[[랭크 기반 병합]]
*[[Kruskal 알고리즘]]
==참고 문헌==
*Tarjan, R. E., & van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM, 31(2), 245–281.
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
==각주==
[[분류:알고리즘]]
[[분류:트리 이론]]