반응형
Find - 어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별
Union - 서로 다른 두개의 집합을 하나의 집합으로 합병
=> 상향식 트리구조로 구현 하는 것이 효율적이다
상향식트리구조 : 위에서 아래로 내려오는 구조가 아닌 아래에서 위로 올라가는 구조
일반적으로 알고 있는 하향식 트리구조는 부모가 자식들만큼의 포인터 개수를 가지고 있어야 하지만
상향식은 자식이 부모를 가르키는 구조이므로 각 노드는 하나의 포인터만 가지고 있으면 된다
그러므로 어느 집합에 포함된 노드의 parent 를 계속 따라가다보면 최종 root 인 어느 집합인지를 알 수 있게 된다
(각 root 집합 명)
반응형
'알고리즘 & 자료구조 > 알고리즘&자료구조' 카테고리의 다른 글
| 다익스트라(Dijkstra) 알고리즘 ( 최단거리 찾기 알고리즘 ) (0) | 2012.10.31 |
|---|---|
| MCST=최소비용신장트리 - Kruskal 알고리즘 [모든노드최소비용연결트리-사이클없음] (0) | 2012.10.31 |
| 최소비용신장트리(MCST)와 최단거리찾기 [우선순위 검색 방법에 의해] (0) | 2012.10.31 |
| 검색 알고리즘 비교( 실행시간 비교 ) (0) | 2012.10.31 |
| Red-Black Tree 검색중 성능이 가장 좋다 (0) | 2012.10.31 |