08. 자료구조론 - Disjoint Set

Disjoint Set (서로소 집합)

Disjoint set은 서로 공통된 요소를 가지지 않고 분리된 집합들을 관리하기 위한 자료구조입니다. 

Disjoint set 내의 집합 $S_i$, $S_j$ 에 대해서 $i != j$ 라면 $S_i$와 $S_j$ 에 공통으로 존재하는 요소는 없습니다.

Disjoint set에서 수행할 수 있는 기본적인 연산에는 Union, Find가 있습니다.

Union은 두 서로소 집합을 합치는 연산이고, Find는 원하는 요소가 어떤 서로소 집합에 있는지 찾는 연산입니다.

 

Disjoint set은 거꾸로된 트리들을 통해 구성할 수 있습니다.

일반적인 트리는 부모가 자식을 가리키는 방향이라면, Disjoint set의 집합 하나를 이루는 트리는 자식이 부모를 가리키는 방향으로 만들어집니다.

그리고 같은 트리 내에 있는 요소들은 모두 같은 서로소 집합에 속하게 됩니다.

 

예를 들어, 위의 서로소집합을 다음과 같은 트리로 만들 수 있습니다. 여기서 어떤 노드가 상위에 있는지는 중요하지 않습니다. 같은 트리에 있기만 한다면 모두 같은 서로소집합의 요소가 됩니다. 

그림1

Find

Disjoint set에서는 특정 서로소집합을 트리의 루트노드로 구별합니다.

따라서 Disjoint set에서 원하는 요소가 어떤 서로소 집합에 있는지 찾으려면, 찾고자하는 요소부터 시작해서 루트노드에 도달할때까지 parent를 따라 계속 올라가면 됩니다. 그리고 최종적으로 해당 요소가 속한 트리의 루트노드에 도달하면 해당 노드를 리턴합니다. 

따라서 어떤 두 노드가 같은 서로소집합인지를 확인하려면 Find를 통해 각각이 속한 트리의 루트노드를 찾고, 두 루트노드가 같은 노드인지 확인하면 됩니다.

위 그림을 예시로 보면, Find(9) = 3, Find(3) = 3, Find(6) = 5, Find(7) = 5, Find(8) = 8 이 됩니다.

Union

만약 위의 두번째와 세번째 집합(트리)을 Union 한다면 아래와 같은 새로운 트리가 생성됩니다. 

이렇게 두 집합을 Union하려면 한 트리의 루트를 다른 트리의 루트에 연결해주면 됩니다.

배열을 이용한 Disjoint set 구현

배열을 이용해 Disjoint set을 구현할 수 있습니다.

이때 주의할 점은 배열의 index가 노드의 값이 되고, 배열에는 parent노드의 인덱스 값이 저장된다는 것입니다. 

그리고 인덱스 0번은 parent가 없다는 뜻의 NULL을 의미하기 위해 사용됩니다.

 

위와 같은 Disjoint set 이 있을 때, 이를 배열로 나타내면 아래와 같습니다.

여기서 {2}와 {9, 10} 집합을 Union 한다고 생각해보겠습니다.

만약 {9, 10}을 {2} 에 가져다 붙이면 합쳐진 트리의 height는 2가 됩니다.

하지만 만약 {2}트리를 {9, 10}에 가져다 붙이면 합쳐진 트리의 height는 1이 됩니다. 

그렇다면 후자의 방식으로 Union을 하는 것이 더 나은 선택입니다. 

 

이렇게 더 효율적인 Union을 구현하기 위해서 각 트리에 rank(트리의 height과 동일한 의미)라는 값을 추가적으로 저장해줍니다.

그리고 두 트리를 Union할 때, 이제는 rank가 작은 트리의 루트노드를 rank가 큰 트리의 루트노드에 연결합니다.

그러면 Union시에 합쳐진 트리의 height를 최소화할 수 있습니다. 

 

그러면 rank를 어디에 저장해두어야 할까요?

rank는 트리 당 하나씩만 저장해두면 되고, 위에서 볼 수 있듯이 각 루트노드에는 배열 값이 모두 0으로 저장되어 있습니다. 이 루트노드에 0대신 rank를 저장해두면 됩니다. 그런데 만약 rank를 그대로 저장해두면 이게 rank값인지, 아니면 parent노드의 인덱스인지 구별할 수 없습니다.

따라서 다음과 같이 rank의 부호를 바꾸어 음수값으로 저장해두는 방법을 취할 수 있습니다. 

따라서 s를 Disjoint set을 저장해둔 배열이라고 할 때,

1. s[i]가 양수이면, s[i]는 i 노드의 parent 노드의 index를 의미합니다. 

2. s[i]가 음수(또는 0)이면, i 노드는 루트노드이고, -s[i]는 해당 트리의 rank를 의미합니다.

구현

typedef int* DisjointSets;

DisjointSets Init(int max_size) {
    DisjointSets s = (DisjointSets)malloc(sizeof(int)*(max_size+1));
    for (int i = 0; i <= max_size; i++) s[i] = 0;

    return s;
}

int Find(DisjointSets s, int x) {
    while (s[x] > 0) x = s[x];
    return x;
}

void Union(DisjointSets s, int elem1, int elem2) {
    int root1 = Find(s, elem1);
    int root2 = Find(s, elem2);

    if (s[root2] < s[root1]) {
        // s[root2], s[root1] 모두 음수이므로 s[root2]가 더 큰 height를 갖는 것임
        // 따라서 root1을 root2에 연결함
        s[root1] = root2;
    } else {
        // 만약 두 트리의 height가 같다면, 
        // 두 트리가 연결되면 합쳐진 트리의 height는 기존 트리보다 1 증가함
        // s[root1]은 음수이므로 height를 증가시키려면 값을 감소시켜야함
        if (s[root1] == s[root2]) s[root1]--;
        s[root2] = root1;
    }
}

Analysis of Disjoint set

Init : $O(n)$ (처음에 한번만 실행됨)

Union : $O(1)$ (Find를 통해 루트 찾는 과정을 제외)

Find : 트리의 height에 비례

 

그리고 아래에서 할 증명에 따라 다음과 같은 lemma가 성립합니다.

위의 Union()과 Find()를 통해 생성된 height h를 갖는 트리는 적어도 $2^h$ 개의 노드를 갖는다.

그리고 이 lemma에 따라 다음과 같은 theorem이 성립합니다.

위의 Union()과 Find()를 통해 생성된 m개의 노드를 갖는 트리의 height는 $log m$을 넘지 않는다.

그리고 이에 따라 다음과 같은 theorem을 도출할 수 있습니다.

Disjoint set을 초기화한 후, 어떤 순서로든 n번의 Union과 n번의 Find를 수행하는 작업을 $O(n log n)$ 시간 안에 수행할 수 있다. 

처음의 lemma를 증명하는 과정은 다음과 같습니다.

1. 1개의 노드를 갖는 트리의 height는 0 입니다.
2. 위의 가설이 k미만의 노드를 갖는 모든 트리에 대해 성립한다고 가정하겠습니다. 
그리고 위의 가설이 정확히 k개의 노드를 갖는 트리에 대해 성립함을 증명하면 증명이 완료됩니다.
k개의 노드를 갖는 트리는 각각 height가 $h_1, h_2$이고, 노드의 개수가 $n_1, n_2$인 트리 $T_1, T_2$를 Union하여 만들 수 있습니다. 
그리고 $T_1, T_2$ 트리는 당연히 k보다 적은 노드를 가질 것이므로 $n_1 \geq 2^{h_1}$, $n_2 \geq 2^{h_2}$ 가 성립합니다.

그리고 $h_2 \leq h_1$ 이어서 $T_2$가 $T_1$의 자식으로 들어간다고 하겠습니다.
만약 $h_2 \lt h_1$ 이면 합쳐진 트리의 높이 h는 $h_1$과 같게되고 
$n = n_1 + n_2 \geq 2^{h_1} + 2^{h_2} \geq 2^{h_1} = 2^h$ 가 됩니다.
만약 $h_2 = h_1$ 이라면 $h = h_2 + 1 = h_1 + 1$ 이 되고
$n = n_1 + n_2 \geq 2^{h_1} + 2^{h_2} \geq 2^{h-1} + 2^{h-1} = 2^h$ 가 됩니다.
따라서 어떤 경우에도 $n \geq 2^h$가 성립합니다.

Path compression

Path compression은 Disjoint set에서 Find 연산을 더 빠르게 수행할 수 있도록 하는 간단한 휴리스틱입니다.

Find 연산을 수행할 때, 루트노드를 찾아가는 경로에 있는 모든 노드들을 찾은 루트노드에 직접적으로 붙여버리는 방식입니다. 그러면 find의 경로에 있던 모든 노드들은 이후 find부터 루트노드까지 한번에 도달할 수 있게 됩니다. 

이렇게하면 당장의 Find 연산에서는 할 일이 조금 늘어나지만, 이후의 find 연산들이 훨씬 빨라지는 효과가 있습니다. 

이렇게 Find(4)를 하면 parent를 따라 3, 2 노드를 거쳐 루트노드인 1에 도달하는데, 루트노드 1을 찾으면 경로에 있던 2와 3노드의 parent를 1로 바꿔주는 것입니다.

 

다음과 같이 그냥 재귀적으로 함수를 호출하는 것이 아니라 호출하고 리턴된 값을 s[x]에 넣어주는 방식으로 구현할 수 있습니다. 

int FindWithPathCompression(DisjointSets s, int x) {
    if (s[x] > 0) return s[x] = FindWithPathCompression(s, s[x]));
    return x;
}