二分探索木によるサーチ

二分探索木の構造と探索アルゴリズム、再帰的なデータ構

造の理解とC言語での実装

【学習内容の構成】

1. 木構造の基礎：節点と枝で構成される階層的データ構

造、根・葉・部分木の概念

2. 二分探索木：左の子は親より小、右の子は親より大とい

う配置規則を持つ探索用データ構造

3. 木の走査：行きがけ順・帰りがけ順・通りがけ順による全

節点の巡回方法

4. 再帰と末尾再帰最適化：再帰的構造の活用と非再帰へ

の変換による効率化

• 前提：C言語の構造体、配列、ポインタの基礎知識

• 意義：効率的なデータ探索手法の習得、再帰の理解

アルゴリズムとデータ構造

• 複雑なプログラムを作成する時，データ構造とア

ルゴリズムについて考える必要がある

• アルゴリズム

– 問題を解くための論理または手順をアルゴリズムとい

う

– ある１問題を解くためのアルゴリズムは，一般に複数

個存在する．

– その中でもより効率よく解答を得られるようなアルゴリ

ズムを見つけることが優れたプログラムを作成する上

で大切

• データ構造

– アルゴリズムを容易にするために工夫されたデータの

並び

– 基本的なデータ構造は，配列，構造体(レコード)型，

キュー，スタック，リスト構造，木構造など

木構造

• 幾つかの節点(node)と，それらを結ぶ枝(branch)から

構成

– 節点がデータに対応

– 枝がデータ間の親子関係に対応

– 子：節点の中で下方に分岐する枝の先にあるもの

– 親：分岐元の節点

親

子

枝(branch)

節点(node)

図．単純な木構造

木構造

• 根(root)：木の一番上の節点を根(root)

• 葉(leaf)：子を持たない節点

• 部分木：木の中のある節点を相対的な根と考えた

ときの，そこから枝分かれした枝と節点の集合

部分木

根(root)

葉(leaf)

二分木(binary tree)

• 木構造で，各節点から出る枝が二本以下

のもの

• 木構造に関するアルゴリズムの中で，中心

的なデータ構造

二分探索木(binary search tree)

• 二分木の一種

• データの配置に規則あり

– 左側のすべての子は親より小さい

– 右側のすべての子は親より大きい

• データの探索のためのデータ構造

13 40 61

二分探索木による探索

• 根(root)から始める

• 探索キーの値と，各節点のデータを比較し，

目標となるデータを探す

– 探索キーよりも節点のデータが小さいときは，

右側の子をたどる

– 探索キーよりも節点のデータが大きいときは，

左側の子をたどる

二分探索木による探索の例

(例） 40である節点を探す場合

1. 根の値(35)と，探索キー(40)を比較

2. 探索キーの方が大きいので，右側の子節点へ移る

3. 次に移った節点の値(46)と探索キー(40)を比較し

4. 探索キーの方が小さいので，左の子節点へ移る

5. 次に移った節点(40)が，目標の節点である

13 40 61

再帰的なデータ構造

• 自分自身を定義するのに，自分自身より1

次低い部分集合を用い，さらにその部分

集合は，より低次の部分集合を用いて定

義するという事を繰り返す構造

二分木の再帰的構造

• 二分木は，各節点の右部分木，左部分木も二分

木

• 二分探索木では，探索において，子へ移動し，

親での処理と同様の処理を繰り返す

右部分木左部分木

右部分木

左部分木

二分探索木の走査

• 走査とは

– 一定の手順で木の全ての節点を訪れること

• 二分木の節点を巡回する方法

– pre-order traversal （行きがけ順）

– post-order traversal （帰りがけ順）

– in-order traversal （通りがけ順）

• 走査の方法や関数の作り方によって，処理速度が異なる

行きがけ順(pre-order traversal)

• 木の高さを計算する時のような，節上の走査が

それより下の部分木に依存する時に使われる

1. 今の節点に操作を施す

2. 左の節点へ移動

3. 右の節点へ移動

F G

A, B, D, E, C, F, G の順に

節点を巡回

帰りがけ順(post-order traversal )

1. 左の節点へ移動

2. 右の節点へ移動

3. 今の節点に操作を施す

F G

D, E, B, F, G, C, A の順に

節点を巡回

通りがけ順(in-order traversal )

• 二分探索木で，全ての節点のデータを，ソート

された順番で表示するなど

1. 左の節点へ移動

2. 今の節点に操作を施す

3. 右の節点へ移動

F G

D, B, E, A, F, C, G の順に

節点を巡回

２分木をC言語の構造体で表現

// ２分木のノード

struct BTNode

{

BTNode * left;

BTNode * right;

int value;

};

left right

value

left right

value

left right

value

例題．二分探索木

• 二分探索木の探索プログラムを作る

– 二分探索木の節点を格納するために，構造体

NODE を作る

– 二分探索木を格納するために，配列 node を

宣言する

• 行きがけ順に，節点に0から6まで番号を付け，そ

れぞれを node[0], ..., node[6]とする

#include<stdio.h>

struct NODE{

int left; /*左の部分木*/

int value; /*節点の値*/

int right; /*右の部分木*/

}

main()

{

struct NODE nod[] ={{1,35,3}, {2,21,EOF}, {EOF,13,EOF}, {4,46,5}, {EOF,40,EOF},

{EOF,61,6}, {EOF,69,EOF}};

int i, in;

printf("Input Number :"); /*探す値を入力*/

scanf("%d", &in);

i=0;

while(nod[i].value!=in) {

if ((nod[i].value>in) & (nod[i].left!=EOF)) { /*左の木を探す*/

i=nod[i].left;

} else if ((nod[i].value<in) & (nod[i].right!=EOF)) { /*右の木を探す*/

i=nod[i].right;

} else {

printf(“Not Found¥n”); /*一番下の節点にきても見つからない場合*/

exit();

}

printf("Found %d in nod[%d]¥n", in, i); /*見つかった場合*/

}

末尾再帰最適化

• 末尾再帰を，非再帰的(反復的)なものに変換す

ること

kaijo(int n)

{

int f = 1;

while(n>1) {

f = f * n;

n--;

}

return f;

}

int main()

{

printf( "%d¥n", kaijo(5) );

return 0;

}

kaijo(int a, int n)

{

if ( n > 1 ) {

a = a * n;

n--;

return kaijo( a, n );

}

return a;

}

int main()

{

printf( "%d¥n", kaijo(1,5) );

return 0;

}

末尾再帰

非再帰

末尾再帰とは？

• （ある条件の時に）関数の終わりで再帰呼び出しを実行

するような関数

• 一般に、再帰関数による処理は、繰り返し処理で書き換

え可能である（問題や記述言語によって、どちらの方が

書きやすいか異なる）

• ただし、通常は、再帰呼び出しの方が時間的・メモリ的な

コストがかかる

• しかし、末尾再帰の場合は、単純に再帰を繰り返しに置

き換えられるので、計算機で最適化ができる（特にインタ

プリタ言語・実行環境で有効）