前回説明した「幅優先探索」は、15 パズルのように完成するまでの最小手数を求めるパズルを解くのに適しています。幅優先探索を行う場合、生成する局面が多くなるとメモリの消費量のほかに、同一局面のチェック処理が問題になります。単純な線形検索を使うと、ここでの処理に時間がかかるのです。6 パズルで最長手数の局面を求めましたが、実行時間がかかったのもこれが原因です。このような場合、データの検索を高速に行うことができれば実行時間を劇的に短縮することができます。
高速なデータ検索といっても難しい話ではありません。私たちの身の回りのことを考えてください。たとえば、筆者の部屋は雑誌や書籍が乱雑に積み上げられていて、とても散らかっています。このような状態では、ある記事を読みたいと思っても、それが掲載されている本を探すのにひと苦労です。整理整頓してあれば簡単に見つけることができるのですが、後悔先に立たずといったところです。まあ、一念発起して整理しても、すぐに散らかってしまうのですが。
これはプログラムの場合にも当てはまる話です。線形探索とは、散らかった部屋の中を力任せに探すことと同じです。データの整理整頓に少々時間がかかっても、探索時間を大幅に短縮できれば、結果として全体の処理時間を短縮できるのです。そこで今回は、高速な検索アルゴリズムの基本である「二分探索木」と「ハッシュ法」を紹介します。ひと言で説明すると、二分探索木は「木」というデータ構造を使ってデータを整理整頓する方法で、ハッシュ法はデータを数値に変換して配列に格納する方法です。
Ｃ言語で木構造をプログラムする場合、ポインタを用いる方法が一般的です。また、ポインタを使ってデータ構造を表す場合、もっとも基本的なものに連結リストがあります。連結リストはハッシュ法でも使用するため、最初に連結リストから説明しましょう。そのあとで、木構造、二分探索木、最後にハッシュ法と話を進めていきます。最初は退屈するかもしれませんが、連結リストや木構造は応用範囲が極めて広いデータ構造です。マスターしておけば、今後のプログラミングに役立つことは間違いありません。難しいことはないので、果敢にチャレンジしてくださいね。
連結リスト (linked list) はよく利用されるデータ構造です。配列と同様に複数のデータを格納することができます。Ｃ言語の配列は連続したメモリ領域に割り当てられますが、連結リストはデータを一方向につなげることで複数のデータを格納します。Ｃ言語では、ポインタを使って連結リストを実現するのが普通です。*1 まず最初にデータを格納する構造体を定義します。
/* セルの定義 */
typedef struct cell {
int data;
struct cell *next;
} CELL;
簡単な例題ということで、連結リストには整数値を格納することにします。連結リストの場合、データを格納する構造体をセル (cell) といいます。セルはデータを格納する変数 data と次のセルを指す変数 next から構成されます。next が再帰的に定義されているように見えますが、ポインタであることに注意してください。このような構造体を「自己参照構造体」と呼ぶことがあります。next をポインタではなく、それ自身を含む再帰的な構造にするとコンパイルでエラーとなります。
変数
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(NULL)
└─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 1 : 連結リストの構造
図 1 のように、セルを箱で表すことにします。左側にデータを格納し、右側に次のセルを示すポインタを格納します。このように、Ｃ言語ではポインタを使ってデータを連結していく方法がよく使われます。ポインタを使うことで、いろいろなデータ構造を簡単に実現することができるのです。ポインタが苦手な方はこれを機会にマスターすることをおすすめします。
連結リストの終端を表すため、最後尾のセルの next には NULL を代入しておきます。データの終端を NULL で表すことも、Ｃ言語では一般的な方法です。そして、先頭セルへのポインタを変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、データがひとつもない状態を空リストといいますが、変数の値に NULL を代入することで表すことができます。
ところで、構造体はデータの構造を定義しただけなので、このままでは使うことができません。プログラムで構造体用のメモリを準備する必要があります。このとき、あらかじめ大域変数として用意しておくと、取り扱うデータによって用意した変数が足りなかったり、逆に変数が余ってメモリを無駄使いする、といった不都合なことが発生します。このような場合、プログラムの実行中に新しいメモリを取得できると便利です。Ｃ言語の標準ライブラリには、自由領域 (free store) *2 からメモリを取得する関数 malloc (memory allocate) が用意されています。malloc には取得するメモリのバイト数を与えます。構造体に必要なバイト数は sizeof 演算子で求めることができます。したがって、メモリからセルをひとつ取得する関数は次のようになります。
リスト : セルを取得する
CELL *get_cell( void )
{
CELL *cp;
cp = malloc( sizeof( CELL ) );
if( cp == NULL ){
fprintf( stderr, "Out of Memory\n" );
exit( EXIT_FAILURE );
}
return cp;
}
malloc が返す値は確保したメモリ領域へのアドレス、つまりセルへのポインタとなります。malloc はメモリを確保できない場合 NULL を返します。malloc を使う場合、この返り値を必ずチェックしてください。メモリをたくさん積んでいるから大丈夫だろう、といって省略してはいけません。また、関数 fopen でもファイルのオープンに失敗すると NULL を返しますが、このように特別な値を返す関数を使う場合、エラーチェックは欠かせません。プログラムの場合、予期していないことがよく発生するものです。エラーチェックはとても重要なことなのです。
malloc で割り当てたメモリは、不用になった時点でシステムに返すことになっています。これをメモリの解放といい、関数 free を使います。free で解放されたメモリは再び malloc で割り当てることができます。つまり、メモリを再利用することができるのです。メモリには限りがあるので malloc で割り当てたまま放置しておくと、いつかは底をついてプログラムは実行不可能となります。malloc を繰り返してメモリを取得する場合、いらなくなったメモリは free で解放することを忘れないでください。
free には malloc が返したアドレスを与えることに注意してください。それ以外のアドレスを与えた場合の動作は不定です。試したことはありませんが、たぶん暴走することになるでしょう。
ところで、ほとんどの処理系ではプログラムの終了時に malloc で取得したメモリを free で解放する必要はありません。プログラムで使用したメモリは実行終了時に解放されますが、このとき malloc で割り当てたメモリも解放されるようになっているからです。もちろん、例外的な処理系もあるでしょうが、一般的には malloc で取得したメモリを最後まで使うのであれば、free を省略できると考えてもいいでしょう。
簡単な例題として、データの探索と挿入を行う関数を作りましょう。最初にデータの探索です。
リスト : データの探索
int search( int num, CELL *place )
{
while( place != NULL ){
if( num == place->data ) return TRUE;
place = place->next;
}
return FALSE;
}
連結リストの場合、先頭から順番にデータを比較する線形探索となります。セルをたどる処理ですが、変数 place はセルへのポインタを表していて、次のセルへのポインタは place->next に格納されていることに注意してください。したがって place を次のセルへ進めるには、place = place->next とするだけでいいのです。このようにポインタをたどることで、順番に各要素へアクセスすることができます。最後尾のセルの場合、next には NULL が格納されているので、place の値は NULL となります。これがループの終了条件となります。
次はデータの挿入です。連結リストの場合、先頭にデータを挿入することは簡単です。
変数 place
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ┼─ X ─→│10│・┼→│20│・┼→│30│／│
└┼┘ └─┴─┘ └─┴─┘ └─┴─┘
│ cp ↑
│ ┌─┬─┐│
└→│40│・┼┘
└─┴─┘
図 2 : 先頭にデータを挿入
連結リストでは、データの挿入はポインタの書き換えで行うことができます。図 2 を見てください。連結リストの先頭セルは、変数 place にセットされています。変数 place を新しいセル cp へのポインタに書き換え、cp の next に先頭セルへのポインタをセットすれば、連結リストの先頭にデータを挿入することができます。プログラムは次のようになります。
リスト : 先頭にデータを挿入
void insert_top( int num, CELL **place )
{
CELL *cp = get_cell();
cp->data = num;
cp->next = *place;
*place = cp;
}
変数 place の値を書き換えるため、引数は CELL **place と宣言して変数のアドレスを受け取ることにします。先頭セルへのポインタは place に格納されているので、新しいセル cp の next にセットしてから、place の値を書き換えます。順番を間違えるとセルのリンケージが途切れるため、プログラムは動作しなくなります。
空リストにデータを挿入する場合、新しいセル cp が最後尾となります。この場合でも、変数 place に格納されている NULL が cp->next にセットされるので、プログラムは正常に動作します。逆にいうと、空リストの場合はリストを格納する変数に必ず NULL をセットしてください。
次はリストの途中にデータを挿入する場合です。連結リストの場合、セルの後ろにデータを追加することは簡単に行えます。
変数 c1 c2
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ┼──→│10│・┼─ X ─→│20│・┼→│30│／│
└─┘ └─┴┼┘ └─┴─┘ └─┴─┘
│ cp ↑
│ ┌─┬─┐│
└→│40│・┼┘
└─┴─┘
図 3 : 途中にデータを挿入
図 3 を見てください。セル c1 と c2 の間にデータを挿入する場合、c1 の next を新しいセル cp へのポインタに書き換え、cp の next に c2 へのポインタをセットします。c2 へのポインタは c1->next から求めることができます。したがって、c1->next を書き換える前に、cp->next へ値をセットします。
それでは具体的にデータを挿入する関数 insert を作ります。関数の仕様は、連結リストの n 番目にデータを挿入する、ということにします。連結リストの要素は、Ｃ言語の配列と同様に 0 から数えることにします。リストの先頭にデータを挿入する場合は 0 を指定します。指定した位置が負の値やリストよりも長い場合は、リストの最後にデータを追加することにします。プログラムは次のようになります。
リスト : データの挿入
void insert( int num, int n, CELL **place )
{
CELL *p, *cp;
if( !n ){
insert_top( num, place );
} else {
for( p = *place; p->next != NULL; p = p->next ){
if( !(--n) ) break;
}
cp = get_cell();
cp->data = num;
cp->next = p->next;
p->next = cp;
}
}
引数 n が 0 ならば、insert_top を呼び出してリストの先頭にデータを追加します。そうでなければ、ポインタをたどって目的の位置に移動します。ここで、ループの終了条件に注意してください。n が負の値やリストより長い場合、ループを終了することになりますが、ループの終了条件を p != NULL で判断すると、ループ終了時の p の値が NULL となってしまいます。これでは、最終セルへのポインタが失われるため、リストの最後にデータを追加することができません。p が最終セルを指している状態で繰り返しを終了するために、終了条件を p->next != NULL で判断しています。これによりループが終了したあとでも、p の値は最終セルへのポインタとなります。
ループを抜けたあと、変数 p が指し示すセルの後ろにデータを挿入にします。まず新しいセル cp を取得し、cp->data には num を cp->next には p->next をセットします。p が最終セルの場合には、p->next に NULL がセットされているので、cp->next の値は最終セルを表す NULL となります。最後に p->next に cp をセットすれば挿入は終わりです。
連結リストの長所と短所は、配列と比較するとよく理解できます。まず長所から考えてみましょう。配列の場合、宣言した大きさ以上にデータを格納することはできません。連結リストでは、セルを作ることができれば（すなわちメモリがあれば）、データを追加していくことができます。また、途中にデータを挿入する場合、配列では要素を移動する処理が必要ですが、連結リストではポインタの書き換えで済ますことができます。
逆に短所としては、配列のように添字を使って簡単に要素を取り出すことはできません。先頭から n 番目の要素を取り出す場合、連結リストでは先頭からポインタをたどっていかなければ、目的地に到達することができません。したがって、ランダムアクセスする場合、配列に比べて時間がとてもかかることになります。もうひとつ、データを格納する場所以外にポインタを格納する場所が必要なので、メモリを余分に使うことも欠点です。
このほかにデータの削除処理がありますが、今回はデータの探索が主題なので説明は割愛いたします。連結リストからのデータの削除は難しい処理ではないので、参考文献を読む前に自分で考えてみるといいでしょう。
「木 (tree) 」は、節やノード (node) と呼ばれる要素に対して、階層的な関係（親子関係）を表したものです。身近な例では、ディレクトリ（フォルダ）の階層構造が木にあたります。図 4 に木構造を示します。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ──────── レベル３
図 4 : 一般的な木構造の一例
図 4 ではアルファベットで節を表しています。ディレクトリにルートディレクトリがあるように、木にも「ルート（根）」と呼ばれる節が存在します。図 4 では A がルートになります。木を図示する場合、階層関係がはっきりわかるように、ルートを上にして同じ階層にある節を並べて描きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っていて、これを「部分木」といいます。また、節が一つもない木を「空の木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - F - J という経路があります。これは、ディレクトリやファイルを指定するときのパスと同じですね。ある節からルートの方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接つながっている節を「親」といいます。逆から見ると、「子孫」と「子」という関係になります。子を持たない節を特に「葉」ということがあります。図 4 でいうと、F は J, K の親で、J は F の子です。J は子を持っていないので葉となります。
木構造では、ルート以外の節では必ずひとつの親を持っています。ルートは親を持たない唯一の節です。また、節は複数の親を持つことができません。複数の親を持つ構造は、木ではなくグラフとなります。つまり、木はグラフの中の特別な構造なのです。
子は「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」と呼びます。このとき、子の順番を逆にした木は、別の木として区別します。また、順番がない木を「無順序木」と呼びます。
節が持っている子の数を「次数」といいます。図 4 の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「n 分木」と呼びます。特に、次数 2 の二分木はプログラムでよく使われるデータ構造です。この二分木をデータの探索に用いるのが「二分探索木」です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 5 : 二分探索木の一例
二分探索木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きなデータを配置するように木を構成します。図 5 に二分探索木の例を示します。
たとえば、図 5 から 19 を探してみましょう。最初に root の 18 と探したい数値の 19 を比較します。19 の方が大きいので右側の子をたどり 22 と比較します。今度は 19 の方が小さいので、左側の子をたどり 20 と比較します。19 の方が小さいので左側の子をたどり、ここで 19 を見つけることができました。
二分探索木によるデータの探索は、「二分探索 (binary search) 」と同じ原理です。二分探索は、あらかじめデータを昇順に並べている配列に対して、特定のデータを高速に探索する方法です。線形探索の実行時間が要素数に比例するのに比べ、二分探索は要素数の対数に比例する時間で探索が完了します。二分探索の過程を図 6 に示します。
[11 22 33 44 55 66 77 88 99] 66 > 55 後半を探す
↑
11 22 33 44 55 [66 77 88 99] 88 > 66 前半を探す
↑
11 22 33 44 55 [66 77] 88 99 77 > 66 前半を探す
↑
11 22 33 44 55 [66] 77 88 99 66 = 66 発見
↑
図 6 : 二分探索
二分探索は探索する区間を半分に分けて調べます。66 を探す場合を考えてみましょう。最初に配列の中央値 55 と 66 を比較します。データが昇順に整列されていれば、66 は中央値 55 より大きいので前半の区間を調べる必要はなく、後半の区間だけを探索すればよいことがわかります。これと同じことを後半の区間に対して行い、最後には区間に要素がひとつしかなくなり、それとデータが一致すれば探索成功、そうでなければ探索失敗となります。図 6 の例でも、線形探索を行えば 6 回繰り返すところが、二分探索であれば 4 回で済みます。
二分探索木の場合も同じです。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。図 5 の場合でも、探索するデータ数は 15, 7, 3, 1 となり最後に見つけることができました。データ数を n とすると、単純な線形探索では平均で n / 2 回の比較が必要になりますが、二分探索木を使うと、log n 程度の回数で収まります。たとえば、100 個のデータがある場合、線形探索では 50 回程度の比較が必要になりますが、二分探索木では 7 回程度で済むわけです。
どちらも高速に探索できるのであれば、簡単な二分探索を使えばいいじゃないかと思われた方もいるでしょう。ところが、二分探索にはデータの挿入に時間がかかるという欠点があるのです。データが昇順に整列されていないと、二分探索は動作しません。線形探索のように、配列の最後にデータを追加していくことはできないのです。まず、データを挿入する位置を求め、そこから後ろにあるデータを移動する処理が必要になります。挿入位置は、二分探索を使って高速に見つけることができますが、データ数が多くなるほど移動処理に時間がかかるようになります。このため、プログラムの実行中に頻繁にデータの登録を行う処理には、二分探索は向かないのです。
これに対し、二分探索木はデータの挿入も高速に行うことができます。データの探索は、ルートから始まって下に向かって進んでいきました。データの挿入も同様に、ルートから始まってデータを比較していき、たどるべき部分木がなくなった所にデータを挿入します。
たとえば、図 5 の二分木に 10 を挿入してみましょう。根からデータを比較していくと左側の子をたどっていき、11 の節にたどり着きます。ここでも左側の子をたどろうとしますが、もう部分木はありません。そこで、11 の左側の子として 10 を挿入します。このとき、配列のようにデータを移動する必要がないため、二分探索木ではデータの挿入も高速に行うことができます。
連結リストと同じくポインタを使った例題を示します。まず最初に、節を表す構造体を定義します。
/* 節の定義 */
typedef struct node {
int data;
struct node *left;
struct node *right;
} NODE;
簡単な例題ということで、二分木には整数値を格納することにしました。連結リストと違い、ポインタを格納する変数が 2 つ必要になります。left が左側の子、right が右側の子を表します。子を持たない場合は、連結リストと同様に NULL をセットするのが一般的です。連結リストのように、節を箱で表すと図 7 のようになります。
変数 root
┌─┐
│ ┼──┐
└─┘ │
↓
┌─┬─┬─┐
│18│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│14│／│／│ │22│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：NULL
図 7 : 二分探索木の構造
連結リストと同様に、ルートへのポインタを変数 root に格納しておけば、この変数を使って二分探索木にアクセスすることができます。また、節がひとつもない空の木は、変数 root に NULL をセットすれば表すことができます。
それでは、データを探索する関数から作ってみましょう。この処理は、ルートから始まって下の方に向かってデータを比較していくだけです。
リスト : データの探索
int search( NODE *root, int key )
{
NODE *p = root;
while( p != NULL ){
if( key == p->data ){
return TRUE;
} else if( key < p->data ){
p = p->left;
} else {
p = p->right;
}
}
return FALSE;
}
関数 search には、二分探索木のルートを表す節 root と探索するデータ key を渡します。ポインタ変数 p は、現在探索している節を表します。これは root で初期化しておきます。あとは、p に格納されている data を比較し、等しい値であれば TRUE を返します。key が小さいのであれば左側の子をたどり、そうでなければ右側の子をたどります。たどるべき木がなくなれば p の値は NULL になるので、while ループを終了し FALSE を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないはずです。
次は、データを挿入する関数を作りましょう。探索と同様に、ルートから始まって下の方に向かってデータを比較していき、たどるべき木がなくなった所に新しいデータを挿入します。同じデータを見つけた場合は FALSE を返し、データを挿入した場合は TRUE を返すことにします。
リスト : データの挿入
int insert( NODE **root, int key )
{
NODE *new, **np = root;
while( *np != NULL ){
if( key == (*np)->data ){
return FALSE;
} else if( key < (*np)->data ){
np = &((*np)->left);
} else {
np = &((*np)->right);
}
}
new = get_node(); /* 節を一つ取得する */
new->data = key;
new->left = NULL;
new->right = NULL;
*np = new;
return TRUE;
}
関数 insert は引数として root を受け取りますが、最初にデータを挿入する場合、つまり空の木 (NULL) にデータを挿入するときは、ルートを格納する変数を書き換える必要があります。このため、引数は NODE **root と宣言して、変数のアドレスを受け取ります。変数 np も同じく、節を格納する変数のアドレスを表します。最初はルートを格納する変数のアドレスですが、二分木をたどるときは、子を格納している left か right のアドレスを表します。*np が NULL であれば、たどるべき木がなくなったので、*np に新しい節を挿入すればいいわけです。もし、空の木であれば *np は NULL なので、ルートに新しい節が挿入されます。
新しい節は関数 get_node で取得します。この関数は get_cell と同様に malloc を呼び出してメモリを確保します。メモリ確保に失敗した場合は、エラーメッセージを出力して終了します。あとは構造体のメンバにデータを書き込んで、*np に新しい節をセットします。
最後に、二分探索木の全データを出力する関数を作ります。二分探索木は、データの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。木のすべての節を規則的な順序で回ることを「巡回 (traverse) 」といいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分探索木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理は、再帰定義を使えば簡単に実現できます。
リスト : データの表示
void print( NODE *tree )
{
if( tree != NULL ){
print( tree->left );
printf("%d\n", tree->data );
print( tree->right );
}
}
まず、tree が NULL ならば何もしません。これが再帰呼び出しの停止条件となります。あとは、通りがけ順の定義そのままにプログラムをするだけです。左の子を出力するため、tree->left に対して print を再帰呼び出しします。次に、節のデータ tree->data を出力します。最後に右側の子を出力するため、tree->rigth に対して print を再帰呼び出しします。
このほかに、データの削除処理がありますが、連結リストと同じ理由で説明は割愛いたします。二分探索木の場合、データの探索に比べて削除処理は複雑です。興味のある方は、参考文献を読んでください。