Path Compression

1정의#

경로 압축(Path Compression)은 find(x) 수행 중, x에서 루트까지의 경로에 있는 모든 노드의 부모를 루트로 직접 바꾸는 기법이다.

2구현#

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

parent[x] = find(parent[x])에서 재귀 호출이 반환한 루트를 parent[x]에 저장한다. 이후 x에서 다시 find를 호출하면 O(1)에 루트를 찾는다.

3시간 복잡도#

임의의 합치기 방식과 경로 압축을 함께 사용할 때, 연산당 분할 상환 시간 복잡도는 O(log n)이다.

4증명#

포텐셜 함수를 정의한다. s(x)를 x를 루트로 하는 서브트리의 원소 수라 할 때, Φ = ∑_{x is root} ⌊log₂ s(x)⌋

초기에는 모든 노드가 독립 트리이므로 Φ = 0이다. 임의 합치기로 b를 a 아래에 붙이면 Φ는 최대 ⌊log₂ n⌋ 증가하므로, unite의 분할 상환 비용은 ⌊log₂ n⌋이다.

find(x)가 경로 u₀ → u₁ → ⋯ → u_k (루트)를 따라가 길이 k인 경로를 압축했다고 하자. 압축 후 u_i (1 ≤ i ≤ k−1)에 대해 u_i−1의 서브트리가 u_i에서 분리되므로 s(u_i)가 s(u_i−1) 만큼 감소한다.

분할 상환 비용 â = 실제 비용 + ΔΦ을 계산한다.

• 감소 노드 (s(u_i-1) ≥ s(u_i)/2): s(u_i)가 절반 이하로 줄어 ΔΦ ≤ −1이므로 â₁ ≤ 1 − 1 = 0이다.
• 유지 노드 (s(u_i-1) < s(u_i)/2): 경로를 올라갈수록 크기가 2배 이상 증가하므로, 하나의 find에서 유지 노드의 수는 ⌊log₂ n⌋ 이하이고 â₂ = 1이다.

â = ∑ â₁ + ∑ â₂ ≤ 0 + ⌊log₂ n⌋ = ⌊log₂ n⌋.

unite에 의한 Φ 증가량은 최대 m · ⌊log₂ n⌋ = O(m log n)이다. 따라서 m번의 연산에 걸친 전체 시간 복잡도는 O(m log n) 이다. ■