Data Structure_#12 Union-find 자료구조
Union-find 자료구조
연산
-
make-set(x): {x} => O(n)
-
find(x): x가 속한 집합의 대표값 리턴 =>O(log n)
-
union(x, y): x, y의 합집합 =>O(logn )
구현 방법
1. 원형 양방향 연결리스트 => 0(n)이 될 수 있기 때문에 비효율적
2. 트리 => O(h)
: 부모링크만 가지고 있고, root는 자기 자신을 가리키게
Height가 작아지도록 height가 큰쪽에서 작은쪽으로 union
