Handling combined exclusive sets
상호 배타적 집합의 처리
지원할 연산
- Make-Set(x) : 원소 x로만 이루어진 집합을 만든다.
- Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다.
- Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합 합집합
연결리스트(Linked list)를 이용한 처리
- 같은 집합의 원소 => 하나의 연결 리스트로 관리
- 연결 리스트의 맨 앞의 원소를 대표원소
연결 리스트로 된 두 집합
무게를 고려한 Union
- 연결 리스트로 된 두 집합을 합칠 때, 작은 집합을 큰 집합의 뒤에 붙인다.
- 대표 원소를 가리키는 포인터 갱신 작업을 최소화
- union시 시간이 가장 많이 드는 작업은 대표원소를 가리키는 포인터를 바꾸어 주는 일
- Linked list을 이용해서 표현되는 배타적 집합들을 만들면서 Weight를 고려한 Union을 사용할 때, m번의 Make-set, union,Find-Set 중 n번이 Make-Set이라면 총 수행시간은 O(m + n log n)
트리를 이용한 집합의 처리
- 같은 집합의 원소들은 하나의 tree로 관리한다
child -> Parent (일반트리와의 차이)
- tree의 root를 집합의 대표 원소로 삼는다.
root노드의 부모노드 포인터는 자신을 가리킨다.
연산의 효율 높이는 방법
Rank Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이 Rank
- 두 집합을 합칠 때, 랭크가 낮은 집합을 랭크가 높은 집합에 붙여 높이를 유지한다.
- 랭크가 동일할 때, 합치면 높이는 커짐
vs.
'Computer Science' 카테고리의 다른 글
| Computer Science - [Algorithm] (0) | 2023.01.02 |
|---|---|
| Computer Architecture - [CPU] (0) | 2022.12.18 |
| Computer Architecture - [RAM] (0) | 2022.12.18 |
| Computer Architecture - [VGA] (0) | 2022.12.17 |
| Computer Architecture - [GPU] (1) | 2022.12.17 |