서로소 집합을 관리하는 Disjoint Set(Union Find)

이전 글에서 MST의 정의에 대해 다뤘다(2jinishappy.tistory.com/114)

이제 MST를 생성하는데 사용하는 자료구조인 Disjoint Set과 그것을 관리하는 자료구조인 Union Find에 대해 정의하고, 어떤 연산으로 MST를 만들 수 있는지 알아본다

 

Union Find의 대표적인 연산은 다음과 같다

1️⃣ makeSet(x): 단일 element(disjoint set)로 이루어진 set을 하나 생성한다.

2️⃣ find(x): x가 포함된 set을 return한다.

3️⃣ union(x, y): x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다.

 

Union Find는 vertex set을 directed tree를 이용하여 저장한다.

이 때, tree의 각 node는 해당 node의 parent 방향으로 edge를 가지고 있으며, root node의 element가 해당 set의 이름(대표)이 된다. 그리고, 각각 node의 height를 rank라고 정의한다(leaf node의 rank=0).

위와 같은 set에서 set의 root node가 A이므로 해당 subtree 전체를 set A라고 한다.

이러한 rank를 활용해서 Union Find 연산을 다시 정의할 수 있다.

 

1️⃣ makeSet(x): 단일 element(disjoint set)로 이루어진 set을 하나 생성한다.

procedure makeSet(x)	
    π(x) = x
    rank(x) = 0

이 때 π(x)는 makeSet 연산을 제외하고는 언제나 x의 parent node를 가리키도록 한다(edge 구현)

-> x = π(x)일 경우 x가 해당 set의 대표(root node)이다. 

 

2️⃣ find(x): x가 포함된 set을 return한다.

function find(x)	
    while x != π(x) : 
    	x = π(x)
    return x

x를 포함한 tree(set)의 root node가 x를 포함한 set의 대표이므로 root node에 도달할 때 까지 edge를 따라 올라간다.

3️⃣ union(x, y): x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다.

procedure union(x,y)	
    rx = find(x)
    ry = find(y)
    if rx = ry: return
    if rank(rx) > rank(ry):
    	π(ry) = rx
    else:
    	π(rx) = ry
        if rank(rx) = rank(ry):
        	rank(ry) = rank(ry) + 1
    	

 

두 set을 포함한 root node 중 rank가 작은 쪽의(tree의 height가 작은 쪽의) root node가, rank가 큰 쪽의 parent를 가리키도록 edge를 추가해준다(π 변경). 이 경우, 두 set의 root node의 기존 rank가 같지 않은 이상 union 연산을 수행한 뒤 새로운 root node의 rank는 변하지 않게 된다(같으면 1 증가).

 

출처: 충대 소프트웨어 알고리즘 강의자료

 

이 때 Union Find로 인해 생성된 Disjoint Set은 몇 가지 property를 가진다.

• 각 set에 해당하는 tree에서 어떠한 node도 해당 node의 parent보다 rank가 작다
• 각 set에 해당하는 tree에서 rank가 n인 root node는 최소 2^k개의 node를 descendant로 가진다.
  • base case: k=0 -> 2^0 = 1개
  • inductive step: rank가 k에서 k+1로 늘어나는 순간에 최소 2^k개의 node를 가진 tree 두 개가 union되므로 rank는 k+1이되고 descendant는 2^k*2 = 2^(k+1)개 이상이 된다.
• 각 set에 해당하는 tree에서 rank가 k인 node는 최대 n/2^k개 이다.
  • 위의 증명과 비슷하게 rank가 k인 tree는 2^k개의 node를 가지므로 각각의 set의 크기는 n/2^k개이다.

 

makeSet(), find(), union() 연산에 있어서, 가장 큰 시간 복잡도를 가지는 것은 find 연산이다(편향 이진 트리 형태를 가질 때).

따라서 find() 연산을 할 때 마다 지나치는 모든 node들을, 해당 set의 root node의 child로 만들어줌으로써 path compression을 해줄 수 있다.

2️⃣ find(x): find 연산을 경로 압축해준다. 이 때 지나치는 node들의 rank를 바꿔줄 필요는 없다.

function find(x)
    if x != π(x): 
    	π(x) = find(π(x))
    return π(x)

출처: https://algocoding.files.wordpress.com/2014/09/uf3_path_compression.png

 

위처럼 편향 이진 트리의 형태를 띄었던 set이 find()연산을 수행한 뒤 경로 압축 최적화가 된 것을 확인할 수 있다.

 

Time Complexity of union find:

- worst case에서 O(log n)이 걸릴 수 있지만 대부분의 경우에서는 짧은 시간이 걸린다.

- path compression을 적용할 경우, 총 m번의 union & find 연산을 수행하는 데 O(m log*n) 시간이 걸린다.

+ log*n = n에 log를 몇 번 적용하면 n이 1 이하가 되는가