[자료구조] 트리/disjoint set의 union과 find

트리를 사용해서 '집합'을 표현해보자

집합의 모든 원소는 0, 1, 2, ..., n-1이라고 가정한다. 

 

모든 집합은 disjoint된다고 가정한다. (각각 집합들끼리 겹치는 원소가 없음)

 

얘는 0~9인 예제이다. 

집합에 대해 수행하고자 하는 연산은 다음 두 가지이다. 

(1) disjoint set union

(2) find(i)

 

(1)은 A∪B를 할 수 있다는 의미, 즉

(2)는 원소 i가 속한 집합을 리턴받는거 가능

 

A∪B을 하려면 어케 할까...

 

두 트리중 하나를 다른 트리의 서브트리로 만들면 된다. 

 

저 위에 그림에서 S1 ∪ S2를 하려고 하면, 

 

이렇게

 

하면 되는것처럼 말이다!

 

 

 

 

 

두가지 함수를 짜보자!

 

void simpleUnion(int i, int j){

parent[i] = j;

}

int simpleFind(int i){

for (;parent[i]>=0; i=parent[i]) ;

return i;

}

 

얘네의 성능을 분석해보자.

simpleUnion( )

 

변질트리

여기서 find(0), ....find(n-1)까지 하면 재귀적으로 호출되서 1+2+...== n^2를 따르게 된다. 

 

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

 

[weighting rule] root i를 가진 트리의 노드 수가 root j를 가진 트리의 노드 수보다 적으면 j를 i의 부모로 만들고, 그렇지 않으면 i를 j의 부모로 만든다 .

 

weighting rule을 반영해서 다시 짠 union함수가 weightUnion()이다.

 

void weightUnion(int i, int j){

/* union the sets with roots i and j, i!=j, using the weighting rule. 

parent[i] = -count[i] and 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;

 

}

 

}

 

??...코드가 뭔소린지 모르겠다....