지나온 경로를 바꾼다
A의 부모가 B, B의 부모가 C, C가 루트라고 하자. A에서 루트를 찾은 뒤 A와 B의 부모를 C로 바꾸면 다음 탐색은 더 적은 부모 연결을 거친다. 새로운 집합을 만드는 것이 아니다.
합치기와의 차이
Union은 서로 다른 두 집합을 하나로 합친다. 경로 압축은 한 집합 안에서 대표를 찾는 과정을 개선한다. 경로가 짧아져도 어느 두 원소가 같은 집합인지에 대한 답은 바뀌지 않는다.
랭크와 함께 사용한다
랭크나 크기를 기준으로 작은 트리를 큰 트리에 붙이는 합치기 전략과 함께 쓸 수 있다. 경로 압축 뒤 실제 높이가 줄어도 랭크를 매번 정확한 높이로 다시 계산하는 것은 일반적인 구현의 필수 조건이 아니다.
한 번과 전체의 성능
경로 압축과 적절한 합치기 전략을 결합한 효율은 여러 연산을 묶어 분석한다. 거의 상수에 가까운 실용적 속도라는 설명을 모든 개별 Find가 항상 한 단계라는 뜻으로 받아들여서는 안 된다.
관련 문서
서로소 집합 자료 구조 / 트리 (그래프 이론) / 크루스칼 알고리즘 / 연결 성분 / 시간 복잡도 / 분할 상환 분석