디스조인트-셋 자료 구조(Disjoint-Set)

디스조인트-셋 자료구조는 유니온-파인드(Union-Find) 자료구조라고도 불리며 번역하면 서로소 집합(disjoint-set), 합집합-찾기(union-find) 자료구조이다.

 

이 자료구조는 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

트리 형태의 원소들로 구성된 포레스트(forest)이다.

각각의 원소는 숫자 ID로 표현되며 랭크(rank)와 부모에 대한 포인터를 가진다.또한 다음과 같은 연산을 지원한다.

자료구조가 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되며, 각각의 원소는 하나의 트리를 나타낸다.

 

이 자료구조는 다음과 같은 3가지 연산을 지원한다.

• make-set(x): x를 ID로 가지는 원소를 추가한다.
• find(x): 원소 x가 속한 트리를 '대표'하는 값을 반환한다. 대푯값은 보통 루트원소다.
• union(x, y): 두 트리를 병합한다. 이 때, 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정한다.