-
Disjoint Sets자료구조 2019. 9. 2. 18:55
n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조
n개의 원소가 n개의 set으로 초기화됨 (MakeSet())
Tree를 사용하는 것이 효율적.
Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j)
Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n))
void simpleUnion(int i, int j) {parent[i] = j;}
효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침
두 set의 height가 같으면 union된 set의 height 증가
Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포함된 set의 root를 반환) (O(nlogn) 평균 O(n-1))
int simpleFind(int i) { while (parent[i] >= 0) i = parent[i]; // move up the tree return i; }
Find시 최종적으로 찾아진 root를 자신의 부모로 만들어 경로를 압축할 수 있음 (path compression)
int Find(int i) { return parents[i] = Find(parents[i]) }
Kruskal 알고리즘 구현 시 사용됨
'자료구조' 카테고리의 다른 글
Hash Table (0) 2019.09.04 Graph (0) 2019.09.03 Selection Tree (0) 2019.09.02 Binary Search Tree (0) 2019.09.02 Priority Queue (0) 2019.09.02