Union-Find (Disjoint Set)
-
공통 원소가 없는, 즉 “상호 배타적” 인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
-
tree형 으로
Union-Find를 구현하면 배열보다 빠르게 Union 연산을 수행할 수 있슴-
루트 노드 가 존재 하므로, 각 원소가 속하는 집합 번호를 바로 이 루트 노드의 원소로 정함
class Node: def __init__(self, data): self.data = data self.parent = self self.rank = 0 # height를 의미함 def make_set(x): return Node(x) def find -
Union 연산
def union(x,y): setA = find(x) # x가 들어 있는 set tree 찾기 setB = find(y) # y가 들어 있는 set tree 찾기 if setA != setB: # 가능하면 height가 높은 tree에 작은 tree를 붙이는게 최종적으로 낮은 height를 유지하기 좋음 if setA.rank > setB.rank: setB.parent = setA else if setA.rank < setB.rank: setA.parent = setB else: # setA.rank == setB.rank 일 경우 어느 쪽에다 연결해도 no problem setA.parent = setB setB.rank += 1
-
Conclusion
《Reference》