| 目次 | 索引 |
|---|---|
h2 探索 toc-search
h3 探索とは toc-what-is-search
あらかじめ格納されているデータの中から、
要求されたデータを見つけることを、
index 探索 search たんさく
と言います。
要求データの格納場所を決定したり、
格納データの中のすべての要求データを列挙したり、
要求データは存在しないと結論を出すことも、
探索に含めます。
また、例えば会員番号と氏名からなるレコードの中から、
与えられた会員番号のレコードを見つけることも探索です。
探索はよく行われるデータ処理ですので、
いくつかの高速アルゴリズムが考えられています。
アルゴリズムの良し悪しは、探索方法だけではなく、
格納データへのデータの挿入や、
格納データからのデータの削除が発生するかどうかにも関係します。
問題は次のように分類できます。
・探索のみ発生する場合
・探索と挿入が発生する場合
・探索、挿入、および削除が発生する場合
ここでは、要求データを探索し、
見つからなかったら格納データへ挿入するという問題を考えます。
具体的には、最初に格納データを空にし、
次々と乱数を発生させては探索し、見つからなかったら挿入する、
という手続きを繰り返します。
例えば、発生した乱数が 4, 1, 3, 1, 4 ですと、
4, 1, 3 までは新しい要素なので、探索しても見つからず、挿入されます。
その後の 1 と 4 は、探索して見つかりますので、挿入されません。
h3 線形探索 toc-linear-search
あらかじめ格納されているデータが、
何の規則性もなく格納されているのでしたら、
先頭から順番に探すしかありません。
この、先頭から順番に探す探索法を、
index 線形探索 linear search せんけいたんさく
と呼びます。
線形探索では、一つ一つ調べますので、
格納データが増えれば探索にも時間が掛かります。
一方、データの挿入は、格納データの末尾に追加するだけですので、
すぐにできます。
線形探索を行う場合、配列にデータを格納するのが簡単です。
このとき、番人を利用しますと、探索の能率が上がります。
具体的には、a[1] から a[n] までの中から v を探索するとき、
前もって a[0] に v を格納し、a[n], a[n - 1], ... と調べるのです。
データがあってもなくても v は見つかりますので、
添字が負でないことを確かめる手間が省けます。
a[0] で見つかれば、それはデータがないことを意味します。
プログラムは以下の通りです。
メソッド search はデータ v を探索し、その格納場所を返します。
データがなければ 0 を返します。
メソッド insert はデータ v を挿入します。
class LinearSearch {
public static void main (String[] args) {
int i, v, n = 0, MAX = 9;
int[] a = new int[MAX + 1];
for (i = 1; i <= MAX; i++) {
v = (int) (Math.random() * MAX) + 1;
if (search(a, n, v) == 0) {
insert(a, n, v);
n++;
}
System.out.print(v + ":");
print(a, n);
}
}
static int search (int[] a, int n, int v) {
a[0] = v;
while (a[n] != v) {
n--;
}
return n;
}
static void insert (int[] a, int n, int v) {
a[n + 1] = v;
}
static void print (int[] a, int n) {
int i;
for (i = 1; i <= n; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
}
}
出力結果は次の通りです。
コロンの右側は探索・挿入する値、
左側は探索・挿入したあとの格納データです。
b04a001@AsiaA1:~/comp3b% java LinearSearch
4: 4
1: 4 1
3: 4 1 3
1: 4 1 3
4: 4 1 3
2: 4 1 3 2
1: 4 1 3 2
6: 4 1 3 2 6
5: 4 1 3 2 6 5
b04a001@AsiaA1:~/comp3b%
h3 二分探索 toc-binary-search
格納データが整列されている場合、高速な探索が可能になります。
それが、
index 二分探索 binary search にふんたんさく
です。
二分探索では、まず、格納データの中央を調べます。
そこにデータがあれば終了します。
なければ、データが左半分にあるか右半分にあるかを見極めます。
そして、半分になった探索範囲の中央を調べます。
これを繰り返して探索範囲を狭めていき、
範囲が空になったらデータはないという結論を出します。
二分探索を行う場合は、配列にデータを格納します。
探索範囲が a[l] から a[r] までですと、
中央の a[k] は k = (l + r) / 2 で求められます。
左半分は a[l] から a[k - 1] までで、
右半分は a[k + 1] から a[r] までです。
例として、{1, 3, 5, 6, 7, 8, 9} の中から 5 を探索します。
下図のように、探索は 3 回で終了します。
| | | | | | | | 5 を探索
| 1 | 3 | 5 | 6 | 7 | 8 | 9 |
+-----+-----+-----+-----+-----+-----+-----+
^ ^ ^ ^ ^
: : : : :
l : : k r 1 回目
: : :
l k r 2 回目
:
lkr 3 回目
二分探索では、飛び飛びに調べますので、
格納データが増えても探索にあまり時間は掛かりません。
一方、データの挿入は、整列状態を保つ必要がありますので、
時間が掛かります。
挿入の能率を上げるため、a[0] を番人として使います。
挿入整列と同じように、a[0] に負の無限大を格納しておきます。
プログラムは以下の通りです。
メソッド search はデータ v を探索し、その格納場所を返します。
データがなければ 0 を返します。
メソッド insert はデータ v を挿入します。
class BinarySearch {
public static void main (String[] args) {
int i, v, n = 0, MAX = 9;
int[] a = new int[MAX + 1];
a[0] = Integer.MIN_VALUE;
for (i = 1; i <= MAX; i++) {
v = (int) (Math.random() * MAX) + 1;
if (search(a, n, v) == 0) {
insert(a, n, v);
n++;
}
System.out.print(v + ":");
print(a, n);
}
}
static int search (int[] a, int n, int v) {
int l = 1, r = n, k;
while (l <= r) {
k = (l + r) / 2;
if (a[k] < v) {
l = k + 1;
} else if (a[k] > v) {
r = k - 1;
} else {
return k;
}
}
return 0;
}
static void insert (int[] a, int n, int v) {
while (a[n] > v) {
a[n + 1] = a[n];
n--;
}
a[n + 1] = v;
}
static void print (int[] a, int n) {
int i;
for (i = 1; i <= n; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
}
}
b04a001@AsiaA1:~/comp3b% java BinarySearch
5: 5
6: 5 6
1: 1 5 6
1: 1 5 6
3: 1 3 5 6
8: 1 3 5 6 8
7: 1 3 5 6 7 8
9: 1 3 5 6 7 8 9
5: 1 3 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h3 二分探索木 toc-binary-search-tree
二分探索木というものを利用しますと、探索も挿入も高速に行えます。
index 二分探索木 binary search tree にふんたんさくき
とは、左の子とその子孫のすべての値が親以下で、
右の子とその子孫のすべての値が親以上である二分木です。
次は二分探索木の例です。
6
|
+-------+-------+
| |
3 9
| |
+---+---+ +---+
| | |
2 5 8
| |
+---+ +---+
| |
1 7
二分探索木でデータを探索するには、最初に根を調べ、
根の値より小さいデータなら左の子を訪ね、
大きいデータなら右の子を訪ねていくことで行えます。
子がなければ、二分探索木にそのデータがないことが分かります。
例えば、上記の二分探索木で 7 を探索しますと、
右、左、左とたどって見つけられます。
6
| 7 を探索
........+-------+
: |
3 9
: |
......... +---+
: : |
2 5 8
: |
..... +---+
: |
1 7
二分探索木にデータを挿入するには、探索と同じ要領で子を訪ねていき、
子がなくなった所で、そのデータを値とする節点を用意し、
新たな子とします。
例として、空の二分探索木にデータ
6, 3, 5, 9, 2, 8, 7, 1
を順に挿入する様子を示します。
6
:
.........
:
3
6
|
+-------+
|
3
:
.....
:
5
6
|
+-------+........
| :
3 9
|
+---+
|
5
6
|
+-------+-------+
| |
3 9
|
....+---+
: |
2 5
6
|
+-------+-------+
| |
3 9
| :
+---+---+ .....
| | :
2 5 8
6
|
+-------+-------+
| |
3 9
| |
+---+---+ +---+
| | |
2 5 8
:
.....
:
7
6
|
+-------+-------+
| |
3 9
| |
+---+---+ +---+
| | |
2 5 8
: |
..... +---+
: |
1 7
二分探索木では、木の一部のみを調べますので、
格納データが増えても探索にあまり時間は掛かりません。
データの挿入も、同じ理由で時間が掛かりません。
プログラムでは、探索は while (true) { ... } で繰り返し木をたどり、
データが見つかるかデータがないことが分かると return で終了します。
挿入も同様です。
また、プログラムを簡単にするために、根の上にダミーの節点を置き、
その値を 0 とします。
本来の節点の値は、すべて 0 より大きいとします。
木を構成するクラスは、前々回定義した IntTree を使います。
class IntTree {
int node;
IntTree left, right;
IntTree (int node, IntTree left, IntTree right) {
this.node = node;
this.left = left;
this.right = right;
}
}
プログラムは以下の通りです。
メソッド search はデータ v を探索し、v 自身を返します。
データがなければ 0 を返します。
メソッド insert はデータ v を挿入します。
search と insert が似ていることに注意してください。
メソッド print は、中央順走査で格納データを出力します。
二分探索木の定義から、中央順に走査しますと小さい順に並びます。
class BinarySearchTree {
public static void main (String[] args) {
int i, v, MAX = 9;
IntTree tr = new IntTree(0, null, null);
for (i = 1; i <= MAX; i++) {
v = (int) (Math.random() * MAX) + 1;
if (search(tr, v) == 0) {
insert(tr, v);
}
System.out.print(v + ":");
print(tr);
}
}
static int search (IntTree tr, int v) {
while (true) {
if (tr.node > v) {
if (tr.left != null) {
tr = tr.left;
} else {
return 0;
}
} else if (tr.node < v) {
if (tr.right != null) {
tr = tr.right;
} else {
return 0;
}
} else {
return tr.node;
}
}
}
static void insert (IntTree tr, int v) {
while (true) {
if (tr.node > v) {
if (tr.left != null) {
tr = tr.left;
} else {
tr.left = new IntTree(v, null, null);
return;
}
} else if (tr.node < v) {
if (tr.right != null) {
tr = tr.right;
} else {
tr.right = new IntTree(v, null, null);
return;
}
} else {
return;
}
}
}
static void print (IntTree tr) {
inorder(tr.right);
System.out.println();
}
static void inorder (IntTree tr) {
if (tr != null) {
inorder(tr.left);
System.out.print(" " + tr.node);
inorder(tr.right);
}
}
}
b04a001@AsiaA1:~/comp3b% java BinarySearchTree
6: 6
3: 3 6
5: 3 5 6
9: 3 5 6 9
2: 2 3 5 6 9
8: 2 3 5 6 8 9
7: 2 3 5 6 7 8 9
1: 1 2 3 5 6 7 8 9
7: 1 2 3 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
最後に、以上の 3 種類の探索法を比較します。
探索と挿入を繰り返す場合は、二分探索木が優れています。
挿入が発生しない場合で、整列済みなら、二分探索です。
整列されていないなら線形探索ですが、
もし、非常に頻繁に探索するならば、
整列しておいてから二分探索することも考えられます。
探索法 探索時間 挿入時間
------------------------------------------------
線形探索 低速 瞬間
二分探索 高速 低速
二分探索木 高速 高速
h2 演習 10 toc-exercises
二分探索木を用いて整列を行うプログラムを作成してください。
すでに説明した通り、
二分探索木を中央順に走査しますと、節点の値が整列されて得られます。
したがって、最初に二分探索木を空にし、
整列したい要素を次々と二分探索木に挿入すれば、整列が行えます。
ただし、上記のプログラムのメソッド insert では、
すでに挿入されている値は二度と挿入されません。
これを、何度でも挿入できるように変更し、
乱数列など、値が重複する数列も整列できるようにしてください。
プログラムは穴埋めとします。
class TreeSelectionSort {
public static void main (String[] args) {
int i, v, MAX = 9;
IntTree tr = new IntTree(0, null, null);
for (i = 1; i <= MAX; i++) {
v = (int) (Math.random() * MAX) + 1;
insert(tr, v);
System.out.print(v + ":");
print(tr);
}
}
static void insert (IntTree tr, int v) {
???
}
static void print (IntTree tr) {
inorder(tr.right);
System.out.println();
}
static void inorder (IntTree tr) {
if (tr != null) {
inorder(tr.left);
System.out.print(" " + tr.node);
inorder(tr.right);
}
}
}
b04a001@AsiaA1:~/comp3b% java TreeSelectionSort
4: 4
4: 4 4
9: 4 4 9
3: 3 4 4 9
6: 3 4 4 6 9
4: 3 4 4 4 6 9
6: 3 4 4 4 6 6 9
5: 3 4 4 4 5 6 6 9
5: 3 4 4 4 5 5 6 6 9
b04a001@AsiaA1:~/comp3b%
今日の演習10の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（12月3日）を明記してください。