1. 무엇인가?
두 집합의 합을 미친듯이 빠르게 구하는 자료구조이다.2. 시간 복잡도
최악의 경우 이다. (α는 아커만 함수의 역함수)3. 어떻게 구현하는가?
트리의 노드 에 대해- {{{ find-root(x)
if u.parent == x then
return x
return find(u.parent)
- {{{ merge(x, y)
z = find-root(x)
w = find-root(y)
w.parent = z
- {{{ create(u)
u.parent = u;
연산자 정의를 이렇게 하면 트리의 균형이 안 맞아 매우 불완전한 Disjoint-set을 만들 수 있다. 최악의 경우 의 시간 복잡도가 된다.
x부터 root까지의 경로를 줄이고
- {{{ find-root(x)
if u.parent == x then
return x
return u.parent = find(u.parent) //path compression이라 부른다.
합병을 로 좀 더 효율적으로 구현하면
- {{{ merge(x, y)
z = find-root(x)
w = find-root(y)
if z.rank == w.rank then
z.rank = z.rank + 1
w.parent = z
else if z.rank > w.rank then
w.parent = z
else
z.parent = w
만큼의 시간이 걸린다.