Set - Basic

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

​ 

1. 개념

여기서는 각 집합을 하나의 트리로 표현하는 방법을 배울것이다.

흔히 다루는 트리와는 조금 다른 방식의 표현을 쓴다.

트리를 나타낼 때, 보통은 부모 노드가 자식 노드를 가리키도록 하지만

여기서는 자식 노드가 부모 노드를 가리키도록 한다.

아래 [그림 0 ]은 트리를 이용한 집합 표현의 예로, 8개의 원소로

이루어진 집합이 트리로 표현되었다.

임의의 노드에서 부모를 가리키는 포인터를 계속 따라가다 보면 자신이 속한 트리의 루트 노드를 만나게 된다.

이 루트 노드가 집합의 대표 노드이다.

트리를 이용한 처리에서 루트 노드의 부모 노드 포인터는

아래 [그림 0 ]과 같이 자신을 가리킨다.

[ 그림 0 ]

트리를 이용한 표현에는 두 집합을 합하는 작업은 연결 리스트 표현보다 간단하다.

두 집합 중 한 집합의 루트가 다른 집합의 루트를 가리키도록 포인터 하나만 변경해주면 된다.

아래의 내용은 트리로 표현된 두 집합을 합하는 내용이다.

 

아래와 같이 합치고자하는 두 집합이 존재한다. [그림1]참고

[ 그림1 ]

[그림 1]에는 집합{ A,B,C,H }와 집합 { D,E,F,G }를 표현하는 두 개의 트리이다.

아래의 [ 그림 2 ]는 [ 그림 1 ]의 두 집합을 하나로 합쳐 집합을 만드는 것이다.

 

위의 두 집합을 합쳐보자. [그림2]참고

[ 그림2 ]

두 집합을 합쳐서, 집합{ A, B,, C, D, E, F, G, H }를 만든 것이다.

합치기 전 두 집합의 대표 원소였던 C,E 중 C가 합쳐진 집합의 대표 원소가 되었다.

 

하나의 원소로 이루어진 집합은 노드를 하나 만들고, 이 노드의 부모가 자신이 되도록

포인터를 만들어 놓으면 된다. [ 그림 3 ]은 하나의 원소로 이루어진 집합이 만들어진 모양을 나타낸다.

[ 그림 3 ]

2. 알고리즘

아래는 집합을 표현하는 구조체

노드 x의 부모 노드는 p[x]이다.

3. 구현

메인 함수

프로그램 실행 결과

헤더 파일 & 소스 파일

common.h

0.00MB

main.c

0.00MB

SetTree.c

0.00MB

SetTree.h

0.00MB