서로소인 집합들의 표현
- 각 직합을 하나의 트리로 표현
예 : 2개의 집합
disjoint한 집합 (sets) = 두 집합이 공집합이다.
집합의 각 원소들이 트리의 노드가 된다.
누가 루트이고 누가 누구의 부모이든 상관이 없다
트리의 각 노드는 자식노드가 아닌 부모 노드의 주소를 가진다. (상향식 트리)
이걸 모든 트리를 하나의 배열로 표현할 때 쓸 수 있도록 배열에 담아서 구현 할 수 있도록 가능하게 설명을 해 주신다...
Find-set(v)
: 자신이 속한 트리의 루트를 찾음
FIND-SET(x)
if x != p[x]
then p[x] <- FIND-SET(p[x])
return p[x]
o(h), h는 트리의 높이
h는 최악의 경우 o(n)
Union(u,v)
한 트리의 루트를 다른 트리의 루트의 자식 노드로 만듬
UNION(u,v)
x <- find-set (u);
y <- find-set (v);
p[x] <- y;
루트 노드를 찾은 이후에는 o(1)
하지만 루트를 찾는데 O(h)
이거는 그냥 u와 v가 속한 두 집합을 하나로 합치는 법이다 (전체 수도코드에 해당)
Weighted Union
: 두 집합을 union 할 때 작은 트리의 루트를 큰 트리의 루트의 자식으로 만듬!!!!
ㄴ 오... -.-)... 더 큰 데에 그냥 합쳐버리면 전체 트리 레벨이 증가하지도 않음!!!
이것은 각 트리의 크기 (노드의 개수)를 카운트 하고 있어야 함
Path Compression
이거로 union find의 성능을 빠르게 해줄 수 있음!
Find(g)
find를 할 때 트리를 위로 따라 올라가야 하는데,
올라가면서 자식 트리들을 다 노드의 자식으로 만드는 방식임!
find 작업을 하며, 트리 높이를 줄이는 방식 (find 한 영역에 대해서만 줄어든다)
-.-)...
댓글
댓글 쓰기