자료구조 : Binary Search Tree

이진 탐색 트리를 구현하기 위해, 구글에 여러 코드들을 보았지만, 데이터 타입에 상관없이 사용할 수 있는 코드는 없었다. 이에 이진 검색 트리의 동작 원리나 이해보다는, 구현을 중점으로 글을 정리해보고자 한다.

 

BST?

Binary search tree - Wikipedia

 아주 간략하게 BST(Binary Search Tree)에 대해 설명하자면, 부모 노드(Parent Node)를 기준으로 왼쪽 자식(Left Child)은 부모보다 작은 값이며 오른쪽 자식(Right Child)은 부모보다 큰 값을 가진다. 완전이진트리(Complete Binary Tree)가 될 경우 탐색의 효율성을 높일 수 있는 자료구조이다.

 

코드

header

#ifndef BST_H
#define BST_H

typedef struct node {
	struct node *left;
	struct node *right;

	char data[0];
} node_t;

typedef struct binary_tree {
	node_t *root;
	int count;
} bst_t;

bst_t *init_bst();
void free_bst(bst_t *);
void ins_bst(bst_t *, const void *, const void *, int, int (*)(const void *, const void *));
void del_bst(bst_t *, const void *, int, int (*)(const void *, const void *));
void *find_data_in_bst(bst_t *, const void *, int (*)(const void *, const void *));
void list_bst(bst_t *, void (*)(const void *));
#endif

 트리의 각 노드를 나타내는 구조체인 node_t라는 구조체만으로도 기능을 구현할 수 있다. 하지만 root 노드를 포인팅하는 bst_t 구조체를 통해, 보다 편리하게 사용할 수 있고 count를 통해 현재 노드의 수를 확인할 수 있다.

 

init

bst_t *init_bst()
{
    bst_t *bst = (bst_t *)malloc(sizeof(bst_t));

    if (bst == NULL) {
        //error logging.
        return NULL;
    }

    bst->root = NULL;
    bst->count = 0;

    return bst;
}

 노드들을 관리할 bst_t 구조체는 위와 같이 초기화 할 수 있다.

 

free

static void free_node(node_t *node)
{
    if (node != NULL) {
        free_node(node->left);
        free_node(node->right);
        free(node);
    }
}

void free_bst(bst_t *bst)
{
    if (bst->root == NULL)
        return;

    free_node(bst->root);
    free(bst);
}

 init와는 달리 free에서는 모든 노드를 순회하면서 해제하여야 한다.

 

insert

static node_t *init_node(const void *data, int data_size)
{
    node_t *node= (node_t *)malloc(sizeof(node_t) + data_size);

    if (node == NULL) {
        // error logging.
        return NULL;
    }

    node->left = node->right = NULL;
    memcpy(node->data, data, data_size);

    return node;
}

void ins_bst(bst_t *bst, const void *data, const void *key, 
            int data_size, int (*cmp_node)(const void *, const void *))
{
    node_t *parent = NULL;
    node_t *temp = NULL;
    
    temp = bst->root;

    while (temp) {
        if (cmp_node(temp->data, key) == 0)
            return;

        parent = temp;
        
        if (cmp_node(parent->data, key) > 0)
            temp = parent->left;
        else
            temp = parent->right;
    }

    node_t *new = init_node(data, data_size);

    if (parent) {
        if (cmp_node(parent->data, key) > 0)
            parent->left = new;
        else
            parent->right = new;
    } else
        bst->root = new;

    bst->count++;
}

 현재 삽입하고자 하는 값에 따라, 어떤 노드를 parent로 하여야 하는지 탐색한다. 결과에 따라 탐색한 parent의 child가 된다. 만약 parent를 찾지 못한다면, root가 없는 상태이다.

 

delete

void del_bst(bst_t *bst, const void *key, int data_size, int (*cmp_node)(const void *, const void *))
{
    node_t *parent = NULL;
    node_t *child = NULL;
    node_t *temp = NULL;
    
    if (bst->root == NULL)
        return;

    temp = bst->root;

    while (temp != NULL && cmp_node(temp->data, key) != 0) {
        parent = temp;
        temp = (cmp_node(temp->data, key) > 0) ? parent->left : parent->right;
    }

    if (temp == NULL)
        return;

    if (temp->left == NULL && temp->right == NULL) {
        if (parent) {
            if (parent->left == temp)
                parent->left = NULL;
            else
                parent->right = NULL;
        } else 
            bst->root = NULL;
    } else if (temp->left == NULL || temp->right == NULL) {
        child = (temp->left != NULL) ? temp->left : temp->right;

        if (parent) {
            if (parent->left == temp)
                parent->left = child;
            else
                parent->right = child;
        } else
            bst->root = child;
    } else {
        // succesor parent
        node_t *s_parent = temp;
        node_t *succesor = temp->right;

        while (succesor->left != NULL) {
            s_parent = succesor;
            succesor = succesor->left;
        }

        if (s_parent->left == succesor)
            s_parent->left = succesor->right;
        else
            s_parent->right = succesor->right;

        memcpy(temp->data, succesor->data, data_size);
        temp = succesor;
    }

    bst->count--;
    free(temp);
}

 delete는 다른 기능들에 비해 다소 복잡하다. 이는 1) 자식이 존재하지 않는 경우, 2) 자식이 하나 존재하는 경우, 3) 자식이 둘 존재하는 경우에 따라 처리해주어야 하기 때문이다. 즉 위의 코드는 삭제하고자 하는 노드의 위치까지 탐색 후, 자식의 존재 여부에 따라 처리하는 것이다.

 

find_data

void *find_data_in_bst(bst_t *bst, const void *key, int (*cmp_node)(const void *, const void *))
{
    node_t *cur_node = bst->root;
    int diff = 0;

    while (cur_node) {
        diff = cmp_node(cur_node->data, key);

        if (diff == 0)
            return cur_node->data;
        else if (diff > 0)
            cur_node = cur_node->left;
        else
            cur_node = cur_node->right;
    }

    return NULL;
}

 root부터 순차적으로 탐색하여, 찾고자 하는 값이 있는지 탐색한다.

 

전체코드

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

#include "bst.h"

bst_t *init_bst()
{
    bst_t *bst = (bst_t *)malloc(sizeof(bst_t));

    if (bst == NULL) {
        //error logging.
        return NULL;
    }

    bst->root = NULL;
    bst->count = 0;

    return bst;
}

static void free_node(node_t *);
void free_bst(bst_t *bst)
{
    if (bst->root == NULL)
        return;

    free_node(bst->root);
    free(bst);
}

static node_t *init_node(const void *, int);
void ins_bst(bst_t *bst, const void *data, const void *key, 
             int data_size, int (*cmp_node)(const void *, const void *))
{
    node_t *parent = NULL;
    node_t *temp = NULL;
    
    temp = bst->root;

    while (temp) {
        if (cmp_node(temp->data, key) == 0)
            return;

        parent = temp;
        
        if (cmp_node(parent->data, key) > 0)
            temp = parent->left;
        else
            temp = parent->right;
    }

    node_t *new = init_node(data, data_size);

    if (parent) {
        if (cmp_node(parent->data, key) > 0)
            parent->left = new;
        else
            parent->right = new;
    } else
        bst->root = new;

    bst->count++;
}


void del_bst(bst_t *bst, const void *key, int data_size, int (*cmp_node)(const void *, const void *))
{
    node_t *parent = NULL;
    node_t *child = NULL;
    node_t *temp = NULL;
    
    if (bst->root == NULL)
        return;

    temp = bst->root;

    while (temp != NULL && cmp_node(temp->data, key) != 0) {
        parent = temp;
        temp = (cmp_node(temp->data, key) > 0) ? parent->left : parent->right;
    }

    if (temp == NULL)
        return;

    if (temp->left == NULL && temp->right == NULL) {
        if (parent) {
            if (parent->left == temp)
                parent->left = NULL;
            else
                parent->right = NULL;
        } else 
            bst->root = NULL;
    } else if (temp->left == NULL || temp->right == NULL) {
        child = (temp->left != NULL) ? temp->left : temp->right;

        if (parent) {
            if (parent->left == temp)
                parent->left = child;
            else
                parent->right = child;
        } else
            bst->root = child;
    } else {
        // succesor parent
        node_t *s_parent = temp;
        node_t *succesor = temp->right;

        while (succesor->left != NULL) {
            s_parent = succesor;
            succesor = succesor->left;
        }

        if (s_parent->left == succesor)
            s_parent->left = succesor->right;
        else
            s_parent->right = succesor->right;

        memcpy(temp->data, succesor->data, data_size);
        temp = succesor;
    }

    bst->count--;
    free(temp);
}

void *find_data_in_bst(bst_t *bst, const void *key, int (*cmp_node)(const void *, const void *))
{
    node_t *cur_node = bst->root;
    int diff = 0;

    while (cur_node) {
        diff = cmp_node(cur_node->data, key);

        if (diff == 0)
            return cur_node->data;
        else if (diff > 0)
            cur_node = cur_node->left;
        else
            cur_node = cur_node->right;
    }

    return NULL;
}

static void search_node(node_t *, void (*)(const void *));
void list_bst(bst_t *bst, void (*print_data)(const void *))
{
    printf("cur_nodes : %d\n", bst->count);

    if (bst->root == NULL)
        return;

    search_node(bst->root, print_data);
}

/* Private functions */
static node_t *init_node(const void *data, int data_size)
{
    node_t *node= (node_t *)malloc(sizeof(node_t) + data_size);

    if (node == NULL) {
        // error logging.
        return NULL;
    }

    node->left = node->right = NULL;
    memcpy(node->data, data, data_size);

    return node;
}

static void free_node(node_t *node)
{
    if (node != NULL) {
        free_node(node->left);
        free_node(node->right);
        free(node);
    }
}

static void search_node(node_t *node, void (*print_data)(const void *))
{
    if (node != NULL) {
        search_node(node->left, print_data);
        print_data(node->data);
        search_node(node->right, print_data);
    }
}

 

테스트

#include "bst.h"
#include <string.h>
#include <stdio.h>

typedef struct {
    char name[32];
}info;

void init_info(info *t, const char *name)
{
    memset(t, 0, sizeof(info));
    memcpy(t->name, name, 32);
}

int cmp_name(const void *a, const void *b)
{
    return strcmp(((info *)a)->name, ((char *)b));
}

void print_data(const void *a)
{
    printf("%s\n", (char *)a);
}
int main()
{
    info temp;
    init_info(&temp, "TEST1");
    bst_t *bst = init_bst();
    ins_bst(bst, &temp, "TEST1", sizeof(info), cmp_name);

    init_info(&temp, "TEST2");
    ins_bst(bst, &temp, "TEST2", sizeof(info), cmp_name);
    list_bst(bst, print_data);
    printf("-----------\n");
    info *test = (info *)find_data_in_bst(bst, "TEST2", cmp_name);
    printf("%s\n", test->name);
    printf("-----------\n");
    del_bst(bst, "TEST2", sizeof(info), cmp_name);

    list_bst(bst, print_data);
    init_info(&temp, "TEST5");
    ins_bst(bst, &temp, "TEST5", sizeof(info), cmp_name);
    del_bst(bst, "TEST2", sizeof(info), cmp_name);
    del_bst(bst, "TEST5", sizeof(info), cmp_name);
    del_bst(bst, "TEST1", sizeof(info), cmp_name);

    list_bst(bst, print_data);

    free_bst(bst);
}

 

valgrind 테스트 및 실행 결과

 위와 같은 main 예제 코드를 통해, 구현한 BST의 init, insert, delete, find, search, free까지 모든 기능들이 정상 작동한다는 것을 알 수 있다. 재귀를 사용해, 보다 간단하게 기능들을 작성할 수 있다. 하지만 반복문을 사용하여 구현함으로써 BST 구현과 원리에 대해 보다 명확하고, 직관적으로 이해할 수 있었다.