[ 자료구조 ] 트리 - 04 . 분리 집합

[분리집합이란]

[분리집합]

교집합을 갖지 않는 집합 (원소의 모임)을 말한다 . 분리집합은 두개 이상의 집합을 일컬을때만 사용 가능한 개념이다 .

 

[분리집합과 트리]

분리집합은 집합들간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰때 유용하다 .

원소 혹은 개체가 어느 집합에 소속되어 있는가?라는 정보를 바탕으로 하는 알고리즘에 응용 가능하다.

이와같이 어떤 한 원소가 속한 집합을 알아내는 것을 집합 탐색이라고 한다 .

 

[분리집합의 표현]

[분리집합의 표현]

지금까지 본 일반 / 이진트리는 모두 부모가 자식을 가리키는 포인터를 가지고 있었다 .

분리집합은 이와 다르게 자식이 부모를 가리킨다 .

즉 , 루트 노드는 집합 그 자체이고 , 루트 노드를 포함한 트리 내의 모든 노드들은 그 집합에 소속된다 .

 

[분리집합의 구조체]

typedef struct tagDisjoinSet
{
    struct tagDisjoinSet* Parent;
    //어떠한 데이터든지 입력 할 수 있다
    void* Data;
}DisJoinSet;

자식 노드에 대한 포인터가 아닌 부모에 대한 포인터만 존재한다 .

루트 노드는 Parent가 NULL이다 .

 

[분리집합의 연산 ]

분리집합의 목적은 원소가 어느 집합에 귀속되어 있는지 아는 것에 있다 . 정렬,순차접근등은 중요하지 않다 .

그렇기에 분리집합의 연산은 합집합/집합 탐색 두 가지가 주요하다 .

 

합집합

두 집합을 더하는 연산이다 .

분리집합을 이루는 트리내의 모든 노드는 루트 노드가 나타내는 집합 안에 있다 .

합집합은 합쳐지는 집합의 부모 노드를 목적 노드로 지정해주면 끝이다 .

void DS_UnionSet(Disjointset* Set1 , Disjointset* Set1)
{
    Set2=DS_FindSet(Set2);
    Set2->Parent = Set1;
}

 

집합 탐색

원소가 속한 집합은 루트노드가 곧 자신의 집합이므로 , 집합 탐색은 원소가 속한 트리의 루트노드를 알면 된다 .

부모 포인터가 NULL (루트)일때까지 타고 올라가 부모를 반환하면 해당 집합을 반환하는 것이다 .

DisJoinSet* DS_FindSet(DisjoinSet* Set)
{
    while( Set->Parent!=NULL)
    {
    	Set=Set->Parent;
    }
    return Set;
}

 

[분리집합의 구현]

[DS.h]

#ifndef DS
#define DS

#include<stdio.h>
#include<stdlib.h>

typedef struct tagDisjoinSet
{
	struct tagDisjoinSet* Parent;
	void* Data;
}DisjoinSet;

//합집합
void DS_UnionSet(DisjoinSet * Set1,DisjoinSet* Set2);
//집합 탐색
DisjoinSet* DS_FindSet(DisjoinSet* Set);
//집합 생성
DisjoinSet* DS_CreateSet(void* NewData);
//집합 삭제
void DestroySet(DisjoinSet Set);




#endif // !DS

[DS.cpp]

#include"DS.h"

//합집합
void DS_UnionSet(DisjoinSet* Set1, DisjoinSet* Set2)
{
	Set2 = DS_FindSet(Set2);
	Set2->Parent = Set1;
}
//집합 탐색
DisjoinSet* DS_FindSet(DisjoinSet* Set)
{
	while (Set->Parent != NULL)
	{
		Set = Set->Parent;
	}
	return Set;
}
//집합 생성
DisjoinSet* DS_CreateSet(void* NewData)
{
	DisjoinSet* NewNode = (DisjoinSet*)malloc(sizeof(DisjoinSet));
	NewNode->Data = NewData;
	NewNode->Parent = NULL;
	return NewNode;
}
//집합 삭제
void DS_DestroySet(DisjoinSet* Set)
{
	free(Set);
}

[Test.cpp]

#include"DS.h"

int main(void)
{
	int a = 1, b = 2,c = 3, d = 4;
	DisjoinSet* Set1 = DS_CreateSet(&a);
	DisjoinSet* Set2 = DS_CreateSet(&b);
	DisjoinSet* Set3 = DS_CreateSet(&c);
	DisjoinSet* Set4 = DS_CreateSet(&d);

	printf("Set1 == Set2 : %d\n", DS_FindSet(Set1) == DS_FindSet(Set2));
	DS_UnionSet(Set1, Set3);
	printf("Set1==Set3 : %d\n", DS_FindSet(Set1) == DS_FindSet(Set3));

	DS_UnionSet(Set3, Set4);
	printf("Set3==Set4 : %d\n", DS_FindSet(Set3) == DS_FindSet(Set4));

	return 0;
}