2011
연재 차례
1. C언어 소개
2. 형태, 연산자, 표현
3. 제어 흐름
4. 함수와 프로그램 구조
5. 포인터와 배열
6. 구조체
7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개
트리(Tree)는 컴퓨팅에서 폭넓게 사용되는 자료구조이다. 트리 자료구조는 노드들을 계층형으로 연결하는 비선형 자료구조로서 노드들을 선형적으로 연결하는 스택과 큐와 같은 선형 자료구조와 구분된다.
트리의 분류
트리는 자식의 개수, 노드가 연결되는 순서, 트리의 높이 등에 따라서 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), Red-Black Tree, B-Tree 등으로 분류된다.
이진 탐색 트리(Binary Search Tree)는 이진 트리의 속성을 가지면서 자식 노드의 크기가 왼쪽에서 오른쪽 순서로 연결되는 것이다. 따라서, 이진 탐색 트리에서는 노드안의 데이터를 정렬된 결과로 산출할 수 있다.
Red-Black Tree는 이진 탐색 트리의 속성을 가지면서 노드들에 색상(Red, Black) 속성을 추가하여 트리의 높이가 균형 잡히도록 한다. 아래의 그림은 Red-Black Tree의 모습을 보여주고 있다.
이진 탐색 트리(Binary Search Tree)
BST(Binary Search Tree)는 정렬된 이진 트리 라고도 하며 다음과 같은 속성을 가진다. 비교하는 노드의 키를 기준으로 왼쪽 하위 트리는 키보다 작은 노드들이고 오른쪽 하위 트리는 키보다 큰 노드들이다. 왼쪽과 오른쪽 하위 트리들 또한 binary search tree 이다. BST의 가장 큰 장점은 in-order 탐색을 효율적으로 수행하여 정렬과 탐색을 효과적으로 수행할 수 있다는 것이다. 따라서 BST는 집합적인 데이터 구조체를 구현할 때 기본이 되는 자료 구조이다.
BST 검색(Searching)
BST 에서 특정 값을 검색할 때 재귀적으로 반복 처리하는 방식을 사용한다. 먼저 루트 노드에서 검색을 시작한다. 검색하고자 하는 키값이 루트 노드의 키값과 같다면 검색키가 루트 노드에 있다는 것이며 검색 성공한다. 검색 키값이 루트보다 작다면 왼쪽 서브트리로 이동하여 탐색한다. 검색 키값이 루트보다 크다면 오른쪽 서브 트리로 이동하여 탐색한다. 검색키가 발견될 때까지 이와 같은 동작을 재귀적으로 반복한다. 만약 서브트리의 포인터가 널이라면 더 이상 검색을 반복할 수 없다는 의미이고 검색키가 없다는 것이다. 이와 같은 탐색 알고리즘을 C언어로 코딩 하면 아래와 같다.
bool bst_search (int key)
{
Node *next = this->root();
while (next != NULL) {
if (key == next->value()) { //검색성공
return true;
} else if (key < next->value()) {
next = next->left(); //왼쪽서브트리로이동
} else {
next = next->right(); //오른쪽서브트리로이동
}
}
return false; //검색실패(검색키없음)
}
BST 삽입(Insertion)
BST 에 노드를 삽입하기 전에 우선 탐색(Searching)을 먼저 수행하여 삽입하고자 하는 키의 위치 노드를 찾는다. 삽입키가 루트 노드의 키보다 작다면 왼쪽 서브 트리로 이동하고 크다면 오른쪽 서브 트리로 이동하여 삽입위치를 찾아서 삽입한다. 삽입 알고리즘을 C언어로 코딩 하면 아래와 같다.
void InsertNode (Node* &treeNode, Node *newNode)
{
if (treeNode == NULL)
treeNode = newNode;
else if (newNode->key < treeNode->key)
InsertNode(treeNode->left, newNode); //왼쪽으로 이동
else
InsertNode(treeNode->right, newNode); //오른쪽으로 이동
}
-
BST의 동작들(탐색, 삽입, 삭제)을 모두 구현한 C언어 코드는 다음과 같다.
(실습 소스) bst.h
//
// Source: tree_bst.h written by Jung,JaeJoon at the www.kernel.bz
// Compiler: Standard C
// Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//
//boolean 데이터타입(gcc: #include <stdbool.h>) -
typedef enum {
true = 1,
TRUE = 1,
false = 0,
FALSE = 0
} bool;
//단어구조체정의
typedef struct
{
int key;
char *word;
} KEY_WORD;
//이진트리노드선언
typedef struct node3
{
struct node3* left;
void* data;
struct node3* right;
} NODE3;
//이진트리구조체선언-
typedef struct
{
int count; //노드수
int (*compare) (void* argu1, void* argu2);
NODE3* root;
} TREE_BST;
//이진탐색트리함수선언-
TREE_BST* bst_create (int (*compare) (void* argu1, void* argu2));
TREE_BST* bst_destroy (TREE_BST* tree);
bool bst_insert (TREE_BST* tree, void* data_in);
bool bst_delete (TREE_BST* tree, void* data_key);
void* bst_retrieve (TREE_BST* tree, void* data);
void bst_traverse (TREE_BST* tree, void (*process)(void* data));
bool bst_empty (TREE_BST* tree);
bool bst_full (TREE_BST* tree);
int bst_count (TREE_BST* tree);
static NODE3* _insert (TREE_BST* tree, NODE3* root, NODE3* node_new);
static NODE3* _delete (TREE_BST* tree, NODE3* root, void* data_key, bool* success);
static void* _retrieve (TREE_BST* tree, void* data, NODE3* root);
static void _traverse (NODE3* root, void (*process) (void* data));
static void _destroy (NODE3* root);
-
(실습 소스) bst.c
//
// Source: tree_bst.c written by Jung,JaeJoon at the www.kernel.bz
// Compiler: Standard C
// Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//
#include <stdlib.h>
//#include <malloc.h>
#include "bst.h"
//Create BST Interface
TREE_BST* bst_create (int (*compare) (void* argu1, void* argu2))
{
TREE_BST* tree;
tree = (TREE_BST*) malloc (sizeof(TREE_BST));
if (tree) {
tree->root = NULL;
tree->count = 0;
tree->compare = compare;
}
return tree;
}
//Insert BST Interface
bool bst_insert (TREE_BST* tree, void* data_in)
{
NODE3* node_new;
node_new = (NODE3*)malloc(sizeof(NODE3));
if (!node_new) return false;
node_new->left = NULL;
node_new->right = NULL;
node_new->data = data_in;
if (tree->count == 0)
tree->root = node_new;
else
_insert (tree, tree->root, node_new);
(tree->count)++;
return true;
}
//Internal Insert
NODE3* _insert (TREE_BST* tree, NODE3* root, NODE3* node_new)
{
if (!root) return node_new;
if (tree->compare(node_new->data, root->data) < 0)
{
root->left = _insert (tree, root->left, node_new); //new < root
return root;
} else {
root->right = _insert (tree, root->right, node_new); //new >= root
return root;
}
return root;
}
//Delete BST Interface
bool bst_delete (TREE_BST* tree, void* data_key)
{
bool success;
NODE3* node_new_root;
node_new_root = _delete (tree, tree->root, data_key, &success);
if (success) {
tree->root = node_new_root;
(tree->count);
if (tree->count == 0) tree->root = NULL; //tree empty
}
return success;
}
//Internal Delete
NODE3* _delete (TREE_BST* tree, NODE3* root, void* data_key, bool* success)
{
NODE3* node_del;
NODE3* node_exch;
NODE3* node_new_root;
void* data_hold;
if (!root) {
*success = false;
return NULL;
}
if (tree->compare (data_key, root->data) < 0) //data_key < root
root->left = _delete (tree, root->left, data_key, success);
else if (tree->compare (data_key, root->data) > 0) //data_key > root
root->right = _delete (tree, root->right, data_key, success);
else {
node_del = root;
if (!root->left) { //No left subtree
free (root->data);
node_new_root = root->right;
free (node_del);
*success = true;
return node_new_root;
} else {
if (!root->right) { //Only left subtree
node_new_root = root->left;
free (node_del);
*success = true;
return node_new_root;
} else { //Has two subtrees
node_exch = root->left;
while (node_exch->right) node_exch = node_exch->right; //Find largest node on left subtree
//Exchange Data
data_hold = root->data;
root->data = node_exch->data;
node_exch->data = data_hold;
root->left = _delete (tree, root->left, node_exch->data, success);
}
} //Left subtree
} //data_key = root
return root;
}
//Retrieve BST Interface
void* bst_retrieve (TREE_BST* tree, void* data)
{
if (tree->root)
return _retrieve (tree, data, tree->root);
else
return NULL;
}
//Internal Retrieve
void* _retrieve (TREE_BST* tree, void* data, NODE3* node)
{
if (node) {
if (tree->compare (data, node->data) < 0)
return _retrieve (tree, data, node->left);
else if (tree->compare (data, node->data) > 0)
return _retrieve (tree, data, node->right);
else
return node->data;
} else
return NULL;
}
//Traverse BST Interface
void bst_traverse (TREE_BST* tree, void (*process) (void* data))
{
_traverse (tree->root, process);
return;
}
//Internal Traverse
void _traverse (NODE3* root, void (*process) (void* data))
{
if (root) {
_traverse (root->left, process);
process (root->data);
_traverse (root->right, process);
}
return;
}
//Empty BST Interface
bool bst_empty (TREE_BST* tree)
{
return (tree->count == 0);
}
//Full BST Interface
bool bst_full (TREE_BST* tree)
{
NODE3* node_new;
node_new = (NODE3*)malloc(sizeof(*(tree->root)));
if (node_new) {
free (node_new);
return false;
} else
return true;
}
//BST Count Interface
int bst_count (TREE_BST* tree)
{
return (tree->count);
}
//Destroy BST Interface
TREE_BST* bst_destroy (TREE_BST* tree)
{
if (tree) _destroy (tree->root);
free (tree);
return NULL;
}
//Internal Destroy
void _destroy (NODE3* root)
{
if (root) {
_destroy (root->left);
free (root->data);
_destroy (root->right);
free (root);
}
//return;
}
Red-Black Tree
Red-Black Tree는 BST에서 파생된 것으로서 스스로 트리의 균형을 맞추어 갈 수 있는 장점을 가지고 있다. Red-Black Tree는 1972년 Rudolf Bayer에 의해서 “symmetric binary B-tree” 라는 이름으로 발명되었다. 그러나 1978년 Leonidas J. Guibas과 Robert Sedgewick의 논문에서 지금의 명칭으로 변경되었다. Red-Black Tree의 탐색, 삽입, 삭제는 O(log n) 시간으로 수행 가능하다. (여기서 n은 트리안의 노드들의 개수이다)
Red-Black Tree는 각각의 노드가 색상(red 혹은 black) 속성을 가지고 있는 binary search tree이다. 따라서, Red-Black Tree는 다음과 같은 속성을 만족해야 한다.
(1) 노드는 red 혹은 black 이어야 한다.
(2) 루트는 black 이다.
(3) 모든 리프들은 black 이다.
(4) 모든 red 노드의 자식들은 black 이다.
(5) 어떤 노드에서 자식까지의 단순 경로는 동일한 개수의 black 노드들을 포함한다.
Red-Black Tree는 노드의 삽입과 삭제 시 위의 속성을 만족하지 않으면 아래 그림과 같이 노드의 회전을 통해서 속성을 만족하는 방향으로 트리의 균형을 맞춘다. 이때 노드의 값은 a <= A <= b <= B <= c 조건을 항상 만족한다.
void rbt_left_rotate (TREE_RBT* tree, NODE3* x)
{
NODE3* y;
y = x->right;
x->right = y->left;
if (y->left) y->left->parent = x;
y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y; } else tree->root = y;
y->left = x;
x->parent = y;
}
Red-Black Tree의 Right-Rotate 알고리즘을 C언어로 코딩 하면 아래와 같다.
-
void rbt_right_rotate (TREE_RBT* tree, NODE3* x)
{
NODE3* y;
y = x->left;
x->left = y->right;
if (y->right) y->right->parent = x;
y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
} else tree->root = y;
y->right = x;
x->parent = y;
}
-
B-Tree
B- Tree는 1971년 Boeing Research Labs에서 일하던 Rudolf Bayer와 Ed McCreight에 의해서 발명되었다. 이들은 발표 당시에 B-Tree의 B의 의미를 언급하지 않았기 때문에 “Balanced”, “Boeing”, “Bayer” 등의 의미로 불려지고 있다. B-Tree는 초창기에 Disk 기억장소를 효과적으로 사용하기 위해서 만들어 졌으나, 오늘날에는 DBMS등의 다양한 컴퓨팅 분야에서 효율적인 자료구조로 널리 응용되고 있다.(B-Tree를 발표할 당시의 논문을 필자가 운영하는 사이트 http://www.kernel.bz/db/02/db0201.htm 에 원문을 번역해 두었으니 참고하기 바란다)
B-Tree는 다음과 같은 속성을 만족한다.
(1) 모든 노드는 최대 m개의 자식을 가질 수 있는 공간이 있다.
(2) 루트를 제외한 모든 노드는 적어도 m/2개의 자식을 가진다.
(3) 루트 노드는 적어도 2개의 자식을 가진다.
(4) 모든 리프들은 동일한 level에 나타난다. (리프들의 높이는 동일하다)
(5) k개의 자식을 가지고 있는 내부 노드는 k-1개의 키를 가진다.
위의 속성을 만족하는 B-Tree의 높이는 아래와 같은 범위로 계산된다.
위의 속성을 만족하도록 B-Tree에 노드를 삽입하는 모습을 아래의 그림을 통해 확인할 수 있다.
(아래에서 m=4 이다)
아래 그림은 노드를 삭제한 후 B-Tree 속성을 만족 시키는 과정이다.
아래의 소스는 C언어로 B-Tree 자료구조를 선언한 것이다.
-
//배열오더정의(트리노드안의엔트리개수)
#define ORDER 5
#define ENTRIES_MIN (((ORDER + 1) / 2) - 1)
//BTree 구조체선언-
struct node4;
typedef struct
{
void* data;
struct node4* right_son;
} ENTRY;
//BTree 노드정의
typedef struct node4
{
struct node4* first_son;
int entry_cnt;
ENTRY entries[ORDER - 1];
} NODE4;
typedef struct
{
int cnt_data; //데이터개수
int cnt_node; //노드개수
int cnt_height; //트리높이
NODE4* root;
int (*compare) (void* key1, void* key2);
} BTREE;
맺음말
트 리(Tree)는 노드들을 계층형으로 연결하는 비선형 자료구조로서 컴퓨팅에서 데이터를 관리할 때 폭넓게 활용되고 있다. 트리는 노드의 연결방식과 자식 노드의 수, 높이의 균형을 맞추는 방식에 따라서 여러 가지로 나누어 지며, 가장 대표적인 것으로 BST(Binary Search Tree), RBT(Red-Black Tree), B-Tree가 있다. BST는 노드가 왼쪽에서 오른쪽으로 크기 순서대로 연결되는 속성을 가진다. RBT는 BST의 속성을 가지면서 Rotate를 통해서 트리의 높이를 일정하게 하여 균형이 잡히도록 한다. B-Tree는 BST와 RBT속성을 모두 만족하면서 자식 노드의 개수를 2개 이상 가짐으로써 좀더 빠르게 노드의 데이터들을 관리할 수 있는 장점이 있다.
필 / 자 / 소 / 개
※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ Techworld, Inc. 무단전재 및 재배포 금지
번호 | 제목 | 작성 | 조회수 |
---|---|---|---|
394 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ② (15) | 2012-08-17 | 2078 |
393 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ① (14) | 2012-08-17 | 2337 |
392 | [C언어와 알고리즘] 해싱(Hash) 실습 (13) | 2012-08-17 | 2948 |
391 | [C언어와 알고리즘] 트리(Tree) 실습 (12) | 2012-08-17 | 4018 |
390 | [C언어와 알고리즘] 리스트(List) 실습 (11) | 2012-08-17 | 5650 |
389 | [C언어와 알고리즘] 큐(Queue) 실습 (10) | 2012-08-17 | 4917 |
388 | [C언어와 알고리즘] 스택(Stack) 실습 (9) | 2012-08-17 | 4123 |
387 | [C언어와 알고리즘] 소팅을 통한 알고리즘 분석 (8) | 2012-08-17 | 2482 |
386 | [C언어와 알고리즘] 알고리즘 소개 (7) | 2012-08-17 | 2132 |
385 | [C언어와 알고리즘] 구조체 (6) | 2012-08-17 | 3982 |
0개 댓글