이번에는 나를 가장 화나게 했던 트리를 만들어보고자 한다. 무슨 욕심으로 트리까지 만들려고 했는지는 모르겠지만, 어쨌거나 구현은 어느정도 되었으니까 다행이다. 여러 번 포기할 뻔 했다. 다른 부분보다도 특히 트리의 삭제부분에서 큰 문제를 겪었기 때문에 이번 포스트는 다소 화가 섞여있을지도 모른다.
트리(Tree)
구현해두었던 트리는 이진 탐색 트리(BST, Binary Search Tree)다. 이진 트리이므로 자식을 두 개씩 가질 수 있다. BST 의 경우, 부모 노드를 기준으로 값이 큰 것은 오른쪽에, 값이 작은 것은 왼쪽에 자리한다.
Tree
트리는 일단 기본적으로 루트 노드가 필요하기 때문에 루트 노드 만큼은 구조체 안에다가 넣어두자. 그런데 아래의 코드 에서 _searchStack 은 어디에 쓰이는지 의문이 들 수도 있는데, 그것은 아래에서 트리 순회를 하기 위해 사용할 것이다.
#include <string.h>
#include "Stack.h"
#include "Queue.h"
typedef struct __Tree__ {
size_t length;
Node* root;
/**
* @private
*/
Stack _searchStack;
} Tree;
Tree tree(size_t size, ...);
/**
* Create Binary Tree
*
* @public
*/
Tree tree(size_t length, ...) {
Tree tr = { .length = 0, .root = NULL, ._searchStack = stack(0) };
va_list ap;
va_start(ap, length);
for (int i = 0; i < length; i++) {
tr_insert(&tr, va_arg(ap, void*));
}
va_end(ap);
return tr;
}tr_*
트리를 구성하는 함수들 자체는 링크드 리스트보다 적은 편이다. 구현 해야 할 건덕지는 참 여러모로 고생스럽기는 하다만 여러 알고리즘을 풀다보면 이러한 고민은 늘 하게 되는지라 이제는 점점 적응해나가고 있다. 트리 또한 기본적으로 삽입과 삭제, 검색, 반복자를 지원하되 반복자의 경우 Inorder 트리 순회를 따른다.
void tr_insert(Tree*, void*);
void tr_erase(Tree*, void*);
void* tr_at(Tree*, void*);
void tr_clear(Tree*);
Node* tr_begin(Tree*);
Node* tr_next(Tree*, Node**);
Node* tr_end(Tree*);
Node* tr_prev(Tree*, Node**);
int tr_done(void*);tr_insert(Tree*, void*)
트리의 경우 함수를 꼼꼼히 하나하나씩 살펴봐야 한다. 가장 핵심으로 봐야 하는 코드는 조건문이라고 볼 수 있다. 큰 값은 오른쪽에, 작은 값은 왼쪽에 배정한다. 만약 트리의 루트 노드가 비어있는 상태라면 첫 번째 노드는 루트 노드로 간주하여 처리한다.
/**
* @private
*/
int __append(Node** target, Node** iter, void* element) {
if (*target == NULL) {
*target = create_node(element);
return 1;
}
else {
*iter = *target;
return 0;
}
}
/**
* Insert new node
*
* @public
*/
void tr_insert(Tree* tree, void* element) {
if (tree->root != NULL) {
Node* iter = tree->root;
while (1) {
if (iter->element < element) {
if (0 != __append(&iter->next, &iter, element)) break;
}
else {
if (0 != __append(&iter->prev, &iter, element)) break;
}
}
}
else {
tree->root = create_node(element);
}
tree->length++;
}__append() 함수는 노드가 자리해야할 위치를 찾는다. A 를 넣는다고 해보자. 예를 들어 D(root), B(root->prev), F(root->next) 일 경우, A 는 root->prev->prev 에 해당하는 위치에 있어야 한다.
__append() 함수의 구현을 잘 살펴보면 *target 이 NULL 포인터인 경우를 체크하는데, __append() 의 파라매터로 넘겨줄 때 iter->next, 또는 iter->prev 에 대해 NULL 체크를 하는 것이다. 그부분이 비어있다면 노드를 생성하고, 그렇지 않다면 iterator 의 위치를 *target 으로 바꾼 뒤 다시 반복하면 된다.
조건문에서 void* 에 대해 비교연산을 하고 있는데, 그다지 바람직하지 않을 수 있다.
tr_erase(Tree*, void*)
트리에서 값을 삭제하는 과정은 상당히 고생스럽다. 일단 값을 그냥 없애는 것이 아니라, 총 세가지의 경우의 수가 존재하는데, 자식 노드가 없는 노드를 지울 때, 자식이 하나만 있는 노드를 지울 때, 자식이 두 개있는 노드를 지울 때. 이렇게 총 세가지의 경우의 수가 있다.
자식이 없는 노드
자식이 없는 노드를 지우는 것은 간편하다. 그냥 날리면 되기 때문이다. 위의 트리에서 A 노드를 지우면 다음과 같이 그냥 날려버리면 된다.
자식이 하나만 있는 노드
자식이 하나만 있는 노드를 지울 때는 지울 노드의 왼쪽 또는 오른쪽 노드로 대체할 수 있다. 예를 들어 현재 바로 위의 트리에서 자식이 하나있는 B 를 삭제하면 다음과 같다.
자식이 두 개 있는 노드
자식이 두 개 있는 노드는 지울 수 있는 방법이 두 가지인데, 지울 노드를 기준으로 왼쪽 트리에서 가장 큰 값을 찾아서 대체하는 것과, 오른쪽 트리에서 가장 작은 값으로 대체하는 것이다. 노드를 지울 때 중요한 것은 이진 탐색 트리의 기본 원칙인 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치시켜야 한 다는 점이다. 우리는 위의 트리에서 루트 노드인 D 를 지워보자.
왼쪽 트리에서 가장 큰 값, 오른쪽 트리에서 가장 작은 값으로 대체할 수 있으므로 나타날 수 있는 트리는 두 가지이며 내가 구현한 방법은 오른쪽 트리에서 가장 값으로 대체하는 방법을 기본으로 한다.
이렇게 탄생한 코드는 다음과 같다. 트리에서 삭제할 타겟 노드를 찾는데, 현재 돌고있는 반복자의 왼쪽, 오른쪽 노드를 검사하여 타겟을 잡는다. 현재 돌고 있는 반복자 노드에 대해 검사할 경우 옳은 것은 루트 노드일 경우로만 간주한다.
/**
* Remove node with element
*
* @public
*/
void tr_erase(Tree* tree, void* element) {
void* lowest = NULL;
for (Node* iter = tr_begin(tree); 1 != tr_done(iter); iter = tr_next(tree, &iter)) {
// 반복자의 오른쪽 노드가 타겟인 경우
if (iter->next != NULL && iter->next->element == element) {
if (NULL != (lowest = (Node**)__remove(tree, &iter->next))) break;
}
// 반복자의 왼쪽 노드가 타겟인 경우
else if (iter->prev != NULL && iter->prev->element == element) {
if (NULL != (lowest = (Node**)__remove(tree, &iter->prev))) break;
}
// 반복자 자신이면서 루트 노드인 경우
else if (iter->element == element && tree->root->element == element) {
if (NULL != (lowest = (Node**)__remove(tree, &iter))) break;
}
}
if (lowest != NULL && lowest != (void*)1) {
__remove(tree, (Node**)lowest);
}
tree->length--;
}타겟에 대해서 해당 타겟노드를 기준으로 왼쪽 트리에서 가장 큰 노드 또는 오른쪽 트리에서 가장 작은 노드를 찾아야 하는데 그 역할을 해주는 것이 __remove() 함수이다. 하지만 이름에서도 보이듯 이 함수의 본래 기능은 노드를 삭제하는 기능이다.
/**
* @private
*/
void* __remove(Tree* tree, Node** target) {
// 자식 노드가 없는 경우
if ((*target)->next == NULL && (*target)->prev == NULL) {
free(*target); *target = NULL;
return (void*)1;
}
else {
if (tree->root != (*target)) {
// 자식 노드가 두 개인 경우
if (((*target)->next != NULL && (*target)->prev != NULL)) {
// 오른쪽 서브트리에서 가장 작은 노드를 얻어옴
return __lowest(target, "next");
}
// 자식 노드가 한 개인 경우
else {
Node* t = (*target)->next != NULL ? (*target)->next : (*target)->prev;
free(*target); *target = t;
return (void*)1;
}
}
// 루트 노드인 경우
else {
if (((*target)->next != NULL)) {
return __lowest(target, "next");
}
else {
return __lowest(target, "prev");
}
}
}
return NULL;
}코드를 보면 위에서 언급한 것 처럼, 자식의 개수에 따라 처리를 해주는 방법을 달리하고 있다는 사실을 알 수 있으며, 특히 자식이 두 개인 경우에는 __lowest() 함수에서 오른쪽 노드에서 가장 작은 값을 찾아서 리턴해주는 것을 볼 수 있다. 이 함수에서는 코드의 구현이 자칫 헷갈릴 수 있는데, strcmp() 함수는 두 문자열을 비교하여 같으면 0 을 반환한다. 이는 조건문에서 false 로 평가한다는 점을 유의해야 한다.
/**
* @private
*/
Node** __lowest(Node** target, const char* direction) {
// 방향이 '오른쪽' 인 경우, 오른쪽으로 한 칸 이동
Node** lowest = strcmp(direction, "next") ? &(*target)->prev : &(*target)->next;
while (1) {
// 왼쪽 서브트리에서 더 이상 큰 값이 없을 때까지 (direction -> 'prev')
if (strcmp(direction, "next")) {
if ((*lowest)->next != NULL) lowest = &(*lowest)->next;
else break;
}
// 오른쪽 서브트리에서 더 이상 작은 값이 없을 때까지 (direction -> 'next')
else {
if ((*lowest)->prev != NULL) lowest = &(*lowest)->prev;
else break;
}
}
// 삭제할 노드의 값을 타겟에 미리 복사해둔다.
(*target)->element = (*lowest)->element;
return lowest;
}tr_at(Tree*, void*)
트리에서 값을 검색하는 함수. 간단하게 값을 비교해가면서 트리를 타고 내려가면 된다. 트리의 검색 방법은 너비 우선 탐색, 깊이 우선 탐색등이 있지만 이진 탐색 트리는 말 그대로 탐색하기 좋게 트리 자체가 구성되어 있어서 그것을 굳이 구현할 필요성은 없다. 사실 한 번 구현은 했었는데 아닌 것 같아서 날리긴 했다.
/**
* Get node with element
*
* @public
*/
void* tr_at(Tree* tree, void* element) {
Node* at = tree->root;
for (int i = 0; i < tree->length; i++) {
if (at->element < element) {
at = at->next;
}
else if (at->element > element) {
at = at->prev;
}
if (at->element == element) return (Node*)at;
}
return NULL;
}tr_clear(Tree*)
트리를 비울 때는 가장 간단한 방법인 루트 노드만을 타겟으로 비우는 전략을 취했다. 위에서 배운 트리의 삭제의 경우에 따르면 루트 노드만을 삭제하는 전략을 취하면 알아서 값을 대체하며 맨 마지막에는 루트 노드 하나만 남고 자식이 없는 경우의 트리 노드의 삭제의 예를 따를 것이다.
/**
* Clear binary tree
*
* @public
*/
void tr_clear(Tree* tree) {
size_t s = tree->length;
for (int i = 0; i < s; i++) {
tr_erase(tree, tree->root->element);
}
}tr_begin(Tree*), tr_end(Tree*), tr_next(Tree*, Node**), tr_prev(Tree*, Node**), tr_done(void*)
트리의 순회를 하기 위한 반복자를 제공한다. 기본적으로 Inorder 순회를 따르며 트리의 순회의 경우에는 preorder, Inorder, postorder 가 존재하는데, 이진 탐색 트리에서 오름차순으로 정렬된 형태로 트리를 순회하려면 Inorder 순회가 필요하다. 각 오더에 대한 설명은 자세한 생략하되, Inorder 의 경우 언급을 해보자.
이와 같은 트리구조가 있을 때 각 순회에 대한 것은 다음과 같으며 순회의 순서 또한 적어놓았다. 트리에 대한 이해가 필요하다면 아래의 노드를 왜 저렇게 방문하는지를 먼저 이해할 필요가 있으니까 차근차근 그림을 그려가며 따라가보면 좋다. 이 포스트에서는 트리의 순회에 대해 자세하게 설명하지는 않고 있으므로 다른 블로그를 보면서 이해하면 더욱좋다.
전위(Pre-order; (root, prev, next)): DBACFEG
중위(In-order; (prev, root, next)): ABCDEFG
후위(Post-order; (prev, next, root)): ACBEGFD
tr_begin(), tr_end(), 그리고 tr_next(), tr_prev() 는 방향만 다를 뿐 함수의 구현은 큰 차이가 없기 때문에 처리할 수 있다. 아래의 코드의 다음에서 __begin(), __next() 함수를 알아보자.
/**
* Get first node by in order
*
* @public
*/
Node* tr_begin(Tree* tree) {
return __begin(tree, "prev");
}
/**
* Get last node by in order
*
* @public
*/
Node* tr_end(Tree* tree) {
return __begin(tree, "next");
}
/**
* Get next node by in order
*
* @public
*/
Node* tr_next(Tree* tree, Node** iter) {
return __next(tree, iter, "prev");
}
/**
* Get prev node by in order
*
* @public
*/
Node* tr_prev(Tree* tree, Node** iter) {
return __next(tree, iter, "next");
}
/**
* is Done
*
* @public
*/
int tr_done(void* iter) {
if (iter == NULL) {
return 1;
}
return 0;
}Inorder 순회를 구현하기 위해 내가 택한 것은 스택을 함께 사용하는 것이다. 각 노드를 방문할 때 스택으로 먼저 넣어놓고 빼면서 방문을 하는 것이다. 내려가면서 함께 스택을 쌓아둔다. __start() 에서는 루트 노드에 대해 스택을 넣고 __walk() 함수로 왼쪽 서브트리로 내려가면서 제일 마지막 노드(제일 작은 값을 가진 노드)로 가기까지 스택을 쌓고 맨 마지막에는 그 노드를 리턴할 것이므로 스택에게 제거한다.
__move() 함수는 반복자에게 다음 요소를 방문할 것을 요청하는데, prev 가 리프 노드에 해당하는 경우 스택에서 제거한 뒤 해주지만, 서브트리 기준으로 root 의 경우에는 next 가 있다면 next 로 이동하여 다시 prev 방향으로 타고 내려가게 된다.
/**
* @private
*/
Node* __begin(Tree* tree, const char* direction) {
Node* iter = tree->root;
st_clear(&tree->_searchStack);
st_push(&tree->_searchStack, iter);
__walk(tree, &iter, direction);
st_pop(&tree->_searchStack);
return iter;
}
/**
* @private
*/
Node* __next(Tree* tree, Node** iter, const char* direction) {
*iter = strcmp(direction, "next") ? (*iter)->next : (*iter)->prev;
if (*iter != NULL) {
st_push(&tree->_searchStack, *iter);
__walk(tree, iter, direction);
}
if (st_top(&tree->_searchStack) != NULL) {
*iter = (Node*)st_top(&tree->_searchStack)->element;
st_pop(&tree->_searchStack);
return *iter;
}
return NULL;
}__walk() 를 보면, 조건문에서 strcmp() 의 사용때문에 헷갈릴 수가 있지만, direction 이 prev 일 경우 (*iter)->prev 로 이동한다. 그 과정을 스택을 쌓으면서 이동하는 것이다.
/**
* @private
*/
void __walk(Tree* tree, Node** iter, const char* direction) {
while (1) {
// (direction -> 'prev')
if (strcmp(direction, "next")) {
if ((*iter)->prev != NULL) {
*iter = (*iter)->prev;
st_push(&tree->_searchStack, *iter);
}
else break;
}
// (direction -> 'next')
else {
if ((*iter)->next != NULL) {
*iter = (*iter)->next;
st_push(&tree->_searchStack, *iter);
}
else break;
}
}
}어떻게 사용해볼까?
드디어 끝났다. 구현만 다소 복잡할 뿐 사용법은 다른것과 별반 다르지 않다. 사실 포인터를 비교하는 부분에서 컴파일러마다 일부 다르게 처리하는 경향이 있는 것 같아서 버그가 있었는데, 일단은 그냥 넘어가기로 했다. 완벽하게 구현하는 것이 목적이 아니라, 자료구조를 스스로 구조에 맞게 구현함으로서 경험을 얻기 위해 한 것이었기 때문이다.
Tree tr = tree(1, "Hello, world!");
tr_insert(&tr, "Example");
for (Node* iter = tr_begin(&tr); 1 != tr_done(iter); iter = tr_next(&tr, &iter)) {
// Hello, world
// Example
printf("%s", (const char*) iter);
}
tr_clear(&tr);더 읽을거리
C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)
