RSS
この章の概要です。
関連する話題が、以下のページにあります。
二分探索木は、前章で紹介した二分木を実戦的に使う実例です。二分木にあるルールを適用することによって、データの探索効率を向上させたデータ構造です。
あるルールというのは、「左の子の値 ＜ 親の値 ＜ 右の子の値」という条件を持たせるというものです。この式だと同じ値を持てないようですが、２つの不等号のうち片方だけなら = を付けられます。
このルールを満たした木のイメージ図は、次のようになります。
このルールを満たすようにしていれば、次の手順で、特定の値を持ったデータを探せます。
先ほどのイメージ図を見ながら考えると、たとえば、最初に根を調べたとき、探したい値の方が小さかったとしたら、根の右部分木は調べる必要がないことが分かります。これは、１回比較を行うたびに、探索する対象が半分になることを意味しています。
探索アルゴリズムを先に学習していた人は、二分探索（【探索】第４章）と同じことが起きているといえばわかると思います。。
この作業を繰り返すので、探索する対象はどんどん半分に減っていきます。探索の効率が非常に良いことがわかります。計算量（【導入】第１章）でいえば、O(log n) です。
ところが、二分探索木は運用を誤ると、せっかくの効率を失ってしまいます。前章でも触れたように、木構造はまるで連結リストのような形状になってしまう可能性があるためです。
この場合でも、左の子がないだけであって、「左の子の値 ＜ 親の値 ＜ 右の子の値」というルールは満たしていますから、木には見えませんが、これでも二分探索木だといえます。
しかしこれでは、「１回比較を行うたびに、探索する対象が半分に」ならないので、探索効率は非常に悪くなっています。もはや連結リストと同等なので、計算量でいえば O(n) にまで落ち込んでいます。
このように二分探索木は、どのような形になっているかによって、性能が大きく変化します。性能を保つためにはできるだけ、葉の高さがそろった奇麗な形の木になるように工夫することが必要です。この件については、後で再び取り上げます。
では、実際のプログラムを見ていきましょう。
// main.c
#include <stdbool.h>
#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 bool add_elem(int value);
static bool remove_elem(int value);
static bool 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();
}
/*
二分探索木を削除
*/
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];
get_line( buf, sizeof(buf) );
enum Cmd_tag cmd = CMD_NUM;
for( int 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[cmd]();
}
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;
}
/*
要素を入れる
*/
bool add_elem(int value)
{
return bsearch_tree_add( gBSTree, value );
}
/*
要素を取り出す
*/
bool remove_elem(int value)
{
return bsearch_tree_remove( gBSTree, value );
}
/*
要素を探す
*/
bool search_elem(int value)
{
return bsearch_tree_search(gBSTree, value) != NULL;
}
/*
木の中身を出力
*/
void print_elem(void)
{
bsearch_tree_print( gBSTree );
}
/*
標準入力から１行分受け取る
受け取った文字列の末尾には '\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 <assert.h>
#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 BSTree_tag {
struct BSNode_tag* root; // 根へのポインタ
};
static void delete_rec(struct BSNode_tag* p);
static struct BSNode_tag* remove_min(struct BSNode_tag** p);
static void print_rec(struct BSNode_tag* p);
/*
二分探索木を作る
*/
BSearchTree bsearch_tree_create()
{
BSearchTree tree = malloc(sizeof(struct BSTree_tag));
tree->root = NULL;
return tree;
}
/*
二分探索木を削除する
*/
void bsearch_tree_delete(BSearchTree tree)
{
if( tree == NULL ){
return;
}
if( tree->root != NULL ){
// 根を起点にして、すべての節を解放する
delete_rec( tree->root );
}
free( tree );
}
void delete_rec(struct BSNode_tag* p)
{
if( p == NULL ){
return;
}
delete_rec( p->left );
delete_rec( p->right );
}
/*
二分探索木に要素を追加する
*/
bool bsearch_tree_add(BSearchTree tree, int value)
{
assert(tree != NULL);
struct BSNode_tag** p = &(tree->root);
// 根から節を辿って、value を置いても二分探索木のルールを満たせる場所を探す
while( *p != NULL ){
if( (*p)->value == value ){
// すでに同じ値の要素があった。
// このプログラムでは、これは失敗とみなすことにする。
return false;
}
else if( (*p)->value < value ){
p = &((*p)->right);
}
else{
p = &((*p)->left);
}
}
// この場所に節をつくる
*p = malloc(sizeof(struct BSNode_tag));
(*p)->value = value;
(*p)->left = NULL;
(*p)->right = NULL;
// １つ目の節のときは、根として登録
if( tree->root == NULL ){
tree->root = *p;
}
return true;
}
/*
二分探索木から要素を取り除く
*/
bool bsearch_tree_remove(BSearchTree tree, int value)
{
assert(tree != NULL);
struct BSNode_tag** p = &(tree->root);
while( *p != NULL ){
struct BSNode_tag* 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 = remove_min( &x->right );
(*p)->left = x->left;
(*p)->right = x->right;
}
free( x );
return true;
}
else if( x->value < value ){
p = &(x->right);
}
else{
p = &(x->left);
}
}
return false;
}
/*
二分探索木から要素を探す
*/
BSNode bsearch_tree_search(BSearchTree tree, int value)
{
assert(tree != NULL);
struct BSNode_tag* p = tree->root;
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)
{
if( tree == NULL ){
return;
}
print_rec( tree->root );
}
void print_rec(struct BSNode_tag* p)
{
if( p == NULL ){
return;
}
char left[16];
char right[16];
if( p->left == NULL ){
strcpy( left, "NULL" );
}
else{
sprintf( left, "%d", p->left->value );
}
if( p->right == NULL ){
strcpy( right, "NULL" );
}
else{
sprintf( right, "%d", p->right->value );
}
printf( "%s <-- %d --> %s\n", left, p->value, right );
print_rec( p->left );
print_rec( p->right );
}
/*
最小の値をもつ節を取り除く
*/
struct BSNode_tag* remove_min(struct BSNode_tag** p)
{
// 最小の値を持った要素は、必ず左の子を辿った先にある
while( (*p)->left != NULL ){
p = &(*p)->left;
}
struct BSNode_tag* x = *p; // x が削除される要素
*p = (*p)->right; // x の右の子を x の位置へ移動させる
// (right が NULL でも構わない)
return x;
}// bsearch_tree.h
#ifndef BSEARCH_TREE_H_INCLUDED
#define BSEARCH_TREE_H_INCLUDED
#include <stdbool.h>
// 二分探索木の型
typedef struct BSTree_tag* BSearchTree;
// 二分探索木の節の型
typedef struct BSNode_tag* BSNode;
/*
二分探索木を作る
戻り値：
作成された二分探索木。
使い終わったら、bsearch_tree_delete関数に渡して削除する。
*/
BSearchTree bsearch_tree_create();
/*
二分探索木を削除する
引数：
tree: 二分探索木
*/
void bsearch_tree_delete(BSearchTree tree);
/*
二分探索木に要素を追加する
引数：
tree: 二分探索木
value: 追加する要素の値
戻り値：
成功したら true、失敗したら false を返す。
*/
bool bsearch_tree_add(BSearchTree tree, int value);
/*
二分探索木から要素を取り除く
引数：
tree: 二分探索木
value: 取り除く要素の値
戻り値：
成功したら true、失敗したら false を返す。
*/
bool bsearch_tree_remove(BSearchTree tree, int value);
/*
二分探索木から要素を探す
引数：
tree: 二分探索木
value: 探し出す要素の値
戻り値：
要素が見つかれば、その要素へのポインタ。
見つからなければ、NULL を返す。
*/
BSNode bsearch_tree_search(BSearchTree tree, int value);
/*
二分探索木の内容を出力する
引数：
tree: 二分探索木
*/
void bsearch_tree_print(BSearchTree tree);
#endifまず、bsearch_tree_create関数を使って、二分探索木の作成を行います。
この関数は、BSearchTree型の戻り値を返します。BSearchTree型は、二分探索木全体を表すための型です。連結リストのときに先頭を表すダミー要素を作ったように（第３章）、BSearchTree はダミーとして働きます。
BSearchTree型の実体は bsearch_tree.c に隠されています。
struct BSTree_tag {
struct BSNode_tag* root; // 根へのポインタ
};このように根へのポインタだけを持っています。bsearch_tree_create関数では、まだ根は作っておらず、roor は NULL です。この時点で根を作ってしまう実装でも何ら問題ありません。
根の表現については、struct BSNode_tag* としています。こちらは以下のようになっています。
struct BSNode_tag {
int value; // この節のデータ
struct BSNode_tag* left; // 左の子へのポインタ
struct BSNode_tag* right; // 右の子へのポインタ
};要素の追加は、bsearch_tree_add関数で行われています。
「左の子の値 ＜ 親の値 ＜ 右の子の値」というルールを満たすことが必要なので、まずは適切な追加位置を探します。
そこでまず、根から調べ始めます。追加しようとする値の方が小さければ左の子へ進み、大きければ右の子へ進みます。この操作を繰り返していき、進む先がなくなったら、そこが適切な追加位置です。進む先がなくなっているという状況なのですから、木構造の葉の位置ということになります。
【上級】このような、葉にしか要素が追加されない実装は二分探索木の単純な実装例です。この方法では、部分木ごとの高さに大きな差ができてしまう可能性があり、探索効率が悪くなっていくかもしれません。たとえば、平衡木と呼ばれる実装では、木の高さをできるだけそろえるように、要素を追加する位置を制御します。
追加しようとする値と同じ値が、すでに存在していた場合には失敗としています。つまり、値の重複を許していないわけですが、このサンプルプログラムの方針だというだけのことであって、重複を許可するような二分探索木をつくることは可能です。これは練習問題とします。
ところで、bsearch_tree_add関数の実装はかなり難しくみえると思います。まず、ポインタ変数 p を宣言しています。
struct BSNode_tag** p = &(tree->root);「*」の数が２つであることに注意してください。つまり、ポインタへのポインタです（Ｃ言語編第３６章）。
適切な挿入位置を探すとき、p が指し示す先を変更しながら進みます。p に代入される値は、実在する節がもっている left や right です。left も right もポインタなので、それを指し示す p は、ポインタへのポインタでなければなりません。
適切な挿入位置を発見したあと、新しい節を生成します。
*p = malloc(sizeof(struct BSNode_tag));
(*p)->value = value;
(*p)->left = NULL;
(*p)->right = NULL;新しく生成した節の left と right が NULL で初期化されるのは、二分探索木の葉のところに追加しているからです。
では、追加する節の親がもっている left と right はどうなっているのでしょうか。もし、left の側に節を追加したのなら left が *p を指すようになっていなければならないですし、right の側に追加したのなら、right が *p を指さなければなりません。そのようなポインタを付け替える操作がないように見えますが、きちんと行われています。
malloc関数を呼び出す段階になったとき、p が何を指しているのかをよく理解してください。ソースコードを観察すると分かるように、p に代入しているのは、&left か &right のどちらかだけです。malloc関数の戻り値は *p に代入しているので、それはどこかの実在する節のメンバである left か right に代入しているということなのです。
つまり「挿入位置の親->left = malloc(～);」のようにしているのと同じです。そのため、親の left（あるいは right）はきちんと書き換わっています。
要素の削除は、bsearch_tree_remove関数で行っています。
二分探索木の操作の中では、削除がもっとも難しい作業になります。これは、葉以外の節を削除する場合には、その子を木の中に残してやらなければならないからです。
もし、子が１個だけの節を削除する場合は割と簡単で、その子を、削除された要素があった位置へ移動させるだけで済みます。
子が２個ある場合が難しく、削除された要素があった位置には、左部分木と右部分木のすべての要素の中から、適切な１つの節を選び出して移動させる必要があります。
具体的には、次のいずれかを選択します。
こうしないと、「左の子の値 ＜ 親の値 ＜ 右の子の値」のルールが壊れてしまいます。つまり、削除された要素があった位置に移動してくる節は、その左部分木のどの節よりも大きい値を持ち、右部分木のどの節よりも小さい値を持っていなければなりません。
サンプルプログラムでは、後者を選択しています。
bsearch_tree_add関数と同様、bsearch_tree_remove関数の実装も、ポインタへのポインタを駆使した複雑そうなコードになっています。実際のところ、説明したとおりですし、詳細に入れたコメントのとおりでもあります。
remove_min という関数も登場しています。この関数は、部分木の中から、一番小さい値をもつ節を探し、そのポインタを返します。その際、削除される節の子を、削除される節の位置に移動させます。削除される節自体は、この関数ではまだ削除（つまり、free関数による解放）は行っておらず、木構造から切り離されただけです。
サンプルプログラムでは「右部分木の中から、もっとも小さい値を持った要素を移動させる」という方針を採っているので、remove_min関数のような実装になります。もう１つの「左部分木の中から、もっとも大きい値を持った要素を移動させる」を採用するなら、一番大きい値を取り除く remove_max関数のような関数を作って、左部分木を操作します。
要素の探索は、bsearch_tree_search関数で行っています。
ここまで理解できていれば、この関数はそれほど難しくありません。根からはじめて、目的の値との大小関係に応じて、左の子か右の子をたどることを繰り返していけばいいだけです。
葉まで行き着いても目的の値と一致しなければ、目的の値は木の中にありません。
要素の出力は、bsearch_tree_print関数で行っています。
木の中身を奇麗に整形して出力するのは、それなりに大変です。この関数はあくまで一例として示しただけです。そもそもデバッグ向けの関数だと言えますから、好きなように実装すればいいと思います。
二分探索木を評価するにあたっては、要素の追加・削除・探索の計算量がポイントです。
葉の高さがほぼ一定な、きれいな形の木になっていれば、追加も削除も探索も、O(log n) の計算量になります。これは、最高の性能だというわけではありませんが、すべてが平均的に “悪くない” 性能です（計算量を比較した表が【導入】第１章にあります）。
しかし、すべての節が根の左部分木（または右部分木）に集中してしまう最悪の状態のときには、O(n) まで悪化します。これは何度か書いているとおり、連結リストと同等の状態だからです。
最良の O(log n) と最悪の O(n) の２択ということではなく、木の状態の程度によって、これらのあいだの性能が出ていると思われます。そのため、性能ができるだけ良い状態を保つためには、どの葉も同じような高さにあるように、木を整え続けることが重要です。
前章で、完全二分木という言葉が登場しました。これは、どの葉も同じ高さにある二分木のことですが、これが理想的な状態と言えます。この状態なら、木の中にある要素を探したり、要素を追加する位置を探したりするときに、１回の比較ごとに、候補が半分に減っていくので、O(log n) の計算量を維持できます。
反対に、非常に悪い状態（連結リストのようなかたち）は、要素を昇順や降順に追加していくだけで簡単に発生します。まれにしか起こらないような現象ではないのです。
この章で取り上げた二分探索木の実装のままで対処するには、要素を追加する順番を工夫するしかありません。これは可能な場合もあるかも知れませんが、難しい場合もあるでしょう。
よりよい対策としては、つねに木を整理して、葉の高さをできるだけそろえるようにすることです。このように実装された木を、平衡木（バランス木）と呼びます。二分探索木を平衡木として実装したものを、平衡二分探索木と呼びます。
平衡二分探索木を実現する方法には、AVL木、赤黒木、AA木など、いくつかあります。
悪い状態を防げると仮定すると、二分探索木は、配列を二分探索（【探索】第４章）することと比べて、要素の追加や削除を少ないコストで行えるという利点があります。
配列を二分探索するには、つねに配列全体をソート済みな状態にしなければなりませんから、要素の挿入や削除のたびに既存の要素をずらす操作が必要な配列では、効率が落ちます（第１章参照）。つまり、配列を二分探索することは、探索自体は速くても、追加や削除が弱いのです。
また、連結リストでは、二分探索自体が効率よく実装できません（【探索】第４章）。
二分探索木は、二分木を「左の子の値 ＜ 親の値 ＜ 右の子の値」となるようにルール付けしたデータ構造です。
どの葉も同じような高さになるように、うまく節がばらけていれば、二分探索（【探索】第４章）と同じ O(log n) の効率が得られます。しかし、節が根の左部分木や右部分木に偏ってしまうと、線形探索（【探索】第１章）と同じ O(n) にまで効率が落ち込んでしまいます。
配列を二分探索することと比べると、配列をソート済みな状態に保つ手間が削減できることから、追加や削除の部分の効率で、二分探索木の方が勝っています。連結リストの二分探索はそもそも非効率なので、こちらにも勝ります。
高い探索効率を保つためには、データを追加する順序が昇順や降順にならないように工夫するか、平衡木と呼ばれるような、つねに木の形を整形する特別な実装を使う必要があります。
問題① 要素を昇順に追加した場合と、ランダムに追加した場合とで、探索性能がどの程度変わるか調べてください。
問題② 値の重複を許すような二分探索木を作成してください。
要素数を意味している「サイズ」について、「要素数」に表記を改めた。
≪さらに古い更新履歴を展開する≫
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |