[Algorithm Part 1] 1. Union-Find

이번 글에서는 (dynamic connectivity 알고리즘으로 유명한) Union-Find에 대해 살펴볼 것이다.

Dynamic Connectivity

Dynamic connectivity 문제는 동적 객체(= 관계가 변할 수 있는 객체)들이 주어졌을 때, "두 객체 연결성 판별 문제"다.

---

Union-Find는 객체 간의 연결성 정보를 가지고 있는 동시에, 2가지 연산을 지원하는 ADT다.

1. union: 두 객체 간의 연결성 부여
2. find: 두 객체 간의 연결성 질의

"연결성 소멸" 연산까지 있으면 보다 좋은 ADT가 될 수 있다.

What is API?

API(Application Programming Interface)는 생성자들과 함수들의 signature와 설명이 있다.

What is Data type & ADT?

Data type(=class) is set of values(=instance variables) and set of operations(=instance methods) on those values.

ADT(=Abstract Data Type) is data type whose representation(=implementation) is hidden from the client.

---

1. Quick-Find [eager approach]

Data Structure

정수 배열(id[])을 사용한다.

배열의 index를 객체로 표현하기 위해, 객체 이름을 정수로 대체한다.

 

id[i]는 i 객체가 속해 있는 CC(=connected component)를 의미한다.

즉, id[p] == id[q]일 때, p와 q은 같은 CC에 속해 있다.

Operations

1. find: id[p]와 id[q]가 같은지 확인한다.

2. union: id[p]인 인덱스를 모두 id[q]로 변경한다.

---

2. Quick-Union [lazy approach]

Data Structure

정수 배열(id[])을 사용한다.

배열의 index를 객체로 표현하기 위해, 객체 이름을 정수로 대체한다.

 

CC는 트리로 구성되어 있으며, id[i]는 i 객체의 부모 객체를 의미한다.

즉, root(p) == root(q)일 때 , p와 q는 같은 CC에 속해 있다. (root(p)는 p의 root 객체를 찾아주는 함수다.)

Operations

1. find: root(p)와 root(q)가 같은지 확인한다.

2. union: id[root(p)]를 id[root(q)]로 변경한다.

Observations

트리가 높아질수록, Union과 Find 비용이 N에 수렴하게 된다.

---

위 2가지 방법은 연산 비용이 비싸다. 이번에는 quick union 알고리즘 개선점에 대해 살펴볼 것이다.

2.1. Improvement1: weighting

각 트리의 노드(=객체) 수를 저장해, 작은 트리를 큰 트리에 합병한다.

이는 트리 깊이를 $\lg N$보다 작게 만들어 준다.

 

트리 깊이가 $\lg N$인 이유는 다음과 같다.

트리 깊이가 증가하는 경우는 더 큰 트리에 합병되는 경우 밖에 없기 때문이다.

즉, 트리 크기가 2배 이상 돼야, 트리 깊이가 증가한다.

Operations

Quick union과 같다.

+ 새로운 정수 배열(sz[])를 사용해 CC의 객체 총 개수를 기록한다.

---

2.2. Improvement 2: path compression 

다음 2가지 중 한 가지 방법을 사용해 root() 함수를 수정한다.

1. root 노드를 찾은 후, 경로에 있던 모든 노드를 root 노드에 연결시켜 경로를 압축시킨다.
2. root 노드를 찾는 도중에, 경로에 있는 모든 노드를 조상(grandparent) 노드와 연결시켜 경로를 압축시킨다.

Operations

Weighted quick union과 같다.

+ 위와 같이 root() 함수를 수정한다.

---

Performance

Algorithm	initialize	union	find
quick-find	N	N	1
quick-union	N	N	N
weighted-QU	N	$\lg N$	$\lg N$
weighted-QU + path compression	N	$\lg^* N$	$\lg^* N$