Union-Find 연산

Region Merging을 구현할 때 필요한 "Disjoint Set"을 위한 자료구조이다.
본 내용은 "C로 쓴 자료구조론, Horowitz, Sahni, Anderson-Freed 저, 이석호 역" 에서 발췌하였다.
부족한 부분은 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Introduction To Algorithms", The MIT Press, 440-461, 1999.을 참조해야 한다.

트리를 사용하여 집합을 표현하는 방법에 대해 살펴보자.
여기서 집합의 모든 원소는 0, 1 , 2, ..., n-1 등의 수라고 가정하자.
이 수들은 실제 원소의 이름이 저장되어 있는 심볼 테이블의 인덱스를 의미할 수도 있다.
그리고 모든 집합들은 서로 분리(disjoint) 관계라 하자. 즉 임의의 두 집합 S_i 와 S_j ( i != j )는 어떤 원소도 공통으로 가지고 있지 않다.
가령, 0 부터 9 까지의 10 개의 원소들은 세 개의 분리집합, S1 = {0, 6, 7, 8}, S2 = {1, 4, 9}, S3 = {2, 3, 5} 로 나누어질 수 있다. 이러한 집합을 표현하는 예를 그림으로 그려보면 다음과 같다.

각 집합에서 노드들은 부모에서 자식으로 연결하는 일반적인 방법 대신, 자식에서 부모로 가는 링크로 연결되어 있음을 주목하자. 이러한 연결 방법을 사용하는 이유는 집합 연산의 구현을 논의할 때 분명해질 것이다. 이런 집합에 대하여 수행하고자 하는 연산은 다음과 같다.

(1) 분리 합집합(disjoint set union)
      S_i 와 S_j 가 분리집합일 때 이들의 합집합은
      S_i U S_j = { x | x 는 S_i 또는 S_j 에 있는 모든 원소 } 이므로
      S1 U S2 = { 0, 6, 7, 8, 1, 4, 9 }이다.
      우리는 모든 집합이 서로 분리되어 있다고 가정했기 때문에
      S_i 와 S_j 는 독립적으로 존재하지 않고, 대신 S_i U S_j 로 존재한다고 가정할 수 있다.

(2) Find(i)
     원소 i 를 포함하는 집합을 찾는다. 위의 예에서 보면 3은 S3 에 8 은 S1 에 있다.

먼저 합집합(union) 연산을 고려해보자. S1 과 S2 의 합집합을 만들기 위해서는 노드들이 자식에서 부모로 가는 링크로 연결되어 있으므로 간단히 두 트리 중의 하나를 다른 트리의 서브트리로 만들면 된다. 그러면 S1 U S2 는 아래 그림에 있는 표현 중의 하나가 될 것이다.

합집합 연산의 구현은 한 루트의 부모 필드가 다른 트리의 루트를 가리키도록 하면 된다. 이것은 각 집합을 가리키는 포인터를 사용하면 쉽다. 이 포인터들은 각 집합 이름에 대하여 그 집합의 루트를 가리킨다. 그리고 각 루트가 집합 이름을 가리키는 포인터를 가지고 있어서 한 원소가 어느 집합에 포함되어 있는지 결정하기 위해서는 그 트리의 루트로 연결된 부모 링크를 따라 올라가서 집합 이름을 가리키는 포인터를 찾으면 될 것이다. S1, S2, S3 에 대한 표현은 아래 그림과 같이 나타낼 수 있다.

union 과 find 알고리즘을 소개할 때는 실제 집합 이름은 무시하고 그 집합을 표현하는 트리의 루트로 식별할 것이다. 예컨대, 집합 이름 S1 대신 이 집합을 0 으로 참조할 것이다. 이것을 집합 이름으로 바꾸는 것은 간단하다. 집합 이름을 유지하는 테이블 name[] 이 있다고 하자. 한 원소 i 가 루트가 j 인 트리에 속하고 j 가 집합 이름 테이블의 k 번째 원소를 가리키는 포인터를 가진다면 그 집합의 이름은 name[k] 이다.
트리의 노드들에는 0 에서 n-1 까지 번호가 부여되어 있으므로 노드 번호를 바로 인덱스로 사용할 수 있다. 따라서 각 노드는 그의 부모를 연결하기 위해서 부모 인덱스를 포함할 하나의 필드만 있으면 되므로 필요한 자료구조는 배열 int parent[MAX_ELEMENTS] 이다. 여기서 MAX_ELEMENTS 는 최대 원소수이다. 아래 그림은 S1, S2, S3 를 이 방법으로 표현한 것으로서 각 루트 노드의 parent 필드값은 -1인 것에 주목하자.

find(i) 연산은 i 에서 시작하여 음수값의 부모 인덱스를 만날 때까지 인덱스들을 따라가면 된다. 예를 들어, find(5)는 5 부터 시작하여 5 의 부모인 2 로 이동하고 이 노드가 음수 인덱스를 가지므로 루트에 도달한 것이다. 마찬가지로 연산 union(i, j) 도 간단하다. 즉 루트가 i 와 j 인 두 트리를 합치면 된다. 만일 첫번째 트리를 두번째 트리의 서브트리로 만들기로 한다면, parent[i] = j 라는 문장 하나로 합집합 연산이 수행된다. 이러한 내용을 바탕으로 union-find 함수의 초기 구현은 아래와 같다.

int find1( int i )   // 부모찾는 연산
{
     for ( ; parent[i] >= 0 ; parent[i] )   // parent값이 음이면 부모다.
      :
      :
     return i ;
}
void union1( int i, int j )   // 하나를 다른 하나의 서브트리로 만든다.
{
     parent[i] = j ;   // 전체 root는 j 가 된다.
}

union1 과 find1 의 분석 : union1 과 find1은 기술하기가 쉬운 반면, 성능은 매우 좋지 않다. 예를 들어 p 개의 원소가 각각 p 개의 집합에 하나씩 포함되어 있다면, 즉 S_i = { i }, 0 <= i < p 라면 이 집합들을 나타내는 트리들의 초기 상태는 p 개의 노드들로 이루어진 포리스트이고 parent[i] = -1, 0 <= i < p 일 것이다. 이 집합들에 대해서 다음과 같이 union-find 연산을 연속적으로 수행해 보자.

union(0, 1), find(0)
union(1, 2), find(0)
:
:
union(n-2, n-1), find(0)

위의 연산 결과는 아래 그림과 같은 변질(degenerate) 트리가 만들어진다.

합집합 연산을 위해 소요되는 시간은 상수이므로 n-1 개의 합집합 연산을 수행하기 위한 시간은 O(n) 이 된다. 그렇지만 각 find 는 0 으로부터 루트까지의 부모 링크 체인을 따라가야 하므로 레벨 i 에 있는 원소에 대한 find 의 수행 시간은 O(i) 가 된다. 따라서 n-1 번의 find 를 수행하기 위해 필요한 총 시간은 다음과 같다.

변질 트리의 생성을 피하기 위해서는 union 과 find 연산을 좀 더 효율적으로 구현할 수 있는 방법을 고려해야 한다. 이는 union(i, j) 에 가중법칙(weighting rule)을 적용하면 해결할 수 있다.

[정의: union(i, j) 를 위한 가중법칙] 트리 i 의 노드수가 트리 j 의 노드수보다 적다면 j 를 i 의 부모로 만들고 그렇지 않으면 i 를 j 의 부모로 만든다.

이 규칙을 이용하여 앞에서 주어진 집합의 합집합 연산을 수행하면 아래의 트리가 얻어지게 된다.

이 법칙을 적용하기 위해서는 어떤 트리에 얼마나 많은 노드가 있는지를 알아야 하는데 이것은 모든 트리의 루트에 계수(count) 필드를 첨가하면 쉽게 해결할 수 있다. 가령 i 가 어떤 트리의 루트 노드라면 count[i] 는 그 트리의 노드수이다. 그러나 루트 이외의 모든 노드는 음이 아닌 수를 parent 필드에 가지고 있으므로 계수를 루트의 parent 필드에 음수로 저장하면 된다. 가중법칙을 적용한 합집합 연산이 union2 이다. union2 에 전달되는 인자는 트리의 루트이어야 함을 기억하자.

void union2(int i, int j)
{
     /* 가중법칙을 이용하여 루트와 i 와 j (i != j)인 집합을 합집합함. */
     /* parent[i] = -count[i] 이며 parent[j] = -count[j] 이다. */
     int temp = parent[i] + parent[j] ;
     if ( parent[i] > parent[j] ) {
          parent[i] = j ; // j 를 새 루트로 만듦
          parent[j] = temp ;
     }
     else {
          parent[j] = i ; // i 를 새 루트로 만듦
          parent[i] = temp ;
     }
}

[보조정리1] n 개의 노드를 가진 트리 T 가 union2 함수로 만들어진 트리라면, T에 있는 어떤 노드도 log_2 n + 1 보다 큰 레벨을 가질 수 없다.

[증명] n = 1 일 때 보조정리는 명백하다. 그리고 i <= n-1 개의 노드를 가진 모든 트리가 이 정리를 만족한다고 가정하자. 그러면 i = n 일 때도 역시 참이라는 것만 보여주면 된다. 트리 T 가 union2 함수에 의해 만들어졌다는 가정하에 마지막으로 수행된 합집합 연산 union(k, j) 를 고려해 보자. m 이 트리 j 의 노두수라면 k 에는 n - m 개의 노드가 있다. 여기서 모순됨이 없이 1 <= m <= n/2 을 가정할 수 있다. 그러면 T 에 있는 노드들의 최고 레벨은 k 의 최고 레벨과 같거나 j 의 그것보다 1 이 크다. 전자의 경우라면 T 의 최고 레벨 log_2 (n-m) + 1<= long_2 n +1 이 되며, 후자의 경우에는 T 의 최대 레벨 <= log_2 m + 2 <= log_2 n/2 + 2 <= log_2 n +1 이 되어 만족함을 알 수 있다.

[예제1] 초기 상태가 parent[i] = -count[i] = -1, 0 <= i < n=2^3 인 집합들에 대하여 다음과 같은 일련의 합집합 연산에서 union2 함수의 동작을 살펴보자.
union(0, 1) union(2, 3) union(4, 5) union(6, 7)
union(0, 2) union(4, 6) union(0, 4)
합집합이 열의 순서대로(즉, 1열이 처음에 2열이 그 다음 등등으로, 또 동일 열내에서는 위에서부터 아래의 순서로) 수행되면 아래와 같은 트리가 구성된다.

이 예에서도 명백한 것처럼 일반적인 경우에 있어서도 m 개의 노드를 가진 트리의 최대 레벨은 log_2 m + 1 이다.

보조정리1 에 따라 n 개의 원소를 가진 트리에서 find 연산을 한 번 수행하는 데 걸리는 최대 시간은 최대 O(log_2 n) 이다. 그리고 n-1 개의 union 과 m 개의 find 를 혼합하여 연속으로 실행하기 위한 시간은 최악의 경우 O(n+ m log_2 n)이 된다. 여기서 놀라운 것은 아직도 더 개선할 여지가 있다는 사실이다. 이것은 붕괴법칙(collapsing rule)을 사용하여 find 알고리즘을 수정하는 것을 의미한다.

[정의: 붕괴법칙] 만일 j 가 i 에서 루트로 가는 경로 위에 있다면 j 를 루트의 자식으로 만든다.

아래 프로그램은 find 연산에 붕괴법칙을 적용한 것이다. 이 새로운 함수는 각각 개별적으로 find 를 수행할 때에는 앞서 작성한 함수보다 약 2배 가량의 시간이 필요하지만 연속적인 find 수행시에는 최악의 경우를 피할 수 있다.

int find2(int i)
{
     /* 원소 i 를 포함하는 루트를 찾음. */
     /* 붕괴법칙을 사용하여 i 로부터 루트로 가는 모든 노드를 붕괴시킴 */
     int root, trail, lead ;
     for (root = i ; parent[root] >= 0 ; root = parent[root])
      :
     for (trail = i ; trail != root ; trail = lead) {
          lead = parent[trail] ;
          parent[trail] = root ;
     }
     return root ;
}

[예제2] union2 를 사용하여 예제1 의 연속된 합집합 연산 결과로 얻은 트리를 고려해 보자. 여기서는 다음 8 개의 find 연산을 수행하고자 한다.

find(7), find(7), .... , find(7)

find 의 옛날 함수를 이용하면 각 find(7) 이 세 개의 parent 링크 필드를 거쳐야 하므로 여덟개의 find 를 수행하려면 총 24회의 이동이 필요하다. 하지만 새로운 find 함수에서는 처음 find(7) 은 세 개의 링크를 거치고 두 개의 링크를 변경하지만, 나머지 일곱 개의 find 에서는 단지 하나의 링크만 거치면 된다. 따라서 총 이동수는 13 이 된다(이 문제에서는 두 개의 링크만 변경하면 되지만 함수 find2 는 노드 4 로부터의 링크를 포함한 세 개를 변경하는 것에 주목하자).

일련의 union 과 find 수행에 있어서 union-find 알고리즘의 최악의 경우의 특성이 보조정리2 에 잘 나타나 있다. 이 보조정리를 기술하기에 전에 액커만 함수(Ackermann's function) A(p, q) 와 역함수 관계에 있는 완속 증가 함수 a(m, n) 을 소개한다. 이 a(m, n) 의 정의는 다음과 같다.

여기서 사용된 액커만 함수의 정의는 다음과 같다.

함수 A(p, q) 는 급속 증가 함수이다. 윗식을 이용하여 다음 세 가지 사실을 증명할 수 있을 것이다.

여기서 m != 0 이라고 가정한다면 (2)와 (3) 그리고 a(m, n) 의 정의로부터 log_2 n < A(3, 4) 일 때 a(m, n) <= 3 임을 알 수 있다. 그런데 (1)을 보면 A(3, 4) 는 정말 매우 큰 수임을 알 수 있다. 보조정리2 에서 n 은 수행될 합집합의 수이다. 실제의 모든 경우에 있어서 우리는 log_2 n 이 A(3, 4) 보다 작다고 가정할 수 있으므로 실제의 경우에서 a(m, n) <= 3 이다.

[보조정리2] m>=n 개의 find 와 n-1 개의 union 들이 혼합된 일련의 수행을 위해 필요한 최대 시간을 T(m, n) 이라 하자. 그러면 어떤 양의 상수 k_1 과 k_2 에 대해 다음의 식이 만족된다.

a(m, n) 이 완속 증가 함수일지라도 union-find 의 복잡도는 find 의 수 m 에 대하여 비선형적이다. 요구되는 공간을 보면 각 원소마다 하나의 노드가 필요하게 된다.