Union-find Data Structure(연결 리스트를 이용한 처리)

상호 배타적 집합의 처리

상호배타적 집합만을 대상으로 한다.  이때 교집합은 제외된다.

Union(합집합)을 지원해주는 연산 작업들에는

   ■  Make-Set(x) : 원소 x로만 이루어진 집합을 만든다.

   ■  Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다.

   ■  Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합을 만든다.

 

 

집합을 처리하는 방법에는 연결리스트를 이용하는 방법과 트리를 이용하는 방법이 있다.

• 연결 리스트를 이용한 상호 배타적 집합의 처리 방법을 이해한다.
• 연결 리스트를 이용해 집합을 처리하는 연산들의 수행 시간을 분석한다.
• 트리를 이용한 상호 배타적 집합의 처리 방법을 이해한다.
• 트리를 이요해 집합을 처리하는 연산들의 수행 시간을 분석한다.

 

 

연결 리스트를 이용한 처리

같은 집합의 원소들은 하나의 연결 리스트로 관리한다.

연결 리스트의 맨앞의 원소를 집합의 대표 원소를 삼는다.

 

 

1) Make-Set(x)을 한 상태

Make-Set(x): 원소 x로만 이루어진 집합을 만든다.

이때 대표노드는 자신이 된다. 

 

 

2) Find-Set(x)을 한 상태

Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다.

위의 그림에서 집합을 두개로 나눌 수 있다. 위의 연결 리스트를 집합 A, 아래 연결 리스트를 집합 B라고 하자.각 집합의 노드들은 맨앞의 노드를 대표노드로 포인터를 가리키고 있다.

 

 

3) Union(x,y)을 한 상태

Union(x,y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합을 만든다.

이 상황에서 집합 A를 부집합, 집합 B를 주집합이라고 저의 한다. 

주집합 B에 부집합 A를 붙이는데 집합 A에서 각 노드들이 가리키고 있던 대표노드의 포인터를 

집합 B의 대표노드로 바꿔준다. 그리고 NIL를 가리키고 있던 집합 B의 마지막 노드를 집합 A의 머리 노드를 가리키게 연결해준다.

Union을 이러한 방식으로 해주는 이유는 무게를 고려한 Union방식 때문이다.

무게를 고려한다는 의미는 연결 리스트로 된 두집합을 합칠 때 작은 집합을 큰 집합의 뒤에 붙이는 것을 말한다. 이러한 이유는 연결하는 집합의 대표 원소를 가리키는 포인터 갱신 작업을 최소화 하기 위한 것이다. 

 

 

4) 수행 시간

연결 연결 리스트를 이용해 표현되는 배타적 집합에서 무게를 고려한 Union을 사용할 때, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set이라면 이들의 총 수행시간은 O(m+nlogn)이다.