알고리즘...101

트리를 이용한 집합의 처리

연결 리스트를 이용한 집합의 처리보다 효율적인 방식으로 각각의 집합을 트리로 표현하는 방법이다.

기존의 트리와는 달리 자식 노드가 부모 노드를 가리키는 방식으로 표현된다.

 

이러한 방식을 사용하는 경우 두 집합을 합칠 때 단순하게 합치려는 노드의 루트가 기존 집합의 루트를 가리키도록 하면 된다.

 

쉽게 배우는 알고리즘 상호배타적 집합의 처리 그림 7-4

 

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

- 랭크를 이용한 Union

각 노드에 자신의 서브 트리의 높이를 랭크(Rank)라는 이름으로 저장하고 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.

 

쉽게 배우는 알고리즘 상호배타적 집합의 처리 그림 7-7

 

- 경로 압축

FindSet 진행 시 중간에 만나는 모든 노드에 대해 루트를 직접 가리키도록 바꾸어 추후 FindSet을 할 때 경로의 길이를 줄이는 방법이다.

 

쉽게 배우는 알고리즘 상호배타적 집합의 처리 그림 7-8

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘