쉽게 배우는 알고리즘 7장 요약

7장 상호배타적 집합의 처리

1. 연결 리스트를 이용한 집합의 처리

1.1 개요
- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결한다.
- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있다.
- 대표 원소는 연결 리스트의 맨 앞에 있는 원소가 되고 tail은 마지막 원소를 가리킨다.
- 아래의 세 연산이 필요하다.
  * Make-Set(x): 원소 x로만 이루어진 집합을 만든다. 노드를 하나 만들어 대표 노드는 자신을 가리키도록 하고, 다음 원소를 가리키는 포인터는 NIL로 한다.
  * Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.
  * Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 주집합의 tail에 해당하는 노드의 다음 원소 포인터를 부집합의 대표 노드를 가리키도록 바꾸고 부집합의 모든 노드의 대표 원소 포인터는 주집합의 대표 노드를 가리키도록 바꾼다.

1.2 수행시간
- 두 집합을 합칠 때 큰 집합을 그대로 두고 작은 집합을 붙이는 것이 수행시간이 더 빠르다.
- 책 참조

2. 트리를 이용한 집합의 처리

2.1 기본 원리
- 자식 노드가 부모 노드를 가리키도록 한다.
- 두 집합을 합하는 방법: 한 집합의 루트가 다른 집합의 루트를 가리키도록 변경한다.
- 하나의 원소로 이루어진 집합 만들기: 노드를 하나 만들고 이 노드의 부모가 자신이 되도록 포인터를 만든다.

2.2 연산의 효율을 높이는 방법

2.2.1 랭크를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크라는 이름으로 저장한다.
- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.

2.2.2 경로 압축
- 기본 원리에서의 Find-Set과 같이 행하되 Find-Set(x)를 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.

2.2.3 효율성
책 참조