アルゴリズムA 第10回


探索

たくさんのデータの中から、ある特定の値を持つデータを探しだす操作のこと。 探索するためには、

という操作が必要になります。

線形探索と二分探索

この講義の第1回と第2回で学びました。

線形探索法はデータがどういう順番で並んでいても構わないのですが、 二分探索法はデータがソート済みの状態である必要がありました。

1回あたりの計算量線形探索法二分探索法
挿入O(1)O(n)
探索O(n)O(log n)
削除O(n)O(n)

二分探索木 (Binary Search Tree)

二分木の各節にデータを持たせたもので

任意の節 x について、左部分木に含まれる要素は節xよりも小さく、 右部分木に含まれる要素は節xよりも大きい、
という制約を持つ。

あるデータの集合を表す二分探索木はいくつも存在する。

        13                      6
      +--+--+                 +-+------+
      5     21                5        21
    +-+-+ +-+               +-+      +-+
    2   7 15                2        15
      +-+                          +-+
      6                            13
                                 +-+
                                 7

Javaにおいては、データが大小比較可能なオブジェクトである場合は Comparable インターフェイスを実装しており、 int compareTo(Object) メソッドを持ちます。 このメソッドの返り値は以下の意味を持ちます。

以下に示すJavaプログラムは教科書と同様に、データもキーも Integerオブジェクトとしていますのでこのメソッドを使って 大小比較しています。

2分木探索のプログラム

BinarySearchTreeクラスを作成し、 探索、挿入、削除に関してそれぞれ メソッドを用意すると、次のようになる。

基本は「keyがノードより小さければ左部分木へ、大きければ右部分木へ」 と処理をする。 左右両方の部分木をもつノードの削除だけが少し考え方が難しいが、 「『右部分木の最小のもの』(これは、『削除するノードの次に大きいノード』 を意味する)を探してきて、削除するノードと置き換え」ればよい。 もちろん、 「『左部分木の最大のもの』(これは、『削除するノードの次に小さいノード』 を意味する)を探してきて、削除するノードと置き換え」ても構わないのだが。

BinarySearchNode.java
授業で配布するプリントを参照して下さい。
BinarySearchTree.java
授業で配布するプリントを参照して下さい。
TestBinarySearchTree.java
授業で配布するプリントを参照して下さい。
TestBinarySearchTree.javaの実行例
% javac TestBinarySearchTree.java
% java TestBinarySearchTree
 2  3  4  5  6  7  8 
 2  3  4  5  6  7 
 2  3  4  5  7 
 2  3  4  5 
 2  4  5 

二分探索木においては、根から節までの経路長の平均は最良だと O(log n) となるが、最悪だと O(n) になるので注意が必要である。(大きい順に、または、小さい順に挿入が起きた場合が最悪)

→平衡木 (AVL木、B Tree など) では、挿入・削除が行われるたびに 木の形を見直して、高さが log2n 程度に収まるように 変形する。



アルゴリズムA 演習


課題提出〆切は次回の講義の開始時刻です。

課題10a

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai10a
提出ファイルBinarySearchTree.java
コメント欄:

BinarySearchTree.java の欠けている部分を自分でコードを書きなさい。

課題10b

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai10b
提出ファイルBinarySearchTree.java
コメント欄:RunBinarySearchTree.javaにbsearch01.txtを入力として与えた時の出力

前回のサンプルプログラムのように、木構造を正しく表示する prettyPrint() メソッドを BinarySearchTree.java に追加しなさい。

RunBinarySearchTree.java
授業で配布するプリントを参照して下さい。
bsearch01.txt
insert 7
insert 3
insert 11
insert 5
insert 2
insert 9
insert 15
insert 13
insert 1
insert 6
show
delete 2
show 
delete 5
show
delete 11
show
RunBinarySearchTree.javaの実行例
% javac RunBinarySearchTree.java
% java RunBinarySearchTree < bsearch01.txt
      null
    15
        null
      13
        null
  11
      null
    9
      null
7
        null
      6
        null
    5
      null
  3
      null
    2
        null
      1
        null

---------
...(略)