21. Data Structures for Disjoint Sets

n개의 원소를 서로소인 집합들로 분할해야 할 때가 있다. 이 때의 주요 동작 두 가지는 원소가 속한 집합을 찾는 것이고 두 집합을 병합하는 것이다.

21.1. Disjoint-set operations

서로소-집합 자료 구조는 서로소인 동적 집합들의 모임이다. 각 집합에 대해 대표 원소를 지정해서 각 집합을 특정한다. 이는 다음의 동작을 지원해야 한다.

  • MAKE-SET(x) : 원소가 x뿐인 집합을 생성.
  • UNION(x, y) : 원소 x가 속한 집합과 y가 속한 집합을 병합.
  • FIND-SET(x) : 원소 x가 속한 집합을 반환.

MAKE-SET이 n번, 모든 동작이 일어나는 횟수를 m번이라 하면 m \geq n이며 UNION의 횟수는 최대 n – 1이다.

An application of disjoint-set data structures

비방향 그래프에서의 연결 요소를 찾는 데 쓰일 수 있다.

CONNECTED-COMPONENTS(G)
for each vertex v ∈ G.V
    MAKE-SET(v)
for each edge (u, v) ∈ G.E
    if FIND-SET(u) ≠ FIND-SET(v)
        UNION(u, v)
SAME-COMPONENT(u, v)
if FIND-SET(u) == FIND-SET(v)
    return TRUE
else
    return FALSE

21.2. Linked-list representation of disjoint sets

연결 리스트로 서로소 집합을 구현할 수 있다.

A simple implementation of union

UNION(x, y)의 구현은 간단하지만 분할 상환 \Theta(n)이다.

A weighted-union heuristic

리스트의 길이를 저장하고 항상 짧은 리스트를 긴 리스트에 붙이는 가중-병합 휴리스틱을 쓰면 UNION은 여전히 \Omega(n)이지만 m개의 MAKE-SET, UNION, FIND-SET 동작은 O(m + n \lg n)이 된다.

Theorem. 서로소 집합의 연결 리스트 구현에서 m개의 MAKE-SET, UNION, FIND-SET 동작은 MAKE-SET이 n번일 때 O(m + n \lg n)이 된다.

21.3. Disjoint-set forests

서로소 집합 포레스트 구현은 각각의 집합을 트리로 나타내며 각 원소는 그 부모에 대한 링크만을 가진다.

Heuristics to improve the running time

서로소 집합 포레스트 구현은 그 자체만으로는 연결 리스트보다 빠르지 않다. 다만 휴리스틱을 써서 수행 시간을 극적으로 개선시킬 수 있다. 첫째는 랭크에 의한 병합으로 더 작은 트리를 더 큰 트리에 병합시키는 것이다. 둘째는 경로 압축이다.

Pseudocode for disjoint-set forests

유사코드로 알아보자.

MAKE-SET(x)
x.p = x
x.rank = 0
UNION(x, y)
LINK(FIND-SET(x), FIND-SET(y))
LINK(x, y)
if x.rank > y.rank
    y.p = x
else
    x.p = y
    if x.rank == y.rank
        y.rank++
FIND-SET(x)
if x ≠ x.p
    x.p = FIND-SET(x.p)
return x.p

FIND-SET은 투 패스 방식이다. 첫 번째 패스는 루트를 찾고 두 번째 패스는 부모를 루트로 업데이트한다.

Effects of the heuristics on the running time

랭크에 의한 병합만 쓰면 수행 시간은 O(m \lg n)이며, 경로 압축만 쓰면 n개의 MAKE-SET, f개의 FIND-SET 의 수행 시간은 \Theta(n + f(1 + \log_{2 + \frac{f}{n}} n))이다. 둘을 같이 쓰면 O(m \alpha(n))이다. 거의 대부분의 경우 \alpha(n) \leq 4이다.

21.4. Analysis of union by rank with path compression

앞 절에서 알아본 O(m \alpha(n))을 증명해 보자.

A very quickly growing function and its very slowly growing inverse

k = 0일 때 A_{k}(j) = j + 1, 이외에는 A_{k}(j) = A_{k-1}^(j + 1)(j)로 정의하자.

Lemma. j \geq 1일 때 A_{1}(j) = 2j + 1이다.

Lemma. j \geq 1일 때 A_{2}(j) = 2^{j+1}(j + 1) - 1이다.

이제 \alpha(n) = \min\{k : A_{k}(1) \geq n\}로 정의하자. 이는 A_{4}(1) 이하의 n에 대해 항상 4 이하이다. 그러므로 사실상 4 이하라고 봐도 된다.

Properties of ranks

Lemma. x.rank \leq x.p.rank이며 x \neq x.p이면 등호가 성립하지 않는다. x.rank는 최초에 0이며 x \neq x.p인 한 계속 증가하며 이후부터는 변하지 않는다. x.p.rank는 단조증가한다.

Corollary. 노드에서 루트로 가는 단순 경로에서 랭크는 단조증가한다.

Lemma. 모든 노드의 랭크는 최대 n – 1이다.

Proving the time bound

이제 시간 상한을 분석해 보자.

Lemma. m^{\prime}개의 MAKE-SET, UNION, FIND-SET 연산들을 m개의 MAKE-SET, LINK, FIND-SET 개로 바꾼다고 하자. 이 때 UNION을 2개의 FIND-SET과 LINK로 바꾼다. 이 경우 바꾼 뒤의 연산들이 O(m \alpha(n))에 동작한다면, 바꾸기 전의 연산들은 O(m^{\prime} \alpha(n))에 동작한다.

Potential function

잠재 함수는 모든 트리의 잠재 함수의 합으로 정의한다. 이 때 level(x)를 \max \{ k : x.p.rank \geq A_{k}(x.rank)\}로 정의하면 0 \leq level(x) < \alpha(n)이 된다. iter(x)는 \max \{ i : x.p.rank \geq A_{level(x)}^{(i)}(x.rank) \}로 정의한다. 트리의 잠재 함수는 x가 루트거나 rank가 0이면 \phi_{q}(x) = \alpha(n) x.rank로 정의한다. 이외에는 \phi_{q}(x) = (\alpha(n) - level(x)) \cdot x.rank - iter(x)로 정의한다.

Lemma. 모든 노드에 대해 0 \leq \phi_{q}(x) \leq \alpha(n) \cdot x.rank이다.

Corollary. x가 루트가 아니고 x.rank > 0이면 \phi_{q}(x) < \alpha(n) \cdot x.rank이다.

Potential changes and amortized costs of operations

이제 각 연산이 잠재 함수에 주는 영향을 알아보자.

Lemma. 루트가 아닌 노드 x에 대해 q번째 연산이 LINK나 FIND-SET이라 하자. 그러면 \phi_{q}(x) \leq \phi_{q-1}(x)이다. x.rank ≥ 1이고 level(x)나 iter(x)가 q번째 연산에서 변화한다면 \phi_{q}(x) \leq \phi_{q-1}(x) - 1이다.

Lemma. MAKE-SET은 분할 상환 O(1)이다.

Lemma. LINK는 분할 상환 O(\alpha(n))이다.

Lemma. FIND-SET은 분할 상환 O(\alpha(n))이다.

Theorem. MAKE-SET n번, UNION, FIND-SET까지 합쳐서 m번 할 경우 서로소 집합 포레스트 구현과 랭크에 의한 병합, 경로 압축을 쓰면 최악 수행 시간은 O(m \alpha(n))이 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중