집합의 처리

집합의 처리 영역에서는 두 부분으로 나눠 진다.

 

1. 연결 리스트를 이용한 집합의 처리

 

2. 트리를 이용한 집합의 처리

 

우선은 연결리스트를 이용한 집합의 처리를 알아보도록 한다.

 

상호 배타적 집합의 관리를 위해 필요한 세가지 연산이 있다.

 

 

 

1. 연결 리스트를 이용한 집합의 처리

---

Make-Set(x) : 원소 x로만 구성된 집합을 만든다.

                   

Find-Set(x) : 원소 x를 가진 집합을 알아낸다.

 

Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합 하나로 합친다.

---

Make-Set(x) : 원소 하나로 구성된 집합을 만드는데, 노드를 하나 만들어 해당원소를 저장한다.

대표노드로는 자신을 가리키도록 하고, 다음 원소는 없으므로 포인터는 NIL로 해둔다.

 

Find-Set(x) : 원소 x가 포함된 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.

 

Union(x,y) : Find-Set(x) 와 Find-Set(y)를 이용하여 x와 y가 속한 집합의 대표 노드를 각각 알아낸 다음 두 집합 중 하나를 다른 집합 뒤에 붙인다.

 

 

연결 리스트에서의 방법을 기다리는 시간은 O(m)의 시간이 든다,

 

 

2. 트리를 이용한 집합의 처리

 

트리를 이용한 집합의 처리는 연결 리스트를 이용한 집합의 처리보다 효율적이며, 흔히 다루는 트리와는 조금 다른 방식의 표현을 쓴다. 트리를 나타낼 때는 보통 노드가 자식 노드를 가리키도록 하지만 여기서는 자식 노드가 부모 노드를 가리키도록 한다.

두 집합을 합치는 작업에서 차이는 트리를 이용한 집합의 처리는 한 집합의 루트가 다른 집합의 루트를 가리키도록 포인터 하나만 변경해주면 된다.

 

연산의 효율을 높이는 방법

 

랭크를 이용한 Union

 

각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크 라는 이름 으로 저장하게 된다.  단 하나의 노드로 된 트리는 높이를  0이라고 정의하는데 루트 노드의 랭크가 해당 집합의 랭크가 된다.

이 방법에서는 두 집합을 합칠 때 링크가 낮은 집합을 랭크가 높은 집합에 붙인다.

 

경로 압축

 

경로 압축은 Finde-Set을 행하는 과정에 경로의 길이를 줄이는 아이디어를 넣은 것이다. Find-Set과 같이 행하되 Find-Set을 수행하는 과정에서 나는 모든 노드가 직접 루트를 가리니키는 포인터를 바꾸어 준다. 

 

방법의 평균수행시간이 O(1)인데 

임의 노드 랭크는 O(logn)의 시간이 수행된다.