2. Union-Find

Union-Find는 다음과 같은 문제를 해결한다.
 
N개의 Object가 주어졌을 때
 
두 Object가 연결되어있는지 여부(Find)
API : boolean connected(int p, int q)
 
두 Object의 연결(Union)
API : void union(int p, int q)

연결내부에 순서가 없기때문에 집합의관점에서 같은집합인지여부확인(Find) 합집합 생성(Union) 용도로 사용가능하다.
 
이것을 이용하면 물리적인 문제뿐만 아니라, 격자형태에서 연결구조인 사진, 분산화된 네트워크 연결구조 등 여러 문제를 풀 수 있다. 결론적으로 가장 최적의 성능을 내는 알고리즘은 weighted QU + path compression 이다.
 

Algorithm	Worst-case time
quick-find	N
quick-union	N
weighted QU	logN
QU + path compression	logN
weighted QU + path compression	log*N

 
log*N은 1이 될 때까지 N에 대해 log연산을 계속 수행했을 때 수행한 총 횟수를 말한다.
이 때, 2^65536 개의 N에 대해서 union-find를 위한 Data Access는 고작 5번밖에 수행되지 않는다.
 
실제로 구현은 배열을 통해 이루어지며, QU(quick-union)은 추상자료구조로서 Tree를 사용한다.
 
quick-find는 가장 단순하지만 N개의 Object에 대해서 N번 union을 했을 때 N^2번 Data Access가  발생한다는 문제점이 있다. 10000개의 object라면 100000000번, 즉 1억번 Data Access가 될 것이다.
 
quick-union은 단순히 구현했을 때 quick-find보다도 좋지 않다. 이것은 Tree의 Balance를 무시하고 비대칭적으로 Tree가 성장했을 때 Find시 많은 비용을 발생시킨다.
 
weighted QU는 quick-union의 이와같은 단점을 상쇄하기 위해 Tree의 size를 추적하고, 작거나 같은 트리의 root가 크거나 같은 트리의 root에 연결됨으로서 Balance를 맞춘다. 이론적으로는 size가 x이고 depth가 d인 tree가 union될 때, union된 tree의 depth는 depth+1까지 밖에 증가할 수 없고, tree의 size는 큰 tree가 항상 x보다 size가 크거나 같으므로, 2x보다 크거나 같아야한다.
따라서, 이것을 더이상 union불가능 할 때까지 i번 시도한다면, 최종적인 tree의 size는 x*2^i <= N 를 만족할 것이다.
이것을 양쪽에 로그를 씌우면,  logx + i <= logN
초기 트리 size인 x=1일 경우, i <= logN 이고, depth = d + i 인데, 초기트리는 d = 0이므로  depth = i가 되어
depth <= logN 이 되어 항상 이진로그N 보다 항상 작거나 같게 된다.
따라서, 이후에 union 또는 find연산을 할 때 worst-case에서 최대 logN번까지만 탐색을 하게되어 성능이 개선된다.
 
QU + path compression은 QU에서 find할 때 경로상에 있는 노드들을 직접 root와 직접 연결되도록 tree를 재구성함으로서 tree를 최대한 flat하게 만들어 tree의 depth를 낮추고 성능을 개선하는 방법이다. 
 
weighted QU + path compression은 QU + path compression에서 weighted QU로만 바뀌었을 뿐 원리는 동일하다.
가장 성능이 좋다.
 
알고리즘의 적용예시로 Percolation(유입/침투)문제가 있는데, 이는 격자구조에서 연결성을 확인함으로서 격자구조 위에서 아래방향으로 침투가 되어있는지를 지속적으로 체크하고 시뮬레이션하는 것을 골자로 한다.
이렇게 시뮬레이션으로 수백 수천만번 연결성을 확인하는 경우 union-find의 알고리즘을 사용하면 시뮬레이션 성능을 크게 개선할 수 있다.