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