쉽게 배우는 알고리즘-08집합의 처리

가정: 상호배타적 집합만을 대상으로 하기에 교집합은 없다

  Make-Set(x): 원소 x로만 이루어진 집합을 생성 

  Find-Set(x): 원소 x를 가지고 있는 집합을 알아냄

  Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합

표현방법 : 연결리스트, 트리

 

1) 연결 리스트

-같은 집합의 원소들은 하나의 연결 리스트로 관리

-연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼음

 

[정리 1]

연결 리스트를 이용해 표현되는 배타적 집합에서 무게를 고려한 Union을 사용할 때,

m번의 Make-Set, Union, Find-Set 중

n번이 Make- Set이라면 이들의

총 수행 시간은 O(m + n log n)이다.

 

 

 

 

2)트리

-같은 집합의 원소들은 하나의 트리로 관리 

-자식 노드가 부모 노드를 가리킨다

-집합의 대표원소: 루트

 

연산의 효율을 높이는 방법

① 랭크를 이용한 union

-각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크Rank라는 이름 으로 저장한다

-두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다

② 경로 압축

- Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리 키도록 포인터를 바꾸어 준다