C言語アルゴリズム-二分探索木

二分探索木 (Binary Search Tree)

二分探索木 (Binary Search Tree)とは

二分探索木とは、全てのノードが以下の条件を満たす二分木（あるノード「node：節点」が持つ子ノードの数が最大で2個までとしたデータ構造）です。

左の子ノード(左の部分木)の値は、親ノードの値より小さい。
右の子ノード(右の部分木)の値は、親ノードの値より大きい。

つまり「左の子＜親ノード＜右の子」という関係が成り立っている探索木のことです。

二分探索木の性能

二分探索木では、１回比較を行う度に探索する対象が半分になります。したがって、探索の計算量は二分探索と同じく「O(log n)」となります。ただし、要素の追加が左部分木や右部分木の一方に偏ると、木構造ではなくリスト構造のような状態になってしまい、探索は線形探索的になります。探索効率を保つためには、データを追加する順序が昇順や降順にならないように工夫するか、平衡木と呼ばれるような木を整形する処理機能を実装する必要があります。

二分探索木のデータ構造

ルートを基点にキーの比較により、ノードの配置場所を決定していきます。

以下は「18」をルートとしたデータです。


 - {18:"eighteen"}
  - {10:"ten"}
   - { 5:"five"}
    - { 8:"eight"}
   - {15:"fifteen"}
    - {13:"thirteen"}
  - {21:"twenty one"}
   - {19:"nineteen"}
   - {32:"thirty two"}

ノードの削除が発生した場合、ノードの付け替えが発生します。

以下は「10」と「18」を削除した後のデータ構造です。


 - {19:"nineteen"}
  - {13:"thirteen"}
   - { 5:"five"}
    - { 8:"eight"}
   - {15:"fifteen"}
  - {21:"twenty one"}
   - {32:"thirty two"}

二分探索木の探索手順

探索において、ノードを訪れる順番には以下のような定番的なものがあります。

深さ優先探索
- 行きがけ順（前順：preorder）
  - ノードに立ち寄る、左部分木をなぞる、右部分木をなぞる
- 通りがけ順（間順：inorder）
  - 左部分木をなぞる、ノードに立ち寄る、右部分木をなぞる
- 帰りがけ順（後順：postorder）
  - 左部分木をなぞる、右部分木をなぞる、ノードに立ち寄る
幅優先探索

C言語による二分探索木のサンプルプログラム


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

/* ノードの構成 */
struct node {
    int key;
    char *data;
    struct node *left;
    struct node *right;
};
typedef struct node node_t;

/*!
 * @brief      文字列を領域確保してコピーする(strdup)
 * @param[out] dest  文字列のコピー先
 * @param[in]  src   文字列
 * @return     0     success
 * @return     -1    failure
 */
static int
strcpy_alloc(char **dest, const char *src)
{
    *dest = (char *)malloc(strlen(src) + 1);
    if(*dest == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        return(-1);
    }

    if(strcpy(*dest, src) == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        free(*dest);
        *dest = NULL;
        return(-1);
    }

    return(0);
}

/*!
 * @brief      新規ノードを作成する
 * @param[in]  key   登録キー
 * @param[in]  data  登録データ
 * @return     新規ノードのアドレス。失敗したらNULLを返す。
 */
static node_t *
node_new(int key, const char *data){
    node_t *node = (node_t *)malloc(sizeof(node_t));
    if(node == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        return(NULL);
    }

    if(strcpy_alloc(&(node->data), data) != 0){
        free(node);
        return(NULL);
    }
    node->key   = key;
    node->left  = NULL;
    node->right = NULL;

    return(node);
}

/*!
 * @brief       ノードを検索する
 * @param[out]  root  木構造の根
 * @param[in]   key   登録キー
 * @return      ノードのアドレスを返す。存在しない場合には、検索ノード
 *              が配置されるべきアドレス（現状でNULL）を返す。
 */
static node_t **
node_search(node_t **root, int key)
{
    node_t **node = root;

    while(*node != NULL){
        if(key == (*node)->key){      /* ノードを発見した */
            break;
        }else if(key < (*node)->key){ /* 左部分木に進む */
            node = &(*node)->left;
        }else if(key > (*node)->key){ /* 右部分木に進む */
            node = &(*node)->right;
        }
    }

    return(node);
}

/*!
 * @brief       データを挿入する
 * @param[out]  root  木構造の根
 * @param[in]   key   登録キー
 * @param[in]   data  登録データ
 * @return      0     success
 * @return      -1    failure
 */
int
bintree_insert(node_t **root, int key, const char *data)
{
    node_t **pos = root;
    node_t *new  = NULL;

    /* 挿入すべき場所を探す */
    pos = node_search(root, key);
    if(*pos != NULL){
        fprintf(stderr, "key[%d] is already exist in tree.\n", key);
        return(-1);
    }

    /* 新規ノードを追加する */
    new = node_new(key, data);
    if(new == NULL) return(-1);
    *pos = new;

    return(0);
}

/*!
 * @brief      ノードを解放する
 * @param[in]  node   削除の開始ノード
 */
static void
node_free(node_t *node)
{
    if(node->data != NULL) free(node->data);
    free(node);
}

/*!
 * @brief      木構造のデータ全てを解放する
 * @param[in]  node   削除の開始ノード
 * @note       帰りがけ順（後順：postorder）
 */
void
bintree_free(node_t *node)
{
    if(node == NULL) return;
    bintree_free(node->left);
    bintree_free(node->right);
    node_free(node);
}

/*!
 * @brief       データを検索する
 * @param[out]  root  木構造の根
 * @param[in]   key   登録キー
 * @return      登録データを返す。失敗した場合にはNULLを返す。
 * @note        行きがけ順（前順：preorder）
 */
char *
bintree_search(node_t *root, int key)
{
    node_t *node = NULL;

    node = root;
    while(node != NULL){
        if(key == node->key){
            return(node->data);
        }else if(key < node->key){ /* 左部分木に進む */
            node = node->left;
        }else if(key > node->key){ /* 右部分木に進む */
            node = node->right;
        }
    }
    return(NULL);
}

/*!
 * @brief       最小値のノードを木から取り外す
 * @param[out]  node  探索開始点のノード
 * @return      取り外したノード
 */
static node_t *
remove_minimun_node(node_t **node)
{
    node_t *min = NULL;

    /* 最小値を探す */
    while((*node)->left != NULL){
        node = &(*node)->left;
    }
    min = *node;

    /* 右部分木を以後の最小値ノードとする */
    *node = (*node)->right;
    return(min);
}

/*!
 * @brief       データを削除する
 * @param[out]  root  木構造の根
 * @param[in]   key   登録キー
 * @return      0     success
 * @return      -1    failure
 */
int
bintree_delete(node_t **root, int key)
{
    node_t *target = NULL;
    node_t **node  = NULL;

    /* 削除対象ノードを取得する */
    node = node_search(root, key);
    if(*node == NULL){ /* 対象キーのノードが存在しない場合 */
        fprintf(stderr, "key[%d] not found.\n", key);
        return(-1);
    }

    /* 削除対象ノードのポインタを付け替える */
    target = *node;
    if((target->right == NULL) && (target->left == NULL)){ /* 葉の場合 */
        *node = NULL;
    }else if(target->left == NULL){   /* 右の子ノードのみ存在する場合 */
        *node = target->right;
    }else if(target->right == NULL){  /* 左の子ノードのみ存在する場合 */
        *node = target->left;
    }else{                            /* 左右の子ノードが存在する場合 */
        /* 右部分木の最小値ノードを取得する */
        *node = remove_minimun_node(&target->right);
        (*node)->right = target->right;
        (*node)->left  = target->left;
    }

    /* ノードを削除する */
    node_free(target);

    return(0);
}

/*!
 * @brief       データ一覧を階層形式で表示する
 * @param[out]  node  表示を開始する根
 */
static void
bintree_print(node_t *node)
{
    static int print_depth = 0;

    printf("%*s", print_depth + 3, " - ");
    printf("{%2d:\"%s\"}\n", node->key, node->data);

    if(node->left != NULL){
        print_depth++;
        bintree_print(node->left);
        print_depth--;
    }
    if(node->right != NULL){
        print_depth++;
        bintree_print(node->right);
        print_depth--;
    }
}

int
main(void)
{
    node_t *root = NULL;

    /* データを登録する */
    bintree_insert(&root, 18, "eighteen");
    bintree_insert(&root, 10, "ten");
    bintree_insert(&root, 21, "twenty one");
    bintree_insert(&root,  5, "five");
    bintree_insert(&root, 32, "thirty two");
    bintree_insert(&root, 15, "fifteen");
    bintree_insert(&root, 19, "nineteen");
    bintree_insert(&root,  8, "eight");
    bintree_insert(&root, 13, "thirteen");
    bintree_print(root);

    /* データを検索する */
    printf("[SEARCH] key(21):val(%s)\n", bintree_search(root, 21));

    /* データを削除する */
    bintree_delete(&root, 18);
    bintree_delete(&root, 10);
    bintree_print(root);

    /* 二分木を解放する */
    bintree_free(root);

    return(0);
}