몇 몇 프로그램들은 n개의 다른 원소들을 서로소 집합들의 한 collection으로 그룹화하는 것을 포함한다. 이러한 프로그램들은 종종 특히 두 개의 연산을 수행할 필요가 있다: 주어진 원소를 포함하는 unique set을 찾고, 두 개의 집합을 통합하는 것. 이 챕터는 이러한 연산을 지원하는 자료구조를 유지하는 방법들을 알아 본다.
Section 21.1은 서로소 집합 자료구조에 의해 지원되는 연산들을 설명하고, 간단한 적용을 보여준다. Section 21.2에서, 우리는 disjoint sets에 대한 간단한 링크드리스트 구현을 본다. Section 21.3은 rooted trees를 사용하여 좀 더 효율적인 표현을 보여준다. 그 트리 표현을 사용한 작동 시간은 이론적으로 superlinear하지만, 모든 실제적인 목적에 대해서, linear하다. Section 21.4는 매우 빠르게 성장하는 함수(a very quickly growing function)와 그것의 매우 느리게 성장하는 역함수를 정의하고 이야기한다. 그리고 이것은 tree기반의 구현에서의 연산들의 작동시간에서 나타난다. 그러고나서 복잡한 amortized analysis에 의해, 간신히 superlinear한 작동시간에 대한 상한(upper bound)를 증명한다.
21.1 Disjoint-set operations
disjoint-set data structure는 disjoint dynamic sets의 & = {S_1, S_2, ..., S_k}의 모음이다. 우리는 각 집합을 representative(대표자)로 인식한다. 그리고 그것은 그 집합의 멤버이다. 어떤 적용에서, 어떤 멤버가 대표자로 사용되었는지는 중요하지 않다; 우리는 오직, 만약 우리가 그 요청하는 사이에 그 집합을 수정하지 않고 두 번 동적 집합의 대표자를 묻는다면, 우리는 두 번 같은 답을 얻어야 한다는 것만을 신경쓴다. 다른 적용들은 대표자를 선택하는 미리 명시된 규칙을 요구할지도 모른다. 예를들어, 집합에서 가장 작은 멤버를 선택하는 것과 같은 (물론, 그 원소들이 순서지어질 수 있다는 것을 가정하고).
다른 동적 집합 구현에서 우리가 공부했듯이, 우리는 한 집합의 각 원소를 한 object로 나타낸다. x가 한 오브젝트라고 표기하고, 우리는 그 다음의 연산을 지원하고 싶다:
MAKE-SET(x)는 새로운 집합을 만드는데, 그 집합의 유일한 멤버 (따라서 대표자)는 x이다. 그 집합들이 분리되어있기 때문에, 우리는 x가 벌써 어떤 다른 집합에 들어가 있지 않아야 한다는 것을 요구한다.
UNION(x,y)는 x와 y를 포함하는 동적집합을, 가령 S_x와 S_y를 이러한 두 집합의 통합인 새로운 집합으로 합친다. 우리는 두 개의 집합들이 연산 이전에 분리되어있다는 것을 가정한다. 최종 집합의 대표자는 S_x U S_y의 어떤 멤버이다. 비록 UNION의 많은 구현들이 특정하게 S_x or S_y 둘 중 하나의 대표자를 새로운 대표자로 선택할지라도. 우리가 collection에 있는 sets들이 disjoint하기를 요구하기 때문에, 개념적으로, 우리는 집합 S_x와 S_y를 파괴한다. 그리고 그것을 collection &에서 제거한다. 실제로, 우리는 종종 그 집합들 중의 하나의 원소들을 다른 집합으로 흡수시킨다.
FIND-SET(x)는 x를 포함하는 (unique) set의 대표자에 대한 포인터를 반환한다.
이 챕터 도처에서, 우리는 두 개의 파라미터의 관점에서 서로소 집합 자료구조의 작동시간을 분석할 것이다: MAKE-SET 연산의 개수 n과 MAKE-SET, UNION, 그리고 FIND-SET 연산의 총 갯수 m. 그 집합들이 disjoint하기 때문에, 각 UNION 연산은 하나씩 그 집합들의 개수를 줄인다. n - 1 UNION 연산 후에, 그러므로 오직 하나의 집합만이 남는다. UNION 연산의 개수는 따라서 최대 n - 1이다. 또한 MAKE-SET 연산이 총 연산 횟수 m에 포함되기 때문에, 우리는 m >= n을 갖는다. 우리는 n번의 MAKE-SET 연산들이 처음 수해오디는 n번 연산이라고 가정한다.
An application of disjoint-set data structures
서로소 집합 자료구조의 많은 적용들 중 하나는 방향이 없는 그래프의 연결된 컴포넌트들을 결정하는데서 발생한다 (see Section B.4). 그림 21.1(a)는 예를들어 4개의 연결된 컴포넌트들이 있는 그래프를 보여준다.
다음의 그 절차 CONNECTED-COMPONENTS는 한 그래프의 connected components를 연산하기 위해 disjoint-set operations을 사용한다. 일단 CONNECTED-COMPONENTS가 그 그래프를 미리 처리하기만 한다면, 절차 SAME-COMPONENT는 두 정점들이 같은 연결된 컴포넌트에 있는지에 대한 질문을 답한다 (슈도코드에서, 우리는 한 그래프 G의 정점들이ㅡ 집합을 G.V로 표기하고, 간선들의 집합을 G.E라고 표기한다.)
CONNECTED-COMPONENTS(G) 1 for each vertex v in G.V 2 MAKE-SET(v) 3 for each edge(u,v) in G.E 4 if FIND-SET(u) != FIND-SET(v) 5 UNION(u,v)
SAME-COMPONENT(u,v) 1 if FIND-SET(u) == FIND-SET(v) 2 return TRUE 3 else return FALSE
CONNECTED-COMPONENTS의 절차는 초기에 각 정점 v를 그것 자신의 set에 배치한다. 그러고나서 각 간선 (u,v)에 대해, 그것은 u와 v를 포함하는 집합을 합친다. Exercise 21.1-2에 의해, 모든 간선들을 처리한 후에, 두
정점들은 같은 connected component에 있게 된다. <=>(if and only if)
대응되는 오브젝트들이 같은 집합에 있다.
따라서, CONNECTED-COMPONENTS는 절차 SAME-COMPONENT가 두 정점들이 같은 connected components에 있는지 결정할 수 있게 하는 방식으로 집합들을 연산한다. 그림 21.1(b)는 CONNECTED-COMPONENTS가 어떻게 서로소 집합을 연산하는지를 보여준다.
이 connected-components 알고리즘의 실제 구현에서, 그 그래프의 표현과 disjoint-set data structure의 표현은 서로에 대해 참조할 필요가 있을 것이다. 즉, 한 정점을 나타내는 한 오브젝트는 대응되는 disjoint-set object에 대한 포인터를 포함할 것이다. 그리고 역으로도. 이러한 프로그래밍 세부사항은 구현 언어에 따라 다르고, 우리는 그것들을 더 이상 여기에서 다루지 않는다.
21.2 Linked-list representation of disjoint sets
그림 21.2(a)는 disjoint-set data structure를 구현할 간단한 방식을 보여준다: 각 집합은 그것 자신의 링크드 리스트로 나타내어진다. 각 집합에 대한 오브젝트는 리스트에서 첫 번쨰 오브젝트를 가리키는 head라는 attributes와, 마지막 오브젝트를 가리키는 tail attribute를 갖는다. 리스트에 있는 각 오브젝트는 set member, 리스트에 있는 다음 오브젝트에 대한 포인터 그리고 그 set object 뒤로 가는 포인터를 포함한다. 각 링크드 리스트 내에서, 그 오브젝트들은 어떤 순서든지 나타날지도 모른다. 그 대표자는 리스트의 첫 번째 오브젝트에 있는 set member이다.
이 링크드 리스트 표현과 함께, MAKE-SET과 FIND-SET는 쉽다. 이것은 O(1) 시간을 요구한다. MAKE-SET(x)를 수행하기 위해, 우리는 새로운 링크드 리스트를 만드는데, 그 리스트의 유일한 오브젝트는 x이다. FIND-SET(x)에 대해, 우리는 x의 pointer를 그것의 set object로 따라가고, 그러고나서 head가 가리키는 그 object에서의 멤버를 반환한다. 예를들어, 그림 21.2(a)에서, FIND-SET(g)의 호출은 f를 반환한다.
A simple implementation of union
링크드 리스트 집합 표현을 사용하는 UNION 연산의 가장 간단한 구현은, MAKE-SET or FIND-SET보다 훨씬 더 시간이 걸린다. 그림 21.2(b)가 보여주듯이, 우리는 y의 list를 x의 list 끝에 덧 붙여서 UNION(x,y)를 수행한다. x의 list의 대표자는 그 최종 집합의 대표자가 된다. 우리는 빠르게 y의 list를 어디에 붙일지를 찾기 위해 x의 list에 대해 tail pointer를 사용한다. y의 list의 모든 멤버들이 x의 list에 참여하기 때문에, 우리는 y의 list에 대한 set object를 파괴할 수 있다. 불행하게도, 우리는 원래 y의 list에 있는 각 오브젝트에 대한 set object의 포인터를 업데이트해야만 한다. 그리고 이것은 y의 리스트 길이만큼 선형으로 시간이 걸린다. 21.2 그림에서, 예를들어, UNION(g,e)는 b,c,e,h에 대한 오브젝트들에 대해서 포인터들이 업데이트 되도록 한다.
사실, 우리는 O(n^2) time을 요구하는 n개의 오브젝트들에 대한 m개의 연산의 순서를 쉽게 구성할 수 있다. 우리가 x_1, ... , x_n의 오브젝트들을 가지고 있다고 가정하자. 우리는 MAKE-SET 연산의 sequence를 수행한다. 그리고 다음에 그림 21.3에 보여지는 n - 1의 UNION 연산을 수행한다. m = 2n - 1이 되도록 하기 위해서이다. 우리는 n개의 MAKE-SET 연산들을 수행하는데 O(n)의 시간이 걸린다. i번째 UNION 연산은 i objects들을 업데이트하기 때문에, 모든 n - 1 UNION 연산으로 업데이트 되는 총 오브젝트의 수는
총 연산의 개수는 2n -1이다. 그래서 각 연산은 평균적으로 O(n) 시간을 요구한다. 즉, 한 연산의 amortized time은 O(n)이다.
A weighted-union heuristic
최악의 경우에 UNION 절차의 위의 구현은 호출마다 O(n)의 평균 시간을 요구한다. 왜냐하면 우리가 더 긴 list를 더 짧은 list에 추가할 지도 모르기 때문이다; 우리는 더 긴 list의 각 멤버들에 대한 set object의 포인터를 업데이트 해야만 한다. 대신에 각 list가 또한 list의 길이를 포함한다고 가정하자 (우리가 쉽게 유지할 수 있는 것이다) 그리고, 우리가 항상 더 짧은 list를 더 긴 것에 추가한다고 가정하자. 그리고 이것은 임의로 ties를 분해한다. 이 간단한 weighted-union heuriostic으로, 단일의 UNION operation은 여전히 Ω(n) 시간이 걸린다. 만약 두 집합이 Ω(n) 멤버들을 갖는다면. 다음의 정리가 보여주듯이, 그러나, m개의 MAKE-SET, UNION 그리고 FIND-SET 연산들의 sequence는, 그리고 그것들 중 n은 MAKE-SET 연산이다, O(m + nlgn)이 걸린다.
Theorem 21.1
서로소 집합의 링크드 리스트 표현과 weighted-union heruistic을 사용하여, m개의 MAKE-SET, UNION, 그리고 FIND-SET 연산의 sequence, 그 중에서 MAKE-SET 연산은 n개이고, 이것은 O(m + nlgn) time이 걸린다.
Proof 각 UNION 연산이 두 개의 서로소 집합을 통합하기 때문에, 우리는 최대 n - 1개의 UNION 연산을 결국 수행한다. 우리는 이제 이러한 UNION 연산에 의해 걸리는 총 시간을 제한한다. 우리는 각 오브젝트에 대해 그것의 set object에 대한 오브젝트의 포인터가 업데이트 되는 횟수에 대해 상한을 결정하여 시작한다. 특정한 오브젝트 x를 고려하자. 우리는 매번 x의 포인터가 업데이트 되었다는 것으 ㄹ알고, x가 더 작은 집합으로 시작했었다는 것을 안다. 그러므로 x의 포인터가 업데이트 된 처음에, 그 최종 집합은 적어도 2 개의 멤버를 가졌을 것이다. 유사하게, x의 포인터가 업데이트 되는 그 다음에, 그 최종 집합은 적어도 4개의 멤버들을 가진다. 계속해서, 우리는 어떤 k <= n에 대해, x의 포인터가 lg k 번 업데이트 된 후에, 그 최종 집합이 적어도 k개의 멤버들을 갖는다는 것을 관찰한다. 가장 큰 집합이 최대 n개의 멤버들을 갖기 때문에, 각 오브젝트의 포인터가 최대 ceil(lg n) 횟수로 업데이트 된다. 모든 UNION 연산에 대해. 따라서 모든 UNION 연산에 대해 오브젝트 포인터들을 업데이트하는데 걸린 시간은 O(n lgn)이다. 우리는 또한 tail pointers와 list length를 업데이트하는 것을 설명해야만 한다. 그리고 이것은 오직 UNION 연산당 O(1) 시간이 걸린다. 모든 UNION 연산에 소비되는 총 시간은 따라서 O(n lg n)이다.
m개의 연산들의 전체 sequence에 대한 시간은 쉽게 따라 나온다. 각 MAKE-SET과 FIND-SET 연산은 O(1) 시간이 걸리고, 그것들의 O(m)이 있다. 전체 sequence에 대한 총 시간은 따라서 O(m + nlgn)이다.
21.3 Disjoint-set forests
서로소 집합의 더 빠른 구현에서, 우리는 집합을 rooted trees로 나타낸다. 그리고 각 노드가 한 멤버를 포함하고, 각 트리는 한 집합을 대표한다. 그림 21.4(a)에서 보여지듯이, disjoint-set forest에서, 각 멤버는 그것의 부모만을 가리킨다. 각 트리의 root는 대표자를 포함하고, 그것 자신의 부모이다. 우리가 보듯이, 비록 이 표현을 사용하는 간단한 알고리즘들은 링크드 리스트 표현을 사용하는 것보다 더 빠르지 않을지라도, 두 가지 휴리스틱을 도입하여 - "union by rank" 와 "path compression" - 우리는 asymptotically하게 최적의 disjoint-set data structure를 얻을 수 있다.
우리는 다음과같이 세 개의 disjoint-set operations을 수행한다. MAKE-SET 연산은 간단히 한 가지 노드가 있는 한 트리를 만든다. 우리는 다음의 parent pointers를 따라서 우리가 트리의 root를 찾을 때 까지 FIND-SET 연산을 수행한다. 이 root를 향하여 가는 simple path에서 방문된 노드들은 find path를 구성한다. 그림 21.4(b)에서 보여지듯이, UNION 연산은 한 트리의 root가 다른 것의 root를 가리키도록 한다.
Heuristics to improve the running time
지금까지, 우리는 링크드 리스트 구현에서 개선하지 않았다. n - 1 UNION 연산의 sequence는 n개의 노드들의 linear chain인 tree를 만들지도 모른다. 그러나 두 가지 heuristics를 사용하여, 우리는 전체 m개의 연산에서 거의 linear한 작동시간을 얻을 수 있다.
union by rank라는 첫 번째 heuristic은 우리가 링크드 리스트 표현에서 사용했던 weighted-union heuristic과 유사하다. 명백한 접근법은 더 적은 노드를 가진 트리의 root가 좀 더 많은 노드를 가진 트리의 root를 가리키도록 만드는 것이다. 각 노드에서 root로 하는 subtree의 사이즈를 explicitly하게 추적하기보다는, 우리는 그 분석을 쉽게해주는 한 접근법을 사용할 것이다. 각 노드에 대해서, 우리는 rank를 유지하는데, 그 rank는 그 노드의 height의 상한이다. union by rank에서, 우리는 UNION 연산 동안 더 작은 rank point를 가진 root를 더 큰 rank를 가진 루트로 향하도록 만든다.
path compression이라는 두 번째 heuristic은 또한 꽤 간단하고, 매우 효과적이다. 그림 21.5에서 보여지듯이, 우리는 FIND-SET 연산 동안에 find path point가 직접적으로 root를 가리키도록 하기 위해서 그것을 사용한다. Path compression은 어떠한 ranks들도 바꾸지 않는다.
Pseudocode for disjoint-set forests
union-by-rank heuristic를 사용하여 disjoint-set forest를 구현하기 위해, 우리는 ranks를 추적해야만 한다. 각 노드 x와 함꼐, 우리는 x.rank 라는 정수 값을 유지하고, 그것이 x의 높이의 상한이다 (x와 후손 leaf사이의 가장 긴 simple path에서의 간선의 개수이다). MAKE-SET가 singleton set만들 때, 대응되는 트리에서의 단일 노드는 0의 초기 rank를 갖는다. 각 FIND-SET 연산은 모든 ranks들이 변하지 않게 남겨둔다. UNION 연산은 두 가지 경우를 갖는다. 그리고 그것은 트리들의 roots가 동일한 랭크를 가졌는지에 의존한다. 만약 그 roots들이 동일하지 않은 랭크들을 갖는다면, 우리는 더 높은 rank를 가진 root가 더 낮은 rank를 가진 root의 부모가 되도록 만든다. 하지만, 그 랭크들은 변하지 않게 된다. 대신에 만약 그 roots들이 같은 랭크들을 갖는다면, 우리는 임의로 그 루트들 중에 하나를 부모로 선택하고, 그것의 랭크를 증가시킨다.
이 방식을 슈도코드로 표현해보자. 우리는 node x의 부모를 x.p로 표기한다. UNION에 의해 호출되는 subroutine인 LINK procedure은 두 개의 roots에 대한 포인터를 입력으로 받는다.
MAKE-SET(x) 1 x.p = x 2 x.rank = 0
UNION(x,y) 1 LINK(FIND-SET(x), FIND-SET(y))
LINK(x, y) 1 if x.rank > y.rank 2 y.p = x 3 else x.p = y 4 if x.rank == y.rank 5 y.rank == y.rank + 1
path compression이 있는 그 FIND-SET procedure는 꽤 간단하다:
FIND-SET(x) 1 if x != x.p 2 x.p = FIND-SET(x.p) 3 return x.p
FIND-SET procedure는 two-pass method이다: 그것이 재귀함에 따라, 그것은 root를 찾는 find path에 해해 한 pass를 구성하고, 그 재귀가 돌아옴에 따라, 그것은 각 노드를 직접 root를 가리키도록 업데이트하는 find path로 다시 되돌아온다. FIND-SET(x)의 각 호출은 line 3에서의 x.p를 바노한한다. 만약 x가 root라면, 그러면 FIND-SET 은 line 2를 건너띄고, 대신에 x.p를 반환한다. 그리고 그것이 x이다; 이것은 재귀가 끄탄ㄴ 경우이다. 만약 그렇지 않다면, line 2가 실행되고, 파라미터 x.p가 있는 재귀 호출이 그 root에 대한 포인터를 반환한다. Line 2는 직접적으로 root를 가리키는 node x를 업데이트 한다. 그리고 line 3를 이 포인터를 반환한다.
Effect of the heuristics on the running time
개별적으로, union by rank or path compression 둘 중 하나는 서로소 집합 forests의 연산 작동 시간을 개선시키고, 그 개선은 우리가 두 휴리스틱을 함꼐 사용할 때 훨씬 더 좋아진다. 홀로, union by rank는 O(mlgn)의 작동시간을 만들어 낸다 (see Exercise 21.4-4), 그리고 이 제한은 tight 하다 (Exercise 21.3-3을 보아라). 비록 우리가 그것을 여기에서 증명하지 않을지라도, n개의 MAKE-SET 연산 (끄러므로 최대 n - 1개의 UNION 연산) 그리고 f개의 FIND-SET 연산들의 sequence에 대해, path-compression heuristic은 홀로 O(n + f * (1 + log_2+f/n^n의 최악의 경우 작동시간을 준다.
우리가 union by rank와 path compression을 둘 다 사용할 때, 최악의 경우 running time은 O(m a(n))인데, 여기에서 a(n)은 very slowly growing function이고, 우리는 Section 21.4에서 이것을 정의한다. 서로소 집합 자료구조의 납득할만한 적용에, a(n) <= 4이다; 따라서, 우리는 모든 실제 상황에서 running time을 m에서 선형으로 볼 수 있다. 그러나 엄격히 말해서, 그것은 superlinear하다. Section 21.4에서 우리는 이 상한을 증명한다.
댓글 없음:
댓글 쓰기