본문 바로가기

2011

logo_main.gif


글: 정재준 (rgbi3307@nate.com ) / 커널연구회(www.kernel.bz)   2011-10-06


연재 차례
 1. C언어 소개
 2. 형태, 연산자, 표현
 3. 제어 흐름
 4. 함수와 프로그램 구조
 5. 포인터와 배열
 6. 구조체
 7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개

트리(Tree)는 컴퓨팅에서 폭넓게 사용되는 자료구조이다. 트리 자료구조는 노드들을 계층형으로 연결하는 비선형 자료구조로서 노드들을 선형적으로 연결하는 스택과 큐와 같은 선형 자료구조와 구분된다.

 트 리의 노드는 자식 노드들을 가질 수 있다. 트리는 아래 방향으로 성장하며 상단의 노드는 부모 노드, 하단의 노드는 자식 노드가 된다. 자식이 없는 노드를 리프(leaf) 노드라고 하고  트리에서 가장 상단에 있는 노드를 루트 노드라 한다. 따라서, 루트 노드는 부모 노드를 가지지 않는다. 트리에 대한 동작들은 보통 루트 노드에서 시작하고, 트리의 모든 노드들은 루트 노드에서부터 링크(link, pointer)로 연결된다. 높이(height)는 어떤 노드에서 리프 노드까지 연결된 경로의 길이이다. 트리의 전체 높이는 루트 노드에서 리프 노드까지의 길이이다. 내부 노드는 리프가 아닌 자식 노드들을 가진다. 외부 노드는 자식이 없는 노드이다. (외부 노드는 리프 노드이다)

트리의 분류
트리는 자식의 개수, 노드가 연결되는 순서, 트리의 높이 등에 따라서 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), Red-Black Tree, B-Tree 등으로 분류된다.
이진 트리(Binary Tree)는 [그림 2]처럼 자식의 개수가 2개 이하인 트리이다.

이진 탐색 트리(Binary Search Tree)는 이진 트리의 속성을 가지면서 자식 노드의 크기가 왼쪽에서 오른쪽 순서로 연결되는 것이다. 따라서, 이진 탐색 트리에서는 노드안의 데이터를 정렬된 결과로 산출할 수 있다.

Red-Black Tree는 이진 탐색 트리의 속성을 가지면서 노드들에 색상(Red, Black) 속성을 추가하여 트리의 높이가 균형 잡히도록 한다. 아래의 그림은 Red-Black Tree의 모습을 보여주고 있다.
B-Tree는 Red-Black Tree의 속성을 가지면서 자식의 개수가 2개 이상이 되도록 한다. B-Tree는 데이터베이스나 파일시스템 등에 많이 활용되고 있다.

위에서 예로든 트리 자료구조 동작들에 대해서 C언어 코드와 함께 이해 및 실습하도록 하자.

이진 탐색 트리(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 조건을 항상 만족한다.

 Red-Black Tree의 Left-Rotate 알고리즘을 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개 이상 가짐으로써 좀더 빠르게 노드의 데이터들을 관리할 수 있는 장점이 있다.


필 / 자 / 소 / 개

000000005173-0006.jpg
(정 재준) 필자는 학창시절 마이크로프로세서 제어 기술을 배웠고, 10여년동안 쌓아온 IT관련 개발 경험을 바탕으로 “오라클실무활용SQL튜닝(혜지원)” 책을 집필하고, “월간임베디드월드” 잡지에 다수의 글을 기고하였다.  서울대병원 전산실에서 데이터베이스 관련 일을 하면서 학창시절부터 꾸준히 해온 리눅스 연구도 계속하고 있다.  특히, 스탠포드대학교의 John L. Hennessy 교수의 저서 “Computer Organization and Design” 책을 읽고 깊은 감명을 받았으며, 컴퓨터구조와 자료구조 및 알고리즘 효율성 연구를 통한 기술서적 집필에 노력하고 있다.  또한, 온라인 상에서 커널연구회 (http://www.kernel.bz/ )라는 웹사이트를 운영하며 관련기술들을 공유하고 있다.


※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ
Techworld, Inc. 무단전재 및 재배포 금지

맨 위로
맨 위로