서로소 집합, 상호 배타 집합(Disjoint-Sets)

 서로소 또는 상호 배타 집합들은 서로 중복으로 퐇마된 원소가 없는 집합들을 말한다.

 

즉, 서로소 집합들은 서로간의 교집합이 없는 것이다.

 

서로소 집합은 집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분할 수 있다.

 

이를 대표자(Representative)라고 한다.

 

상호 배타 집합, 즉 서로소 집합을 표현하는 방법으로는 

 

연결 리스트, 트리 등이 있다.

 

또 이와 관련된 연산은

 

Make-Set(x) -  대표자가 x인 집합을 만드는 연산

 

Find-Set(x) - 대표자가 x인 요소를 찾는 연산

 

Union(x,y) - 대표자가 각각 x, y인 집합을 합하는 연산

 

등과 같이 들 수 있다. 

 

 

 

 위에서 언급한 것처럼 서로소 집합의 표현 방법으로는 연결 리스트, 트리 등으로 할 수 있다고 했는데,

 

연결리스트의 경우는 다음과 같이 표현할 수 있다.

 

우선 연결리스트에 쓰이는 노드는 이중 연결 리스트를 사용한다.

 

data를 저장하는 data 필드와 대표 원소를 가리키는 링크 필드,

 

다음 원소를 가리키는 링크 필드로 구성할 수 있다.

 

또 대표 원소는 대표 원소를 가리키는 링크 필드에 자기 자신을 가리키고,

 

대표 원소가 아닌 원소는 대표 원소를 가리키는 것이다. 

 

 

 

이런식으로 한 집합의 연결리스트는 위와 같다.

 

이러한 연결리스트가 두 개 이상 있고, 각각의 대표 원소가 다를 때는 

 

두 집합이 연결되지 않기 때문에 서로소 집합으로 볼 수 있다.

 

이 때 Find-Set 연산을 실행할 경우, 각 노드에서 가리키는 대표 원소를 불러오면 되고,

 

Union 연산을 할 경우 다른 집합에 속한 연결리스트들이 가리키는 대표 원소를 합집합의 대표 원소로 수정하면 된다.

 

Make-Set 연산의 경우에는 새로운 집합을 생성하고, 새로 생성된 집합의 경우 해당 원소가 대표 원소이기 때문에 

 

data를 입력하고, 대표 원소를 가리키는 링크 필드는 본인을 넣는다. 다음 원소를 가리키는 링크 필드는 

 

새롭게 생성되었기 때문에 NULL을 넣는다.

 

그렇다면 트리는 어떻게 표현할까?

 

 

트리로 표현할 경우 이런 형태로 생각할 수 있다.

 

자식 노드는 부모 노드를 가리키고, 루트 노드가 대표자가 된다.

 

따라서 Find-Set 연산을 실행할 경우 자식 노드에서 부모 노드로 거슬러 올라가며

 

루트 노드를 찾아 반환하게 되며,

 

Union 연산을 실행할 경우, 다른 트리의 루트 노드의 부모를 존재하는 트리의 노드 중 하나로 설정하는 것이다.

 

 

 

이렇게 서로소인 집합 트리를 

 

Union 연산을 실행하면

 

 

이런 식으로 붙여 버릴 수 있다. 어디에 붙이는 가는 작성한 연산에 따라 다르게 된다.

 

Make-Set 연산의 경우 

 

 

이런 형태의 트리를 만드는데,

 

자식은 본인이고, 부모 노드 또한 본인을 가리키는 것이다. 

 

 

코드로 생각해 보면,

 

멤버 x를 포함하는  새로운 집합을 생성하는 Make-Set(x) 연산은

Make-Set(x){

parent[x]=x;

}

라고 할 수 있다.

 

각 노드의 부모 노드를 저장하는 배열을 생성해 놓은 다음, 해당 노드의 부모를 입력할 때 자기 자신을 입력하는 경우

 

해당 노드는 루트 노드이고, 대표 노드이다.

 

그렇다면 Find-Set 연산은 어떨까?

 

Find-Set(x){
	if(x==parent[x]) return x;
    else return Find-Set(parent[x]);
 }

 

위와 같이 표현할 수 있다.

 

재귀 호출을 이용해 해당 노드의 부모 노드가 해당 노드가 아닐 경우 계속해서 거슬러 올라가는 것이다.

 

루트 노드가 나올 때까지.

 

마지막으로 Union 연산을 알아보자.

 

Union(x,y){
	parent[Find-Set(y)]=Find-Set(x);
}

 

Union 연산은 간단하게, y집합의 대표 원소를 찾은 다음, 해당 원소의 부모 노드를 자기 자신에서 

 

x 집합의 대표 원소로 바꿔주는 것이다. 

 

 

 

 

 

하지만 이런 트리 구조의 경우 문제점이 있을 수 있다.

 

편향 트리 구조일 경우 쓸데없이 연산이 많아질 수 있다는 것이다.

 

이를 해결하기 위해서 Rank를 사용하거나 Path Compression 방식을 이용해 연산을 줄일 수 있다.

 

 

라고 이해했다.