Set - 집합에 랭크를 추가

< 쉽게 배우는 알고리즘 > 인용

 

1. 설명

앞에서 한 기본적인 내용을 기반으로 랭크를 추가할 것. 

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

단 하나의 노드로 이루어진 트리의 높이는 0이라고 정의한다.

루트 노드의 랭크가 해당 집합의 랭크가 된다.

아래의 [그림 1]은 집합을 나타내는 트리에서 각 노드의 랭크를 사각형 안에 표기한 것이다.

랭크를 이용한 Union에서는 두 집합을 합칠 때, 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. 

 

[그림 1]

아래의 [그림 2]에서 두 집합의 랭크는 각 각 2와 1이다.

랭크가 1인 집합을 랭크가 2인 집합에 붙였고, 두 집합의 랭크는 여전히 2이다.

이런 방식으로 합칠 때, 합집합의 랭크가 커지는 경우는 두 집합의 랭크가 동일한 경우 밖에 없다. [그림 3]을 보자.

 

[그림 2]

[그림 3]​

 

2. 알고리즘

아래는 랭크를 이용한 경우의 알고리즘들이다.

FindSet은 앞과 동일하다.

 

3. 구현

집합 구조체에 랭크를 추가

아래는 집합의 연산 함수들

메인 함수

실행 결과

헤더 파일 & 소스 파일

common.h

0.00MB

main.c

0.00MB

SetTree.c

0.00MB

SetTree.h

0.00MB