二分探索木 | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第8章

アルゴリズムとデータ構造編【データ構造】 第8章 二分探索木

先頭へ戻る

この章の概要

この章の概要です。


関連する話題が、以下のページにあります。

二分探索木

前章で二分木を紹介しました。しかし、前章の範疇では、結局のところ何に使えばいいのかよく分からないと思います。

この章で紹介するのは、二分探索木です。二分探索木は、二分木に対して、あるルールを適用することによって、データの探索効率を向上させたデータ構造です。

あるルールというのは、「左の子の値<親の値<右の子の値」という条件を持たせるというものです。これだと同じ値を持てないことになりますが、2つの不等号のうち片方だけなら=を付け加えれば対応することはできます。このルールを満たした木は、次のような感じになります。

二分探索木

このようなルールを満たしていれば、特定のデータを探すには、次のように行えば良いことになります。

  1. 根を調べる。一致していれば探索完了
  2. 根の値と探したい値を比較して、探したい値の方が小さければ左の子を、大きければ右の子を調べる
  3. 葉に行き着くまで上記を繰り返す。葉に行き着いても一致しなければ、探したい値は木の中に存在しない

先ほどのイメージ図を見ながら考えると、例えば、最初に根を調べたとき、探したい値の方が小さかったとしたら、根の右部分木は一切調べる必要がありません。これは、1回比較を行うたびに、探索する対象が半分になることを意味しています

この作業を繰り返すので、探索する対象はどんどん半分に減っていきます。これはつまり、二分探索【探索】第4章)と同じことが起きている訳です。したがって、二分探索木の探索の計算量は、二分探索と同じく O(log n) となります

ところが、二分探索木では、二分探索と同じように事が運ぶことが保証されている訳ではありません。なぜなら、次のような二分探索木もあり得るからです。

悪い状態の二分探索木

この場合でも、左の子が存在しないだけであって、「左の子の値<親の値<右の子の値」というルールは確かに満たしていますから、どう見ても木には見えませんが、これでも二分探索木だと言えるのです。

このように二分探索木は、どのような形になっているかによって、性能に大きな変化が表れてきます。性能を保つためにはできるだけ、葉の高さが揃った綺麗な形の木になるように工夫することが必要です。この件については、後で再び取り上げます

プログラム例

では、実際のプログラムを見ていきましょう。

/* main.c */

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


/* コマンド */
enum Cmd_tag {
    CMD_ADD,
    CMD_REMOVE,
    CMD_SEARCH,
    CMD_PRINT,
    CMD_EXIT,

    CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

/* コマンドの戻り値 */
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};

/* コマンド文字列 */
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "a", "add" },
    { "r", "remove" },
    { "s", "search" },
    { "p", "print" },
    { "e", "exit" }
};


static void create_bstree(void);
static void delete_bstree(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_add(void);
static enum CmdRetValue_tag cmd_remove(void);
static enum CmdRetValue_tag cmd_search(void);
static enum CmdRetValue_tag cmd_print(void);
static enum CmdRetValue_tag cmd_exit(void);
static int add_elem(int value);
static int remove_elem(int value);
static int search_elem(int value);
static void print_elem(void);
static void get_line(char* buf, size_t size);


/* コマンド実行関数 */
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_add,
    cmd_remove,
    cmd_search,
    cmd_print,
    cmd_exit
};


static BSearchTree gBSTree;


int main(void)
{
    create_bstree();

    while( 1 ){
        print_explain();

        if( get_cmd() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    delete_bstree();

    return 0;
}

/* 二分探索木を作成 */
void create_bstree(void)
{
    gBSTree = bsearch_tree_create( 0 );
}

/* 二分探索木を削除 */
void delete_bstree(void)
{
    bsearch_tree_delete( gBSTree );
    gBSTree = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力して下さい。" );
    printf( " 二分探索木に要素を追加する: %s (%s)\n", CMD_STR[CMD_ADD][CMD_STR_SHORT], CMD_STR[CMD_ADD][CMD_STR_LONG] );
    printf( " 二分探索木から要素を取り除く: %s (%s)\n", CMD_STR[CMD_REMOVE][CMD_STR_SHORT], CMD_STR[CMD_REMOVE][CMD_STR_LONG] );
    printf( " 二分探索木から要素を探す: %s (%s)\n", CMD_STR[CMD_SEARCH][CMD_STR_SHORT], CMD_STR[CMD_SEARCH][CMD_STR_LONG] );
    printf( " 二分探索木の内容を表示する: %s (%s)\n", CMD_STR[CMD_PRINT][CMD_STR_SHORT], CMD_STR[CMD_PRINT][CMD_STR_LONG] );
    printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    enum Cmd_tag cmd;
    int i;

    get_line( buf, sizeof(buf) );

    cmd = CMD_NUM;
    for( i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[i]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    addコマンドの実行
*/
enum CmdRetValue_tag cmd_add(void)
{
    char buf[40];
    int value;

    puts( "二分探索木に入れる数値データを入力して下さい。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    if( add_elem( value ) ){
        printf( "%d を追加しました。\n", value );
    }
    else{
        printf( "%d の追加に失敗しました。\n", value );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    removeコマンドの実行
*/
enum CmdRetValue_tag cmd_remove(void)
{
    char buf[40];
    int value;

    puts( "二分探索木から取り除く数値データを入力して下さい。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );


    if( remove_elem(value) ){
        printf( "%d を取り除きました。\n", value );
    }
    else{
        printf( "%d を取り除くことに失敗しました。\n", value );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    searchコマンドの実行
*/
enum CmdRetValue_tag cmd_search(void)
{
    char buf[40];
    int value;

    puts( "二分探索木から探し出す数値データを入力して下さい。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );


    if( search_elem(value) ){
        printf( "%d が見つかりました。\n", value );
    }
    else{
        printf( "%d は見つかりませんでした。\n", value );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    printコマンドの実行
*/
enum CmdRetValue_tag cmd_print(void)
{
    print_elem();

    return CMD_RET_VALUE_CONTINUE;
}

/*
    exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
    puts( "終了します。" );

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を入れる
*/
int add_elem(int value)
{
    return bsearch_tree_add( &gBSTree, value );
}

/*
    要素を取り出す
*/
int remove_elem(int value)
{
    return bsearch_tree_remove( &gBSTree, value );
}

/*
    要素を探す
*/
int search_elem(int value)
{
    return bsearch_tree_search(gBSTree, value) != NULL;
}

/*
    木の中身を出力
*/
void print_elem(void)
{
    bsearch_tree_print( gBSTree );
}

/*
    標準入力から1行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取ることができる最大文字数は size - 1 文字。

    引数:
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値:
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    /* 末尾に改行文字があれば削除する */
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}
/* bsearch_tree.c */

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


/* 二分探索木の節 */
struct BSNode_tag {
    int                   value;
    struct BSNode_tag*    left;
    struct BSNode_tag*    right;
};



struct BSNode_tag* delete_min(struct BSNode_tag** p);



/* 二分探索木を作る */
BSearchTree bsearch_tree_create(int value)
{
    BSearchTree tree = malloc(sizeof(struct BSNode_tag));
    tree->value = value;
    tree->left = NULL;
    tree->right = NULL;

    return tree;
}

/* 二分探索木を削除する */
void bsearch_tree_delete(BSearchTree tree)
{
    if( tree == NULL ){
        return;
    }

    bsearch_tree_delete( tree->left );
    bsearch_tree_delete( tree->right );
    free( tree );
}

/* 二分探索木に要素を追加する */
int bsearch_tree_add(BSearchTree* tree, int value)
{
    BSearchTree* p = tree;

    while( *p != NULL ){
        if( (*p)->value == value ){
            return 0;
        }
        else if( (*p)->value < value ){
            p = &(*p)->right;
        }
        else{
            p = &(*p)->left;
        }
    }

    *p = bsearch_tree_create(value);

    return 1;
}

/* 二分探索木から要素を取り除く */
int bsearch_tree_remove(BSearchTree* tree, int value)
{
    BSearchTree* p = tree;
    BSearchTree x;

    while( *p != NULL ){
        x = *p;

        if( x->value == value ){
            if( x->left == NULL && x->right == NULL ){
                /* 取り除かれる要素が葉であれば、子がいないので問題なく削除できる */
                *p = NULL;
            }
            else if( x->left == NULL ){
                /* 右の子があるなら、取り除かれる要素の位置へ移動させる */
                *p = x->right;
            }
            else if( x->right == NULL ){
                /* 左の子があるなら、取り除かれる要素の位置へ移動させる */
                *p = x->left;
            }
            else{
                /* 左右に子があるなら、左部分木の中で一番大きい値を持った要素か、
                   右部分木の中で一番小さい値を持った要素のいずれかを、
                   取り除かれる要素の位置へ移動させる。
                   ここでは、右部分木の中で一番小さい値を移動させている。
                */
                *p = delete_min( &x->right );
                (*p)->left = x->left;
                (*p)->right = x->right;
            }

            free( x );
            return 1;
        }
        else if( x->value < value ){
            p = &x->right;
        }
        else{
            p = &x->left;
        }
    }

    return 0;
}

/* 二分探索木から要素を探す */
BSearchTree bsearch_tree_search(BSearchTree tree, int value)
{
    BSearchTree p = tree;

    while( p != NULL ){
        if( p->value == value ){
            return p;
        }
        else if( p->value < value ){
            p = p->right;
        }
        else{
            p = p->left;
        }
    }

    return NULL;
}

/* 二分探索木の内容を出力する */
void bsearch_tree_print(BSearchTree tree)
{
    char left[16];
    char right[16];

    if( tree == NULL ){
        return;
    }

    if( tree->left == NULL ){
        strcpy( left, "NULL" );
    }
    else{
        sprintf( left, "%d", tree->left->value );
    }
    if( tree->right == NULL ){
        strcpy( right, "NULL" );
    }
    else{
        sprintf( right, "%d", tree->right->value );
    }
    printf( "%s <-- %d --> %s\n", left, tree->value, right );


    bsearch_tree_print( tree->left );
    bsearch_tree_print( tree->right );
}


/* 最小の値をもつ節を削除する */
struct BSNode_tag* delete_min(struct BSNode_tag** p)
{
    struct BSNode_tag* x;


    /* 最小の値を持った要素は、必ず左の子を辿った先にある */
    while( (*p)->left != NULL ){
        p = &(*p)->left;
    }

    x = *p;            /* x が削除される要素 */
    *p = (*p)->right;  /* x の右の子を x の位置へ移動させる (right が NULL でも構わない) */

    return x;
}
/* bsearch_tree.h */

#ifndef BSEARCH_TREE_H
#define BSEARCH_TREE_H


/* 二分探索木型 */
typedef struct BSNode_tag* BSearchTree;


/*
    二分探索木を作る

    引数:
        value:	根に格納する値。

    戻り値:
        作成された二分探索木。
        使い終わったら、bsearch_tree_delete関数に渡して削除する。
*/
BSearchTree bsearch_tree_create(int value);

/*
    二分探索木を削除する

    引数:
        tree:	二分探索木
*/
void bsearch_tree_delete(BSearchTree tree);

/*
    二分探索木に要素を追加する

    引数:
        tree:	二分探索木へのポインタ
        value:	追加する要素の値
    戻り値:
        成功したら 0以外、失敗したら 0 を返す。
*/
int bsearch_tree_add(BSearchTree* tree, int value);

/*
    二分探索木から要素を取り除く

    引数:
        tree:	二分探索木へのポインタ
        value:	取り除く要素の値
    戻り値:
        成功したら 0以外、失敗したら 0 を返す。
*/
int bsearch_tree_remove(BSearchTree* tree, int value);

/*
    二分探索木から要素を探す

    引数:
        tree:	二分探索木
        value:	探し出す要素の値
    戻り値:
        要素が見つかれば、その要素へのポインタ。
        見つからなければ、NULL を返す。
*/
BSearchTree bsearch_tree_search(BSearchTree tree, int value);

/*
    二分探索木の内容を出力する

    引数:
        tree:	二分探索木
*/
void bsearch_tree_print(BSearchTree tree);


#endif

初期化

まず、bsearch_tree_create関数を使って、二分探索木の作成を行います。この関数には、根となる節の持つ値を渡すようになっており、関数内部では根を生成しています。

この辺は方針次第で、根を作らず「空の二分探索木」という状態にしても良いのですが、表現が難しくなるので、ここでは根だけは作ってしまうことにしました。

要素の追加

要素の追加は、bsearch_tree_add関数内で行われています。

「左の子の値<親の値<右の子の値」というルールを満たすことが必要なので、まずは適切な追加位置を探すことになります。

そこでまず、根から調べ始めます。追加しようとする値の方が小さければ左の子へ進み、大きければ右の子へ進みます。もし、追加しようとする値と同じ値だった場合には、失敗としています。この操作を繰り返していき、進む先が無くなったら、その位置が適切な追加位置だということになります。

なお、すでに存在している値の重複を許可していないのは、今回のサンプルプログラムの方針だというだけのことであって、重複を許可するような木を作ることは可能です。これは練習問題とします。

要素の削除

要素の削除は、bsearch_tree_remove関数で行っています。

二分探索木の操作の中では、削除が最も難しい作業になります。これは、葉以外の節を削除する場合には、その子を木の中に残してやらないといけないからです。もし、子が1個しかないのであれば話は比較的簡単で、その子を、削除された要素があった位置へ移動させるだけで済みます。

難しいのは、子が2個ある場合です。この場合、削除された要素があった位置には、左部分木と右部分木のすべての要素の中から、適切な1つの節を選び出して移動させる必要があります。具体的には、次のいずれかを選択します。

サンプルプログラムでは、後者を選択しています。

このいずれかの方法を使えば、「左の子の値<親の値<右の子の値」が崩れることなく、要素を削除することができます。どういうことかと言うと、削除された要素があった位置に移動してくる節は、その左部分木のどの節よりも大きい値を持ち、右部分木のどの節よりも小さい値を持っていなければならない訳です。

この2つの条件を満たすには、左部分木の中(削除された要素の値よりも必ず小さいはず)で最も大きい値を持った節か、右部分木(削除された要素の値よりも必ず大きいはず)で最も小さい値を持った節のいずれかを選び出せばいいということになります。

要素の探索

要素の探索は、bsearch_tree_search関数で行っています。

ここまで理解できていれば、この関数はそれほど難しくありません。根からはじめて、目的の値との大小関係に応じて、左の子か右の子を辿ることを繰り返していけばいいだけです。葉まで行き着いても目的の値と一致しなければ、目的の値は木の中に存在しません。

要素の出力

要素の出力は、bsearch_tree_print関数で行っています。

木の中身を綺麗に整形して出力するのは、それなりに大変です。この関数はあくまで一例として示しただけです。そもそもデバッグ向けの関数だと言えますから、好きなように実装すればいいと思います。


ここで、要素の追加と削除が、どの程度の計算量になるかは、二分探索木の重要な評価ポイントとなります。結論として、二分探索木が、葉の高さがほぼ一定な綺麗な形の木になっていれば、追加も削除も探索も、O(log n) の性能が出ます。しかし、すべての節が、根の左部分木(または右部分木)に集中してしまう悪い状態のときには、O(n) まで悪化します


効率が落ちる例

二分探索木の効率を維持するためには、どの葉も同じような高さにあることが重要です

前章で、完全二分木という状態に触れました。これは、どの葉も同じ高さにある二分木のことですが、これが理想的な状態と言えます。なぜなら、どの節の値を探索しようとしても、必ず O(log n) 以内の計算量で済むからです。要するに、二分探索並みの性能が保証される訳です。

しかし、要素の追加が、左部分木や右部分木の一方に偏ると、木構造ではなくリスト構造のような状態になってしまいます。これは、次のような状態です。

悪い状態の二分探索木

こんな状態でも、二分探索木のルールは満たしていますが、探索の性能は、二分探索レベルではなく、線形探索レベルになってしまいます。つまり、計算量も O(log n) から O(n) に落ち込むということですこのような状態は、要素を昇順や降順に追加していけば容易に起こることなので、場合によっては重大な問題となります。

対策として、常に木を整理して、葉の高さをできるだけ揃えるようにする方法があります。これは一般に、平衡木(バランス木)と呼ばれており、二分探索木であれば、平衡二分探索木と呼びます。

平衡二分探索木には、いくつかの実装が存在しており、AVL木赤黒木AA木などがあります。

あるいは、可能であれば、昇順や降順に追加しないように、ランダム性を持たせるようにすれば、性能の低下を防ぐことができます

悪い状態を防げると仮定すると、二分探索木は、配列を二分探索することと比べて、要素の追加や削除が少ないコストで行えるという利点があります。

配列の二分探索の場合は、常に配列全体をソート済みな状態にしなければなりませんから、要素の挿入や削除のたびに既存の要素をずらす操作が必要な配列では、効率が落ちます(第1章参照)。つまり、配列を二分探索することは、探索自体は速くても、追加や削除が弱いのです。

まとめ

二分探索木は、二分木を「左の子の値<親の値<右の子の値」となるようにルール付けしたデータ構造です。

どの葉も同じような高さになるように、うまく節がばらけていれば、二分探索と同じ O(log n) の効率が得られます。しかし、節が根の左部分木や右部分木に偏ってしまうと、線形探索と同じ O(n) にまで効率が落ち込んでしまいます。

配列を二分探索することと比べると、配列をソート済みな状態に保つ手間が削減できることから、追加や削除の部分の効率で、二分探索木の方が勝っています。

高い探索効率を保つためには、データを追加する順序が昇順や降順にならないように工夫するか、平衡木と呼ばれるような、常に木の形を整形する特別な実装を使う必要があります。


練習問題

問題① 要素を昇順に追加した場合と、ランダムに追加した場合とで、探索性能がどの程度変わるか調べて下さい。

問題② 値の重複を許すような二分探索木を作成して下さい。


解答ページはこちら


参考リンク



更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2018/2/12 サンプルプログラムの改善(fgets が受け取った改行文字の削除の方法を修正。const、static の付加)

'2017/11/13 サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2014/12/20 サンプルプログラムで、コマンド処理の方法を整理。

'2012/7/29 新規作成。



前の章へ(第7章 二分木)

次の章へ(第9章 ヒープ)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS