Disjoint-Set(Union-Find) 자료구조
Disjoint-Set 자료구조는 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조입니다. Disjoint-Set
은 Union과 Find연산을 제공하며 Union-Find Set
이라 불리기도 합니다.
Union과 Find연산은 Linkedlist와 Tree로 구현될 수 있으며 Linkedlist로 구현시에 시간복잡도는 O(n)시간이지만 Tree로 구현시 최적화를 통해 최소 O(α(n))시간으로 줄일 수 있습니다.
여기서 O(α(n))은 아커만 함수(Ackermann function)의 역함수로 5이하의 값을 가지기 때문에 실질적으로 상수 시간에 연산을 수행 할 수 있습니다.
또한 Disjoint-Set
자료구조는 최소신장트리(Minimum Spanning Tree)를 찾는 Kruskal 알고리즘에 사용되기도 하는듯 알아두면 굉장히 유용하게 쓸 수 있습니다.
Kruskal 알고리즘에 대한 코드는 다음 포스트를 참고하시기 바랍니다.
지금 부터 Disjoint-Set
에 대하여 예를 통해 살펴보고 python으로 구현해보도록 하겠습니다.
Step by Step
아래의 그림에서와 같이 7개의 부분 집합이 있고 각 부분 집합은 각각의 Parent에 대한 정보를 가지고 있습니다.
초기에는 각 부분집합이 독립이므로 각 부분집합의 Parent는 자기자신이 됩니다.
(Parent[i]=i
이때 i는 각 집합을 나타냅니다.)
이제 집합 (0,1)
, (3,4)
, (5,6)
을 Union 연산해 보겠습니다.
Union에 대한 code는 다음과 같이 나타낼 수 있습니다.
def union(x, y):
# find function will be return the head of the node
x,y = find(x),find(y)
parent[y] = x
Union 연산은 Find 연산으로 두 집합의 부모를 각각 가져와 부모들을 연결시켜주면 됩니다.
다음은 Find연산에 대한 code입니다.
def find(x):
# recursively called until find the parent
if parent[x] == x: return x
else: return find(parent[x])
Find 연산은 recursive call을 통해 최종 Parent 값을 반환합니다.
계속해서 다음은 (1,2)
, (3,6)
을 Union연산 하는 경우입니다.
Union, Find 연산의 한계
위의 Union 연산은 두 집합을 한쪽 방향으로 합치기 때문에 계속해서 Union연산을 수행하다보면 아래의 그림과 같이 한쪽으로 치우쳐진 Tree(skewed tree)형태가 만들어 질 수 있습니다.
치우쳐진 Tree는 Linkedlist와 유사하게 작동하므로 O(n)의 시간복잡도를 갖습니다. 시간복잡도를 줄이려면 최적화가 필요합니다.
여기서 rank
의 개념을 도입시켜 Union 연산을 개선시킬 수 있습니다.
각각의 집합은 rank
를 갖습니다. rank
는 0의 초기값을 갖으며 rank
의 크기란 결국 tree의 높이를 나타냅니다.
def union(x, y):
# rank should be initialized with 0
x,y = find(x),find(y)
if x != y:
if rank[x] < rank[y]: parent[x] = y
else: parent[y] = x
if rank[x] == rank[y]: rank[y] += 1
Union 연산을 실행시에 Tree의 rank
즉 Tree의 높이가 낮은 노드에 subtree가 붙게됩니다.
Union연산 뿐만아니라 Find 연산 또한 개선하여 성능을 향상시킬 수 있습니다.
Find 연산은 여러번 수행 하더라도 최종 parent의 값은 변경이 되지 않는다는 성질이 있습니다.
위의 치우쳐진 Tree에서 find(6)
을 실행하였을 때를 생각해 봅시다.
find(6)
의 최종 Parent를 알고난 후에는 6의 Parent를 최종 Parent인 0으로 옮길 수 있습니다. 이렇게 하면 다음 find(6)
call했을때에 결과를 바로 return 하게 됩니다.
또한 호출경로에 있는 find(5)
, find(4)
, find(3)
, find(2)
모두 최종 Parent에 직접 연결해 줄 수 있습니다. 이는 마치 Dynamic Programming의 Memorization과 유사하다고 볼 수 있습니다.
다음은 개선된 Find 연산입니다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
위의 치우쳐진 Tree에 대하여 6에 대한 Find연산의 결과는 다음 그림과 같습니다.
이렇게 되면 후의 Find연산에 대해 한번의 참조만으로 최종 Parent를 찾을 수 있습니다.
Finally
다음은 위의 (1,2)
, (3,6)
Union연산에 이어서 (0,6)
에 대한 Union연산의 결과입니다.
find(6)
연산으로 노드6이 노드3에 붙게되고 0과 3이 Union됩니다.
위의 내용을 종합한 python code는 다음과 같습니다.
#!/usr/bin/env python3 | |
''' | |
Disjoint-set data structure (also called a union–find data structure or | |
merge–find set) is a data structure that tracks a set of elements partitioned | |
into a number of disjoint (non-overlapping) subsets. | |
''' | |
class UnionFind(object): | |
'''Implemented by tree''' | |
def __init__(self, ): | |
self.parent,self.rank = {},{} | |
def __repr__(self, ): | |
'''To make easy to show how set's are connected''' | |
sets = {} | |
for key in self.parent: | |
parent = self[key] | |
if parent not in sets: sets[parent] = [key] | |
else: sets[parent].append(key) | |
return 'Disjoint-set: ' + str(sets) | |
def get_parent(self, ): | |
return self.parent | |
def __getitem__(self, x): | |
return self.find(x) | |
def find(self, x): | |
''' | |
Path compression flattens the structure of the tree by making every node | |
point to the root whenever Find is used on it. This is valid, since each | |
element visited on the way to a root is part of the same set. | |
The resulting flatter tree speeds up future operations not only on these | |
elements, But also on those referencing them. | |
''' | |
try: | |
if self.parent[x] != x: | |
self.parent[x] = self.find(self.parent[x]) | |
except KeyError: | |
self.parent[x],self.rank[x] = x,0 | |
finally: | |
return self.parent[x] | |
def union(self, x, y): | |
''' | |
Union(x,y) uses Find to determine the roots of the trees x and y belong to. | |
If the roots are distinct, the trees are combined by attaching the root of | |
one to the root of the other. If this is done naively, such as by always | |
making x a child of y, the height of the trees can grow as O(n). | |
To prevent this union by rank is used. | |
''' | |
x,y = self[x],self[y] | |
if x != y: | |
if self.rank[x] < self.rank[y]: self.parent[x] = y | |
else: self.parent[y] = x | |
if self.rank[x] == self.rank[y]: self.rank[y] += 1 | |
if __name__ == '__main__': | |
u = UnionFind() | |
u.union(u['0'],u['1']) | |
print(u) | |
u.union(u['3'],u['4']) | |
print(u) | |
u.union(u['5'],u['6']) | |
print(u) | |
u.union(u['1'],u['2']) | |
print(u) | |
u.union(u['3'],u['6']) | |
print(u) | |
u.union(u['0'],u['6']) | |
print(u) |
Reference
Disjoint set: https://en.wikipedia.org/wiki/Disjoint-set_data_structureKruskal Algorithm: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
Minimum Spanning Tree: https://en.wikipedia.org/wiki/Minimum_spanning_tree
Dynamic Programming: https://en.wikipedia.org/wiki/Dynamic_programming
Memorization: https://en.wikipedia.org/wiki/Memoization