-
트리기초 다지기
트리를 소개합니다
트리(Tree)는 이름에서 알 수 있는 것처럼, 나무를 닮은 자료구조이다
컴퓨터 과학에서도 트리는 굉장히 활용도가 높다. 운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조로 이루어져 있다. 검색 엔진이나 데이터 베이스도 트리 자료구조에 기반해서 구현된다.
트리를 열어봅시다
트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어짐
뿌리, 가지 잎 모두 실제로는 노드이다. 이들은 트리 내의 위치에 따라 명칭만 달라짐. 루트는 트리의 가장 위에 있는 노드를 가리키고, 가지는 루트와 잎 사이에 있는 모든 노드를 일컫는 말이다. 잎 노드는 끝에 있다고 해서 단말(Terminal) 노드라고도 부른다.
B는 C와 D의 부모(Parent)이고, C와 D는 B의 자식(Children)이라고 한다. 그리고 한 부모 밑에서 태어난 C와 D는 형제(Sibling)라고 한다.
트리에서 경로는 한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여 있는 노드들의 순서이다. B노드에서 출발하여 D노드를 방문하고, D에서 출발하여 F에 도착하는데, 이때 "B,D,F"를 B에서 F까지의 경로라고 한다.
경로는 길이(Length)라는 속성을 가진다. 앞에서 얘기한 B,D,F 경로의 길이는 2가 된다.
노드의 깊이(Depth)는 루트에서 노드 사이에 해당노드까지의 경로의 길이를 뜻한다. 깊이와 비슷한 개념의 용어로 레벨(Level)과 높이(Height)가 있다.
노드의 차수(Degree)는 그 노드의 자식 노드 개수를 말하는 것이고, 트리의 차수는 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수를 말한다.
트리 표현하기
트리는 여러 가지 방법으로 표현 가능한 자료구조이다. 거꾸로 세운 나무 그림이 가장 일반적인 트리의 표현 방법이고, 이 외에도 여러 가지 방법들이 사용되고 있다.
중첩된 괄호(Nested Parenthesis)표현법은 같은 레벨의 노드들을 괄호로 같이 묶어 표현하는 방법이다. 이 방법은 읽기는 다소 어렵지만 트리를 하나의 공식처럼 표현할 수 있는 장점이 있다.
중첩된 집합(Nested Set)은 트리가 하위 트리의 집합이라는 관계를 잘표현할 수 있는 장점이 있다.
들여쓰기(Indentation)로도 표현이 가능하다. 윈도우 탐색기의 폴더 트리가 들여쓰기로 표현되어 있다.
노드 표현하기
트리 노드를 표현하는 방법에는 두 가지가 있다. 하나는 'N-링크(N-Link)' 표현법이고 다른 하나는 '왼쪽 자식-오른쪽 형제(Left Child-Right Sibling)' 표현법이다.
N-링크는 노드의 차수가 N이라면, 노드가 N개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법이다. 이 노드로 트리를 이룬다면 트리는 다음과 같은 모습이 된다.
이 표현법은 차수(자식 노드의 수)가 노드마다 달라지는 트리에는 적용하기 어렵다는 단점이 있다. 동적 할당하여 가변 배열을 만들거나 링크드 리스트를 사용하면 이 문제를 풀 수 있지만, 트리의 구조가 복잡해진다는 문제가 있다.
왼쪽 자식-오른쪽 형제 표현법은 이런 문제를 해결한다. 왼쪽 자식-오른쪽 형제 표현법은 왼쪽 자식과 오른쪽 형제에 대한 포인터를 갖고 있는 노드의 구조이다. 이 방법을 사용하면 N개의 차수를 가진 노드의 표현이 두 개의 포인터, 왼쪽 자식-오른쪽 형제만으로 가능하게 된다. 이 표현법을 이용하여 구성한 트리는 다음과 같다.
트리 구현하기
-
노드의 선언
typedef char ElementType;
typedef struct tagLCRSNode
{
struct tagLCRSNode* leftChild;
struct tagLCRSNode* rightSibling;
ElementType data;
} LCRSNode;
-
노드의 생성
LCRSNode* LCRS_createNode(ElementType data)
{
LCRSNode* newNode = (LCRSNode*)malloc(sizeof(LCRSNode));
newNode->leftChild = NULL;
newNode->rightSibling = NULL;
newNode->data = data;
return newNode;
}
-
노드의 소멸
void LCRS_destroyNode(LCRSNode* node)
{
free(node);
}
-
자식 노드 연결하기
void LCRS_addChildNode( LCRSNode* parent, LCRSNode* child)
{
if( parent->leftChild == NULL )
{
parent->leftChild = child;
}
else
{
LCRSNode* temp = parent->leftChild;
while( temp->rightSibling != NULL )
{
temp = temp->rightSibling;
}
temp->rightSibling = child;
}
}
parent의 leftChild가 NULL이 아니라면 자식 노드가 하나 이상 있다는 뜻이다. 이럴 경우 자식 노드의 rightSibling 포인터를 이용해 가장 오른쪽에 있는 자식 노드를 찾고, 찾아낸 최우측 자식 노드의 rightSibling에 child를 대입한다.
-
트리 출력하기
void LCRS_printTree(LCRSNode* node, int depth)
{
int i = 0;
// 깊이 만큼 들여쓰기
for( i = 0 ; i < depth; i++ )
{
printf(" ");
}
// 노드에 담긴 데이터를 출력
printf("%c\n", node->data);
if( node->leftChild != NULL )
{
LCRS_printTree(node->leftChild, depth+1);
}
if( node->rightSibling != NULL )
{
LCRS_printTree(node->rightSibling, depth);
}
}
트리 예제 프로그램
- 예제 LCRSTree.h
-
|
#ifndef _LCRSTREE_H__ #define _LCRSTREE_H__
#include <stdio.h> #include <stdlib.h>
typedef char ElementType; typedef struct tagLCRSNode { tagLCRSNode* leftChild; tagLCRSNode* rightSibling; ElementType data; }LCRSNode;
LCRSNode* LCRS_createNode(ElementType data); void LCRS_destroyNode(LCRSNode* node); void LCRS_destroyTree(LCRSNode* root);
void LCRS_addChildNode(LCRSNode* parent, LCRSNode* child); void LCRS_printTree(LCRSNode* node, int depth);
#endif |
- 예제 LCRSTree.c
|
#include "LCRSTree.h"
LCRSNode* LCRS_createNode(ElementType data) { LCRSNode* newNode = (LCRSNode*)malloc(sizeof(LCRSNode)); newNode->data = data; newNode->leftChild = NULL; newNode->rightSibling = NULL;
return newNode; } void LCRS_destroyNode(LCRSNode* node) { free(node); } void LCRS_destroyTree(LCRSNode* root) { // 형제가 있으면 맨 오른쪽 형제를 찾아 해제 if( root->rightSibling != NULL ) { LCRS_destroyTree(root->rightSibling); } // 자식이 있으면 맨 아래 자식을 찾아 해제 if( root->leftChild != NULL ) { LCRS_destroyTree(root->leftChild); } root->leftChild = NULL; root->rightSibling = NULL;
LCRS_destroyNode(root); }
void LCRS_addChildNode(LCRSNode* parent, LCRSNode* child) { // 자식이 없으면 바로 대입 if( parent->leftChild == NULL ) { parent->leftChild = child; } // 자식이 있으면 자식의 형제의 최우측에 대입 else { LCRSNode* temp = parent->leftChild; while( temp->rightSibling != NULL ) { temp = temp->rightSibling; } temp->rightSibling = child; }
} void LCRS_printTree(LCRSNode* node, int depth) { int i = 0; for( i = 0 ; i < depth ; i++ ) { printf(" "); } printf("%c\n", node->data);
if( node->leftChild != NULL ) { LCRS_printTree(node->leftChild, depth+1); } if( node->rightSibling != NULL ) { LCRS_printTree(node->rightSibling, depth); } } |
- 예제 main.c
|
#include "LCRSTree.h"
void main() { // 노드 생성 LCRSNode* root = LCRS_createNode('A');
LCRSNode* B = LCRS_createNode('B'); LCRSNode* C = LCRS_createNode('C'); LCRSNode* D = LCRS_createNode('D'); LCRSNode* E = LCRS_createNode('E'); LCRSNode* F = LCRS_createNode('F'); LCRSNode* G = LCRS_createNode('G'); LCRSNode* H = LCRS_createNode('H'); LCRSNode* I = LCRS_createNode('I'); LCRSNode* J = LCRS_createNode('J'); LCRSNode* K = LCRS_createNode('K');
// 트리에 노드 추가 LCRS_addChildNode(root, B); LCRS_addChildNode(B, C); LCRS_addChildNode(B, D); LCRS_addChildNode(D, E); LCRS_addChildNode(D, F); LCRS_addChildNode(root, G); LCRS_addChildNode(G, H); LCRS_addChildNode(root, I); LCRS_addChildNode(I, J); LCRS_addChildNode(J, K);
// 트리 출력 LCRS_printTree(root, 0);
// 트리 소멸 LCRS_destroyTree(root); } |
-
이진 트리
누구냐, 넌!
이진 트리(Binary Tree)는 모든 노드가 최대 2개의 자식을 가질 수 있는 트리이다
이진 트리의 여러 형태
다음 그림처럼 잎 노드를 제외한 모든 노드가 자식을 둘씩 가지고 있는 이진 트리를 포화 이진 트리(Full Binary Tree)라고 한다
완전 이진 트리(Complete Binary Tree)는 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 것이 특징이다.
높이 균형 트리(Height Balanced Tree)는 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진 트리이다.
완전 높이 균형 트리(Completely Height Balanced Tree)는 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리읜 높이가 같은 이진 트리를 말한다
이진 트리의 순회
순회(Traversal)는 트리 내의 노드들을 돌아다니는 것을 말한다
-
전위 순회
전위 순회는 아래로 내려가면서 왼쪽 하위를 방문하고 오른쪽 하위를 방문하는 방식이다
전위 순회를 이용하면 이진 트리를 중첩된 괄호로 표현할 수 있다
( A ( B ( C, D ) ), ( E ( F, G ) ) )
-
중위 순회
(1)왼쪽 하위 트리부터 시작해서 (2)루트를 거쳐 (3) 오른쪽 하위 트리를 방문하는 방법이다
중위 순회가 응용되는 대표적인 사례는 수식 트리(Expression Tree)이다
( 1 * 2 ) + ( 7 - 8 )
-
후위 순회
후위 순회의 방문 순서는 왼쪽 하위 트리, 오른쪽 하위 트리, 그리고 루트 노드 순이다.
똑같은 노드를 가지고 중위 순회를 실행해서 노드에 담긴 값을 출력하면 중위 표기식이 나오고, 후위 순회를 실행하면 후위 표기식이 나온다.
이진 트리 구현하기
-
노드의 선언
typedef char ElementType;
typedef struct tagSBTNode
{
struct tagSBTNode* left;
struct tagSBTNode* right;
ElementType data;
}SBTNode;
-
노드의 생성
SBTNode* SBT_createNode(ElementType data)
{
SBTNode* node = (SBTNode*)malloc(sizeof(SBTNode));
node->left = NULL;
node->right = NULL;
node->data = data;
return node;
}
-
노드의 소멸
void SBT_destroyNode(SBTNode* node)
{
free(node);
}
-
전위 순회를 응용한 이진 트리 출력 구현
void SBT_preoderPrintTree(SBTNode* node)
{
if( node == NULL )
return;
// 루트 노드 출력
printf(" %c", node->data);
// 왼쪽 하위 트리 출력
SBT_preoderPrintTree(node->left);
// 오른쪽 하위 트리 출력
SBT_preoderPrintTree(node->right);
}
-
중위 순회를 응용한 이진 트리 출력 구현
void SBT_inorderPrintTree(SBTNode* node)
{
if( node == NULL )
return ;
// 왼쪽 하위 트리 출력
SBT_inorderPrintTree(node->left);
// 루트 노드 출력;
printf(" %c", node->data);
//오른쪽 하위 트리 출력
SBT_inorderPrintTree(node->right);
}
-
후위 순회를 응용한 이진 트리 출력
void SBT_postorderPrintTree(SBTNode* node)
{
if( node == NULL )
return ;
// 왼쪽 하위 트리 출력
SBT_postorderPrintTree(node->left);
// 오른쪽 하위 트리 출력
SBT_postorderPrintTree(node->right);
// 루트 노드 출력
printf(" %d", node->data);
}
-
후위 순회를 으용하여 트리 소멸 함수 구현
void SBT_destroyTree(SBTNode* root)
{
if( node == NULL )
return ;
// 왼쪽 하위 트리 소멸
SBT_destroyTree(root->left);
//오른쪽 하위 트리 소멸
SBT_destroyTree(root->right);
//루트 노드 소멸
SBT_destroyNode(root);
- 예제 BinaryTree.h
-
|
#ifndef BINARY_TREE_H_ #define BINARY_TREE_H_
#include <stdio.h> #include <stdlib.h>
typedef char ElementType;
typedef struct tagSBTNode { tagSBTNode* left; tagSBTNode* right;
ElementType data; }SBTNode;
SBTNode* SBT_createNode(ElementType data); void SBT_destroyNode(SBTNode* node); void SBT_destroyTree(SBTNode* node);
void SBT_preorderPrintTree(SBTNode* node); void SBT_inorderPrintTree(SBTNode* node); void SBT_postorderPrintTree(SBTNode* node);
#endif |
- 예제 BinaryTree.c
|
#include "BinaryTree.h"
SBTNode* SBT_createNode(ElementType data) { SBTNode* node = (SBTNode*)malloc(sizeof(SBTNode));
node->left = NULL; node->right = NULL; node->data = data;
return node; } void SBT_destroyNode(SBTNode* node) { free(node); } void SBT_destroyTree(SBTNode* node) { if( node == NULL ) return ;
// 왼쪽 하위 트리 소멸 SBT_destroyTree(node->left); // 오른쪽 하위 트리 소멸 SBT_destroyTree(node->right); // 루트 노드 소멸 SBT_destroyNode(node); }
void SBT_preorderPrintTree(SBTNode* node) { if( node == NULL ) return ;
// 루트 출력 printf(" %c", node->data);
// 왼쪽 하위 출력 SBT_preorderPrintTree(node->left); // 오른쪽 하위 출력 SBT_preorderPrintTree(node->right); } void SBT_inorderPrintTree(SBTNode* node) { if( node == NULL ) return ;
// 왼쪽 하위 출력 SBT_inorderPrintTree(node->left); // 루트 노드 출력 printf(" %c", node->data); // 오른쪽 하위 노드 출력 SBT_inorderPrintTree(node->right); } void SBT_postorderPrintTree(SBTNode* node) { if( node == NULL ) return ;
// 왼쪽 하위 노드 출력 SBT_postorderPrintTree(node->left); // 오른쪽 하위 노드 출력 SBT_postorderPrintTree(node->right); // 루트 노드 출력 printf(" %c", node->data); } |
- 예제 main.c
|
#include "BinaryTree.h"
void main() { // 노드 생성 SBTNode* A = SBT_createNode('A'); SBTNode* B = SBT_createNode('B'); SBTNode* C = SBT_createNode('C'); SBTNode* D = SBT_createNode('D'); SBTNode* E = SBT_createNode('E'); SBTNode* F = SBT_createNode('F'); SBTNode* G = SBT_createNode('G');
// 트리에 추가 A->left = B; B->left = C; B->right = D;
A->right = E; E->left = F; E->right = G;
// 트리 출력 printf("Preorder\n"); SBT_preorderPrintTree(A); printf("\n");
printf("Inorder\n"); SBT_inorderPrintTree(A); printf("\n");
printf("Postorder\n"); SBT_postorderPrintTree(A); printf("\n");
SBT_destroyTree(A); } |
-
수식 트리
수식 트리를 소개합니다
수식 트리는 하나의 연산자가 두 개의 피연산자를 취한다는 가정 아래, 다음 두 가지 규칙을 가진다
- 피연산자는 잎 노드이다.
- 연산자는 루트 노드, 도는 가지 노드이다.
루트 노드와 가지 노드들은 모두 피연산자를 양쪽 자식으로 둔다. 여기에서 피연산자는 '수(Number)'일 수도 있고 또 다른 '식(Expression)'일 수도 있다
이런 방법으로 수식 트리는 가장 아래에 있는 하위 수식 트리(즉, 잎 노드)로부터 수 또는 계산 결과를 병합해 올라가는 과정을 반복하여 계산을 수행한다.
수식 트리의 구축
스택을 이용한 계산기 알고리즘에서 우리가 일반적으로 사용하는 중위 표기식은 컴퓨터가 처리하기에는 적합하지 않기 때문에 먼저 입력받은(중위 표기) 수식을 후위 표기식으로 변환한 후에 이 변환된 수식을 계산에 사용했다
후위 표기식에 기반한 수식 트리 구축 알고리즘은 여러 가지가 있지만 다음과 같은 과정으로 동작하는 알고리즘을 사용한다.
- 수식을 뒤에서부터 앞쪽으로 읽어나간다
-
수식에서 제일 마지막에 있는 토큰은 루트 노드가 된다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.
-
수식에서 읽어낸 토큰이 연산자인 경우에는 가지 노드가 되며, 이 토큰 다음에 따라오는 두 개의 토큰은 각각 오른쪽 자식 노드와 왼쪽 자식 노드가 된다. 단, 다음 토큰에도 연속해서 연산자인 경우에는 이 토큰으로부터 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰이 왼쪽 자식 노드가된다.
-
수식에서 읽어낸 토큰이 숫자이면 이 노드는 잎 노드이다.
수식 트리의 구현
-
수식 트리 구축하기
입력된 후위 표기식으로부터 수식 트리를 만듬, 매개변수로 입력된 후위 표기식을 뒤부터 읽어 토큰 하나를 분리, 읽어낸 토큰이 연산자이면 두 개의 피연산자가 뒤 따라온다는 뜻이다. 따라서 이 경우에는 방금 읽어낸 연산자 토큰을 노드에 연결하고, 바로 이어 ET_buildExpreesionTree()를 두 번 호출하여 뒤 따라오는 피 연산자 둘을 양쪽 자식으로 연결, 처음 읽은 토큰이 피연산자인 경우에는 해당 토큰을 노드에 입력하고 함수를 반환
void ET_buildExpressionTree(char* postfixExpression, ETNode** node)
{
ETNode* newNode = NULL;
int len = strlen(postfixExpression);
char token = postfixExpression[len-1];
postfixExpression[len-1] = '\0';
switch(token)
{
//연산자이면
case '+':
case '-':
case '*':
case '/':
(*node) = ET_createNode(token);
ET_buildExpressionTree(postfixExpression, &(*node)->right);
ET_buildExpressionTree(postfixExpression, &(*node)->left);
break;
//피연산자이면
default:
(*node) = ET_createNode(token);
break;
}
}
-
수식 트리 계산하기
수식 트리의 노드에 담겨 있는 토큰을 확인해서 연산자인 경우와 피연산자인 경우를 다르게 처리함, 노드에 담겨 있는 토큰이 연산자일 때는 트리의 아래 부분부터 계산 결과를 병합하여 올리도록 하기 위해, 노드의 양쪽 자식에 대해 ET_evaluate()를 재귀 호출, 재귀호출한 ET_evaluate()가 값을 반환하면 왼쪽 수식 트리의 계산 결과는 left 변수에, 오른쪽 수식 트리의 계산 결과는 right 변수에 저장됨
double ET_evaluate(ETNode* tree)
{
char temp[2];
double left = 0;
double right = 0;
double result = 0;
if( tree == NULL )
return 0;
switch( tree->data )
{
// 연산자이면
case '+':
case '-':
case '*':
case '/':
left = ET_evaluate( tree->left );
right = ET_evaluate( tree->right );
if( tree->data == '+' ) result = left + right;
else if( tree->data == '-' ) result = left - right;
else if( tree->data == '*' ) result = left * right;
else if( tree->data == '/' ) result = left / right;
break;
// 피연산자이면
default:
memset(temp, 0, sizeof(temp));
temp[0] = tree->data;
result = atof(temp);
break;
}
return result;
}
- 예제 ExpressionTree.h
|
#ifndef _EXPRESSIONTREE_H__ #define _EXPRESSIONTREE_H__
#include <stdio.h> #include <stdlib.h> #include <string.h>
typedef char ElementType; typedef struct tagETNode { tagETNode* left; tagETNode* right; ElementType data; }ETNode;
ETNode* ET_createNode(ElementType data); void ET_destroyNode(ETNode* node); void ET_destroyTree(ETNode* root);
void ET_preorderPrintTree(ETNode* node); void ET_inorderPrintTree(ETNode* node); void ET_postorderPrintTree(ETNode* node); void ET_buildExpressionTree(char* postfixExpression, ETNode** node); double ET_evaluate(ETNode* tree);
#endif |
- 예제 ExpressionTree.c
|
#include "ExpressionTree.h"
ETNode* ET_createNode(ElementType data) { ETNode* newNode = (ETNode*)malloc(sizeof(ETNode)); newNode->left = NULL; newNode->right = NULL; newNode->data = data;
return newNode; } void ET_destroyNode(ETNode* node) { free(node); } void ET_destroyTree(ETNode* root) { if( root == NULL ) { return; }
ET_destroyTree(root->left); ET_destroyTree(root->right); ET_destroyNode(root); }
void ET_preorderPrintTree(ETNode* node) { if( node == NULL ) return;
printf(" %c", node->data); ET_preorderPrintTree(node->left); ET_preorderPrintTree(node->right); } void ET_inorderPrintTree(ETNode* node) { if( node == NULL ) return;
printf("("); ET_inorderPrintTree(node->left); printf("%c", node->data); ET_inorderPrintTree(node->right); printf(")"); } void ET_postorderPrintTree(ETNode* node) { if( node == NULL ) return;
ET_postorderPrintTree(node->left); ET_postorderPrintTree(node->right); printf(" %c", node->data); } void ET_buildExpressionTree(char* postfixExpression, ETNode** node) { ETNode* newNode = NULL; int len = strlen(postfixExpression); char token = postfixExpression[len-1]; postfixExpression[len-1] = '\0';
switch(token) { // 연산자이면 case '+': case '-': case '*': case '/': (*node) = ET_createNode(token); ET_buildExpressionTree(postfixExpression, &(*node)->right); ET_buildExpressionTree(postfixExpression, &(*node)->left); break; // 피연산자이면 default: (*node) = ET_createNode(token); break; } } double ET_evaluate(ETNode* tree) { char temp[2];
double left = 0; double right = 0; double result = 0;
if( tree == NULL ) return 0;
switch( tree->data ) { // 연산자이면 case '+': case '-': case '*': case '/': left = ET_evaluate(tree->left); right = ET_evaluate(tree->right);
if( tree->data == '+' ) result = left + right; else if( tree->data == '-' ) result = left - right; else if( tree->data == '*' ) result = left * right; else if( tree->data == '/' ) result = left / right; break; // 피연산자이면 default: memset(temp, 0, sizeof(temp)); temp[0] = tree->data; result = atof(temp); break; }
return result; } |
- 예제 main.c
|
#include "ExpressionTree.h"
void main() { ETNode* root = NULL;
char postfixExpression[20] = "71*52-/"; ET_buildExpressionTree(postfixExpression, &root);
// 트리 출력 printf("preorder...\n"); ET_preorderPrintTree(root); printf("\n\n");
printf("inorder...\n"); ET_inorderPrintTree(root); printf("\n\n");
printf("postorder...\n"); ET_postorderPrintTree(root); printf("\n\n");
printf("Evaluation Result : %f\n", ET_evaluate(root));
//정리 ET_destroyTree(root); } |
-
분리 집합
분리 집합: 교집합을 갖지 않는 집합들
분리 집합(Disjoint SEt)은 서로 공통된 원소를 갖지 않는 집합들을 말함, 분리 집합은 두 개 이상의 집합을 일컫을 때만 사용할 수 있는 개념이다
따라서 분리 집합에는 '교집합(Intersection)'이 있을 수 없음. 분리 집합에는 합집합(Union)만이 있을 뿐이다.
분리 집합은 집합들 간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 유용하다. 분리 집합은 원소 또는 개체가 "어느 집합에 소속되어 있는가?"라는 정보를 바탕으로 하는 알고리즘에 응용할 수 있다.
분리 집합의 표현
분리 집합은 자식이 부모를 가리킨다.
루트 노드는 집합 그 자체이고, 루트 노드 자신을 포함한 트리 내의 모든 노드들은 그 집합에 소속된다.
-
분리 집합의 노드
typedef struct tagDisjointSet
{
struct tagDisjointSet* parent;
void* data;
} DisjointSet;
분리 집합의 연산
-
합집합
합집합(Union)은 두 집합을 더하는 연산이다.
예를 들어 위의 두 집합을 합한다고 하면, 오른쪽에 있는 집합의 루트 노드를 왼쪽에 있는 루트 노드의 자식 노드로 만들면 된다.
void DS_unionSet(DisjointSet* set1, DisjointSet* set2)
{
sest2 = DS_findSet(set2);
set2->parent = set1;
}
-
집합 탐색
집합 탐색(Find) 연산은 집합에서 원소를 찾는 것이 아니라, 원소가 속해 있는 집합을 찾는 연산이다.
DisjointSet* DS_findSet(DisjointSet* set)
{
while( set->parent != NULL )
{
set = set->parent;
}
return set;
}
분리 집합 예제 프로그램
- 예제 DisjointSet.h
-
|
#ifndef _DISJOINTSET_H__ #define _DISJOINTSET_H__
#include <stdio.h> #include <stdlib.h>
typedef struct tagDisjointSet { tagDisjointSet* parent; void* data; }DisjointSet;
void DS_unionSet(DisjointSet* set1, DisjointSet* set2); DisjointSet* DS_findSet(DisjointSet* set); DisjointSet* DS_makeSet(void* data); void DS_destroySet(DisjointSet* set);
#endif |
- 예제 DisjointSet.c
|
#include "DisjointSet.h"
void DS_unionSet(DisjointSet* set1, DisjointSet* set2) { set2 = DS_findSet(set2); set2->parent = set1; } DisjointSet* DS_findSet(DisjointSet* set) { while( set->parent != NULL ) { set = set->parent; }
return set; } DisjointSet* DS_makeSet(void* data) { DisjointSet* newNode = (DisjointSet*)malloc(sizeof(DisjointSet)); newNode->data = data; newNode->parent = NULL;
return newNode; } void DS_destroySet(DisjointSet* set) { free(set); } |
- 예제 main.c
|
#include "DisjointSet.h"
void main() { int a = 1, b = 2, c = 3, d = 4;
DisjointSet* set1 = DS_makeSet(&a); DisjointSet* set2 = DS_makeSet(&b); DisjointSet* set3 = DS_makeSet(&c); DisjointSet* set4 = DS_makeSet(&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)); } |