[COSE214] Data structures for disjoint sets

disjoint set이란 intersection이 공집합인, 서로 공통된 원소를 가지지 않은 두 개 이상의 집합을 말하는 것으로 disjoint set data structure은 collection of disjoint set을 의미한다. disjoint set data structure은 3가지 연산을 제공하는데, make-set(x)는 x를 멤버로 하는 new set을 만드는 연산이고, union(x,y)는 x와 y를 각각 가지는 두 집합을 하나로 합치는 연산이며, find-set(x)는 x를 포함하는 집합을 찾아 그 집합의 대표 원소를 반환하는 연산을 말한다. 

 

이 때 이 연산들의 time complexity는 항상 2개의 parameter m, n에 의해 정의된다. n은 make-set operation이 일어나는 횟수를 의미하며, m은 make-set operation + union operation + find-set operation이 일어나는 횟수의 합을 말하므로 mn이 항상 성립한다.

 

이 때 disjoint set의 linked-list representation(집합을 연결 리스트로 표현하는 방식 - 각 원소는 리스트의 노드로 표현되며, 각 노드는 해당 집합의 다음 노드를 가리키는 포인터를 가지고 있음.)과 weighted-union heuristic 방식(두 개의 집합을 합칠 때, 더 작은 집합을 더 큰 집합에 합치는 방식)을 사용하면 time complexity는 O(m+nlgn)이 된다. 이는 make-set 작업은 O(1) 시간이 소요되고, union 작업과 find-set 작업은 O(lgn)이 걸리기 때문에 m개의 make-set 작업과 n개의 make-set, union, find-set 작업을 거치면 총 O(m+nlgn) 시간이 걸린다. 

 

또한 disjoint set forest에서 각 트리에 대해 높이 대신 rank를 사용하여 더 낮은 트리를 더 큰 트리에 연결하여 트리의 높이를 최소화하는 방식인 union by rank 와 find-set 작업 시에 경로 상의 모든 노드를 직접 루트 노드에 연결하여 경로를 압축하는 기법인 path compression을 사용할 때 worst-case의 경우 time complexity는 O(m (n))이 된다.