[자료구조] #20 Disjoint Set

• Disjoint set (서로소 집합)

 

두 집합의 교집합이 empty하면 disjoint하다고 한다.

입력을 여러 개의 상호 배타적인 그룹으로 나누어 관리할 때 사용한다.

 

• 주요 연산

 

make-set(u) : 원소 u가 주어졌을때 u만을 담는 새로운 집합을 생성한다.

find-set(u) : 입력 원소 u를 담고 있는 집합을 반환한다.

union(u, v) : u를 가지고 있는 집합과 v를 가지고 있는 집합을 합친다.

 

Disjoint set에서는 교집합 연산을 고려할 필요가 없다.

 

• Disjoint Set의 표현

 

Disjoint set은 non-binary tree로 표현한다. 

부모 노드를 가리키는 parent pointer tree를 사용한다.

(각 자식 노드는 부모를 가리키고, 루트 노드는 자기 자신을 가리킨다.)

 

각 트리는 집합 하나를 의미한다.

 

• Basic Version의 주요 연산

 

make-set(u)

u를 부모로서 자기 자신을 가리키게 한다.

def make-set(u):
    p[u] ← u

 

find-set(u)

입력 원소 u를 담고 있는 집합의 루트를 반환한다.

노드 u부터 재귀적으로 루트로 올라간다.

def find-set(u):
    if u is p[u]:
        return u
    else:
        return find-set(p[u])

 

union(u, v)

u를 가지는 집합과 v를 가지는 집합을 합친다.

한 집합의 루트가 다른 집합의 루트를 가리키게 한다.

def union(u, v)
    p[find-set(v)] ← find-set(u)

 

• Basic Version 분석

 

공간 복잡도

n개의 원소에 대해서 1차원 배열 p의 공간 : O(n) space

 

시간 복잡도

make-set(u) : O(1) time

find-set(u) : O(hu) time

*hu = u를 가지고 있는 집합 (트리)의 높이 

union(u, v) : hv + hu + c time

 

최악의 경우 find-set(u)은 O(n)의 시간이 걸린다.

→ degenerate 형태가 될때

 

위와 같은 최악의 경우를 피하고 더 빠르게 만들 수 있을까?

 

Disjoint는 각 트리의 높이를 줄이면 빠르게 할 수 있다.

(각 연산의 시간이 트리의 높이에 비례하기 때문)

 

1. Union by rank : 더 작은 트리를 큰 트리에 합치기

2. Path compression : find-set을 할 때 루트로 올라가면서 트리를 평평하게 만들기

 

• Union By Rank

 

아래와 같이 오른쪽 트리가 왼쪽 트리에 합쳐지면, 트리의 높이는 증가한다.

 

만약 높이가 더 작은 트리를 큰 트리에 합치면 높이 변화가 없다.

 

높이를 빠르게 파악하기 위해서 각 노드별로 rank라는 변수를 관리한다.

def union(u, v):
    ur ← find-set(u)  // ur = u를 가지는 집합의 루트 노드
    vr ← find-set(v)  // v가 속한 집합의 루트 노드를 찾음
    
    if rank[ur] > rank[vr]:  // ur의 트리가 vr의 트리보다 더 큰 경우
        p[vr] ← ur  // vr 트리가 ur의 트리로 합쳐짐
    else:
        p[ur] ← vr  // vr의 트리가 ur의 트리로 합쳐짐
    if rank[ur] == rank[vr]: // 높이가 같다면
        rank[vr] ← rank[vr] + 1 // vr의 트리의 높이를 1증가

 

• Path compression

 

find-set을 하면 루트로 거슬러 올라가는데, 올라가면서 마주치는 모든 노드들을 루트로 바로 연결시켜준다.

def find-set(u): 
    if p[u] != u:
       p[u] ← find-set(p[u])
    return p[u]

 

• Union By Rank 분석

 

Claim : union-by-rank를 하면, rank k를 가지는 루트에 의해 표현되는 한 집합의 원소 개수는 최소 2^k개 이상이다.

 

Base case : 만약 rank = 0이라면, 2⁰ = 1개의 원소가 있다.

Inductive step : 랭크 r인 트리가 최소 2^r개의 원소를 가진다고 가정하면, 랭크 r+1인 트리는 최소 2^r+1개의 원소를 가진다.

 

이를 통해 트리의 높이 ≤ rank k ≤ O(log n)이라는 사실을 도출해낼 수 있다.

 

• Path Compression 분석

 

make-set(u) : O(1) time

find-set(u) : O (log n) time

union : O (log n) time

 

make-set, find-set, union으로 구성된 m개의 연산 명령이 주어지고, 그 중 n번의 make-set 연산이 수행된다고 가정하면, 위 시퀀스의 전체 시간 복잡도는 O(mlog n)이다.

 

log n은 매우 큰 n에 대해서도 작기 때문에 이를 상수로 취급할 수 있다.

따라서 전체 연산 시퀀스는 O(m) 시간에 수행될 수 있다.

 

평군적으로 각 연산 명령은 O(1) 시간이 걸린다.

즉, path compression이 적용된 disjoint set을 할수록 트리의 높이는 짧아진다.

 

우리는 이러한 분석을 통해 Union-by-rank와 path-compression이 적용된 disjoint-set은 매우 빠른 연산을 지원한다는 사실을 알 수 있다!