서로소 집합 자료 구조

*메이크셋*은 8개의 개체를 생성한다. *유니온* 연산을 여러 번 수행하면 여러 집합들이 합쳐진다. 컴퓨터 과학 분야에서 **서로소 집합**(disjoint-set) 자료 구조, 또는 **합집합-찾기**(union–find) 자료 구조, **병합-찾기 집합**(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 서로소 집합 자료 구조는 두 개의 유용한 연산을 제공한다: * *파인드(Find)*: 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. *파인드*는 일반적으로 어떤 원소가 속한 집합을 "대표" 하는 원소를 반환하는데, 이를 위하여 어떤 원소와 각 대표 원소들 간의 *파인드* 결과를 비교하여 같은 집합임을 판단한다. * *유니온(Union)*: 두 개의 집합을 하나의 집합으로 합친다. 다른 중요한 연산으로 *메이크셋*(MakeSet)이 있으며 이는 특정 한 원소만을 가지는 집합을 만든다. 이 세 연산을 활용하여 많은 파티션(partitioning) 문제들을 해결할 수 있다. (*응용* 부분 참조) 위의 연산들을 정의하기 위하여 집합을 표현하는 방법이 필요하다. 일반적으로 각 집합 전체를 대표하는 하나의 고정된 *대표 원소*를 정하는 방법이 있다. 이 방법에서 *파인드*(x) 연산은 원소 *x*가 속한 집합의 대표 원소를 반환하고 *유니온* 연산은 두 대표 원소를 입력 인자로 사용한다.
# 서로소 집합 연결 리스트 (Disjoint-set linked lists)
서로소 집합 데이터 구조는 간단히 각 집합을 표현하기 위하여 연결 리스트(linked list)를 사용한다. 각 리스트의 헤드(head) 부분에는 해당 집합의 대표 원소를 저장한다. *MakeSet*은 한 원소만을 가지는 리스트를 생성한다. *유니온*은 두 리스트를 붙이는 연산을 수행하며, 이때 한 리스트의 헤드 부분이 다른 리스트의 꼬리를 가리켜 상수-시간(constant-time) 연산을 수행한다. *파인드* 연산시 특정 원소로부터 리스트의 헤드까지 반대 방향으로 탐사해야 하며, 그렇기 때문에 선형 시간(linear time) 또는 O(*n*) 시간을 요구한다는 단점을 가진다. 이 단점은 각 연결 리스트 노드에 헤드를 가리키는 포인터를 포함시켜 해결할 수 있다. 이 포인터를 통하여 직접적으로 대표 원소를 참조 할 수 있으며, 그 때문에 *파인드* 연산은 상수 시간이 걸린다. 그러나 이 경우 *유니온* 연산시 덧붙여지는 각 원소들이 새로운 리스트의 헤드를 가리키도록 갱신해야하기 때문에 O(*n*) 시간을 요구하게 된다. 만약 각 리스트의 길이를 추적 할 수 있다면, 항상 짧은 리스트를 긴 리스트에 덧붙이면서 요구 시간(required time) 성능을 향상시킬 수 있다. 이 방법은 *가중치-유니온 휴리스틱*(weighted-union heuristic) 라 불리며, *n*개의 원소들의 *m*개의 연이은 *메이크셋*, *유니온*, 그리고 *파인드* 연산을 수행할 경우 O(*m* + *n*log *n*) 시간을 요구한다. 점근적으로(asymptotically) 더 빠른 연산을 위해서 다른 자료 구조가 필요하다.
## 단순한 접근법 분석
지금부터 위 연산이 O(n \log(n)) 제한을 갖는다는 것을 설명하겠다. 만약 여러 리스트들이 있고 각 리스트의 노드들은 속한 리스트의 이름과 원소의 개수 정보를 저장하는 객체를 포함한다고 가정하다. 그리고 모든 리스트들의 전체 원소 개수가 n 개 있다고 가정하자. 이 리스트들 중에 어느 두 개의 리스트를 병합하고, 각 리스트들이 속한 리스트 이름이 유지되도록 노드의 업데이트 하려고 한다. 만약 리스트 A의 길이가 리스트 B보다 길 경우 병합하는 규칙은 B의 원소들을 A 안으로 병합 후 B에 속했던 원소들의 정보를 갱신하는 것이다. 리스트 L에서 특정 원소 x를 정하자. 우리는 최악의 경우 얼마나 많이 x는 속한 리스트의 이름을 갱신하는지 계산 하려고 한다. 원소 x가 속한 리스트의 길이보다 길거나 같은 리스트와 병합을 할 때 x는 속한 리스트 이름을 갱신한다. 갱신이 일어날 때마다 x가 속한 리스트의 크기는 최소 두 배 이상 증가한다. 그러므로 질문은 다음과 같다. “크기가 n이기 이전에 얼마나 자주 숫자가 두 배가 되는가?” (그러면 x를 포함하는 리스트는 모든 n개의 요소들을 포함할 것이다). 답은 정확히 \log_2(n)이다. 그래서 특정 리스트 안의 특정 한 원소는 최악의 경우 \log_2(n) 번의 갱신이 필요할 것이다. 그러므로 n개의 원소를 가지는 한 리스트는 최악의 경우 O(n \log(n)) 시간이 걸린다. 이 구조에서 각 노드는 원소가 속한 리스트의 이름을 포함하기 때문에, 파인드 연산은 O(1) 시간이 걸린다. 마찬가지로 위의 주장은 트리 자료구조의 병합에도 유의하며 다음 장에서 기술하였다. 추가적으로 이는 이진 힙(binomial heap) 과 피보나치 힙(Fibonacci heap) 자료구조에서 여러 가지 연산들의 시간을 분석하는데 활용된다.
# 서로소 집합 숲 (Disjoint-set forest)
서로소 집합 숲(Disjoint-set forest)는 각 집합이 트리로 표현되는 자료구조이며 각 노드들은 부모 노드를 참조한다. 이 구조는 1964년 Bernard A. Galler와 Michael J. Fischer가 처음으로 고안하였으며. The paper originating disjoint-set forests., 이후 정밀한 분석은 수년이 걸렸다. 서로소 집합 숲에서 각 집합의 대표는 해당 트리의 루트(root) 노드이다. *파인드* 연산은 특정 노드에서 루트 노드에 도달할 때까지 부모 노드를 따라 참조한다. *유니온*은 두 개의 트리를 하나로 병합하는 연산으로 한 루트 노드를 다른 루트 노드에 연결한다. 이 단순한 서로소 집합 숲 방법은 매우 불균형적인 트리를 생성 할 수 있기 때문에, 연결 리스트 방법과 다를 바 없다.
## 구현

### 단순한 형태
위의 연산들의 구현은 아래와 같다: **function** *MakeSet*(x) x.parent := x **function** *Find*(x) if x.parent == x return x else return *Find*(x.parent) **function** *Union*(x, y) xRoot := *Find*(x) yRoot := *Find*(y) xRoot.parent := yRoot 단순한 형태의 연산들은 매우 불균형적인 트리를 생성하기 때문에 성능 측면에서 연결 리스트 방법과 다를 바 없다.
### 유니온 바이 랭크(Union by rank)
다음 두 방법으로 위 방법의 성능을 향상시킬 수 있다. 첫 번째는 *유니온 바이 랭크*(union by rank) 방법으로 항상 작은 트리를 큰 트리 루트에 붙이는 방법이다. 트리의 깊이(depth)가 실행 시간에 영향을 주기 때문에, 깊이가 적은 트리를 깊이가 더 깊은 트리의 루트 아래에 추가한다. 그러면 두 트리의 깊이가 같을 경우에만 깊이가 증가한다. 만약 *경로 압축*(path compression)을 활용 한다면 깊이가 같을 경우 알고리즘 동작이 멈추기 때문에 깊이 대신 *랭크*(rank)라는 용어를 사용한다. 한 개의 원소를 가지는 트리는 랭크 *0*을 가지고, 같은 랭크 *r*을 가지는 두 트리가 합쳐질 경우 랭크 *r*+1의 트리가 만들어진다. 이 기술을 활용하여 *유니온* 또는 *파인드* 연산은 최악의 경우 *O*(log *n*) 실행 시간을 가진다. 향상된 *메이크셋*과 *유니온* 연산의 의사코드는 다음과 같다: **function** *MakeSet*(x) x.parent := x x.rank := 0 **function** *Union*(x, y) xRoot := *Find*(x) yRoot := *Find*(y) // if x and y are already in the same set (i.e., have the same root or representative) if xRoot == yRoot return // x and y are not in same set, so we merge them if xRoot.rank yRoot.rank yRoot.parent := xRoot else yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1
### 경로 압축
두 번째 방법은 *경로 압축*(path compression)으로 *파인드* 연산을 수행할 때마다 트리의 구조를 평평하게 만드는 방법이다. 이 방법은 루트 노드까지 순회중 방문한 각 노드들이 직접 루트 노드를 가리키도록 갱신하는 것으로, 모든 노드들은 같은 대표 노드를 공유하게 된다. 트리 윗부분을 재귀적으로 순회하면서 각 노드들이 루트 노드를 부모 노드로 참조하도록 갱신한다. 최종적으로 생성된 트리는 보다 평평하며, 이는 해당 원소뿐만 아니라 이들을 직/간접적으로 참조하는 연산들의 속도를 빠르게 해준다. 다음은 향상된 *파인드* 연산이다: **function** *Find*(x) if x.parent != x x.parent := *Find*(x.parent) return x.parent 이 두 기술들은 상호 보완 및 적용 가능하며, 각 연산마다 분할상환 시간(amortized time)은 단지O(\alpha(n))이며 여기서 \alpha(n)는 함수 n = f(x) = A(x,x)의 역 함수이다. (A는 극도로 빠르게 성장하는 아커만 함수 (Ackermann function)이다. \alpha(n)는 이 함수의 역함수이기 때문에, \alpha(n)는 n의 모든 원격 실용적인 값(remotely practical value)으로 5보다 작다. 실제로 이는 점근적 최적값(asymptotically optimal)이다: Fredman 과 Saks는 1989년에 서로소 집합 자료구조의 각 연산마다 \Omega(\alpha(n)) 단어들을 접근 할 수 있다고 보였다.
# 응용
크루스칼( Kruskal) 알고리즘을 활용하여 최소 스패닝 트리(minimum spanning tree)를 찾을 때 유니온-파인드(Union-Find) 연산의 데모 서로소 집합 자료구조는 집합의 분할을 모델링한다. 예를 들어 이 자료구조를 활용하여 무향 그래프(undirected graph)의 연결된 요소들을 추적 할 수 있다. 그리고 이 모델은 두 개의 꼭짓점(vertex)들이 같은 요소에 속하는지 또는 그 꼭짓점들을 엣지(edge)로 연결할 때 싸이클(cycle)이 발생하는지 등을 결정 할 수 있다. 유니온-파인드 알고리즘은 고성능 단일화(unification)의 구현에 활용된다.volume=21 이 데이터 구조는 점진적으로 연결된 요소(Incremental Connected Components) 기능을 구현하기 위하여 Boost Graph Library에서 활용하고 있다. 또한 크루스칼(Kruskal) 알고리즘에서 그래프의 최소 신장 트리(minimum spanning tree)를 찾는데 활용된다. 위의 서로소 집합 숲 구현은 엣지의 삭제는 지원하지 않는다(심지어 경로 압축 또는 랭크 휴리스틱(rank heuristic)이 없이도).
# 역사
서로소 집합 숲에 사용된 아이디어는 오랫동안 익숙하지만, Robert Tarjan은 1975년 처음으로 역 아커만 함수에 관하여 상한(upper bound)을 증명하였다.doi=10.1145/321879.321884 이때까지 각 연산별 시간에 대하여 최적 경계(best bound)는 O(log* n)이고 (Hopcroft와 Ullman가 증명doi=10.1137/0202024) 여기서 n은 알고리즘의 반복 횟수이다. (하지만 역 아커만 함수 보다 그다지 느리지 않다) Tarjan 과 Van Leeuwen은 최악 경우 복잡도(worst-case complexity)는 유지하면서 실제 더 효율적인 한 경로(one-pass) *파인드* 알고리즘을 개발 하였다. 2007년에는 Sylvain Conchon과 Jean-Christophe Filliâtre은 서로소 집합 숲 자료구조의 지속 버전을 개발하였다. 이는 Coq의 증명을 활용하여 이전 버전의 구조는 효율적으로 유지하고 정확성을 형식화한 버전이다.