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 log₂ s(x)

s(x) ≥ 1이므로 항상 Φ ≥ 0이고, 초기에는 모든 노드가 독립 트리라 s(x) = 1이므로 Φ = 0이다. 임의 합치기로 루트 b를 루트 a 아래에 붙이면 a의 서브트리만 s(a)에서 s(a) + s(b)로 커지고 다른 노드의 서브트리 크기는 변하지 않으므로, ΔΦ = log₂(s(a) + s(b)) − log₂ s(a) ≤ log₂ n이다. 따라서 unite의 분할 상환 비용은 log₂ n + O(1) = O(log n)이다.

find(x)가 경로 u₀ → u₁ → ⋯ → u_k (루트)를 따라가 길이 k인 경로를 압축했다고 하자. 압축 후 u_i (1 ≤ i ≤ k−1)는 자식 u_i−1의 서브트리를 잃으므로 s(u_i)가 s(u_i−1) 만큼 감소하고, u₀과 루트 u_k의 서브트리 크기는 변하지 않는다. 모든 변화가 감소이므로 ΔΦ ≤ 0이다.

내부 노드 u_i (1 ≤ i ≤ k−1)의 분할 상환 비용 â = 실제 비용 + ΔΦ를 계산한다.

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

u₀과 루트 u_k의 실제 비용 O(1)을 더하면 한 번의 find의 분할 상환 비용은 â = ∑ â₁ + ∑ â₂ + O(1) ≤ log₂ n + O(1) = O(log n)이다.

unite와 find 모두 분할 상환 비용이 O(log n)이고 Φ ≥ 0 = Φ_초기이므로, m번의 연산에 걸친 전체 시간 복잡도는 O(m log n)이다. ■