집합의 처리
집합의 처리를 위해서는 다음 3가지의 연산이 필요하다.
1) Make-Set(x) : 원소 x로만 구성된 집합을 만든다.
2) Find-Set(x) : 원소 x를 가진 집합을 알아낸다.
3) Union(x, y) : 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다.
1. 연결리스트 이용
링크드 리스트를 이용하면 하나의 원소로 이루어진 집합은 아래와 같다.(Make-Set으로 만든 결과)
이로 이루어진 두집합을 합치는 과정은 아래와 같다.
{a,b,c}집합의 대표 원소를 {d,e,f,g,h}로 바꾸어준다. 이때 작은 집합을 큰집합 뒤에 붙이는 것이 비용적으로 이득이다. 이를 Weighted Union이라고 한다.
수행시간을 비교해보면 Make-Set이나 Find-Set은 상수시간만 든다. Find-Set은 맨 위에 대표노드만 return하면 되기 때문이다. 하지만 Union은 경우에 따라 걸리는 시간이 달라진다.
이를 이용하여 아래의 정리를 증명할 수 있는데
연결 리스트를 이용해 표현되는 배타적 집합에서 무게를 고려한 Union을 사용할 때, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set이라면 이들의 총수행시간은 O(m+nlogn)이다.
이의 증명은 다음과 같다.
Make-Set이 n번임으로 원소의 총 수는 n개이고 Make-Set과 Find-Set은 상수시간이 걸림으로 아무리 시간을 많이 잡아도 O(m)이다. 이제 Union을 보자. 이때 임의의 원소 x에 대해 확인을 해본다. Union을 할 때 원소 x가 큰집합에 있으면 대표를 갱신할 필요가 없지만 작은 집합에 있다면 갱신을 한번 해야 한다. 또한 작은 집합에 있다면 x가 속한 집합의 크기는 최소 2배 이상 커진다. 자기보다 큰 집합 + 자신 > 자신 + 자신 이기 때문이다. 따라서 x가 속한 집합이 갱신이 일어날 때 마다 1->2^2->2^3->... 이상의 비율로 커지게 된다. 하지만 원소가 총 n개임으로 아무리 많이 갱신이 되어도 을 넘을 수가 없다. 또한 원소의 총수는 n개임으로 위에서 임의의 원소 하나만 생각했던것을 최악의 경우 n개의 원소 모두가 적용된다고 해도
을 넘지 않는다. 따라서 전체시간은 O(m+nlogn)이다.
2. 트리를 이용한 집합의 처리
위의 링크드 리스트보다 효율적인 방법이다. 보통 트리는 부모노드가 자식노드를 가르키게 되있지만 이경우는 반대로 자식노드가 부모 노드를 가르키게 만든다. 그리고 맨위의 루트노드는 NULL이 아닌 자기 자신을 가르킨다.
Union을 할때는 두집합중 한집합의 루트노드가 다른 집합의 루트노드를 가르키면 된다.
이의 연산을 효율적으로 하려면 트리의 높이를 낮게 유지시키는 것이다. 그 방법은 다음과 같다.
1) 랭크를 이용
랭크는 트리의 높이인데 리프노드의 랭크를 0으로 하고 하나 위로 올라갈때마다 랭크를 높인다. 그리고 Union할때 낮은 랭크의 집합을 큰 랭크의 집합에 붙인다. 이렇게 되면 트리의 랭크를 보존할 수 있다. 다만 두 집합의 랭크가 같은 경우는 전체 랭크가 1이 올라가게 된다.
2) 경로 압축
Find-Set과정에서 재귀적으로 단계별로 올라가며 루트노드를 찾는데 이 과정에서 각 노드가 직접 루트노드를 가르키게 한다.
위의 과정을 코드로 직접 구현한 결과가 아래이다.
class Tree_set:
def __init__(self):
self.root = None
def Make_set(self, x):
x = node(x)
x.parent = x
self.root = x
def Find_set(self, x):
if x == x.parent:
return x
else:
x.parent = path_compression(x.parent)
return x.parent
def Union(self, x, y):
y_root = Find_set(y)
x_root = Find_set(x)
if x_root.rank > y_root.rank:
y_root.parent = x_root.parent
return x_root
elif y.rank > x.rank:
x_root.parent = y_root.parent
if y.rank == x.rank:
y_root.rank += 1
return y_root
3) 효율성
(1)
랭크를 이용한 Union을 사용하면 랭크가 k인 노드를 대표하는 집합의 원소 수는 최소 2^k개이다.
우선 랭크가 0이면 원소가 1개이다. 따라서 (1)의 정리를 만족한다. 랭크가 r일때 최소 2^r개의 원소를 가진다고하면 랭크가 r인 트리와 r보다 작은 트리를 합치면 랭크는 유지가 되면서 원소의 수만 늘어난다. 랭크가 r+1로 증가하는 경우는 두 집합의 랭크가 r로 같을때인데 이경우 각각 2^r개의 원소를 최소한으로 가진다고 하였음으로 합치면 최소 원소의 갯수는 2^(r+1)개이다. 그리고 이때의 랭크는 r+1이다. 따라서 첫번째, r번째, r+1번째 모두 만족함으로 수학적 귀납법에 의하여 위의 정리는 성립하게 된다.
(2)
랭크를 이용한 Union을 사용하면, 원소의 수가 n인 집합을 표현하는 트리에서 임의의 노드의 랭크는 O(logn)이다.
정리 (1)에서 랭가 k인 노드를 대표하는 집합 원소 수는 최소 2^k개라고 하였다. 이때 최소의 경우는 일렬일때이다. 따라서 반대로 원소의 수가 k개라면 최대의 랭크는 logk이다.
(3)
트리를 이용해 표현되는 배타적 집합에서 랭크를 이용한 Union을 사용할 때, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set이라면, 이들의 총 수행 시간은 O(mlogn)이다.
Make-Set과 Union은 수행시간이 O(1)이고 m번일어났다고 하면 O(m)이다. 또한 Make-Set이 n번 발생했음으로 원소의 갯수는 n이다. 그리고 Find-Set은 랭크에 따라 달라지는데 (2)에서 임의의 노드의 랭크가 O(logn)인것을 알 수 잇다. 따라서 총 수행시간은 O(mlogn)임을 알 수 있다.
(4)
트리를 이용해 표현되는 배타적 집합에서 랭크를 이용한 Union과 경로 압축을 이용한 Find-Set이 동시에 사용되면, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set일때 이들의 수행시간은 O(mlog*n)이다.
여기서 mlog*n은 아래의 의미를 가진다.
n에 log를 k번 적용할 때 최초로 1이하가 될때의 k를 의미한다. 이는 매우 매우 작은 사실상 상수로 볼 수 있다. 따라서 이 정리는 결국 최악의 경우에는 O(m)의 시간이 든다는 것이다.