アルゴリズム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

public class BinarySearchTree {
    private BinarySearchNode root;		// 二分探索木の根
    public BinarySearchTree() { // コンストラクタ
	root = null;
    }
    public BinarySearchNode search(Integer key) { // 探索する
	BinarySearchNode p = root;		// 根から探索開始する
	while (p != null) {
	    int result = key.compareTo(p.data);	// key と p.data を比較して
	    if (result == 0) {	// key == p.data の場合

		// 自分でコードを書きなさい	// 発見した

	    } else if (result < 0) { // key < p.data の場合
		p = p.left;	// 左部分木に進む
	    } else {		// key >  p.data の場合

		// 自分でコードを書きなさい	// 右部分木に進む

	    }
	}
	return null;		// 発見できなかった
    }
    public BinarySearchNode insert(Integer key) { // 挿入する
	BinarySearchNode p = root;		// まず根に注目する
	BinarySearchNode parent = null;	// 注目しているノードの親ノード
	boolean isLeftChild=false; //pがparentの左のでtrue,右の子でfalse
	while (p != null) {
	    int result = key.compareTo(p.data);	// keyとp.dataを比較して
	    if (result == 0) {	// key == p.data の場合
		return null;	// 既に登録済み
	    } else if (result < 0) { // key < p.data の場合

		// 自分でコードを書きなさい

	    } else {		// key > p.data の場合
		parent = p;
		isLeftChild = false;
		p = p.right;
	    }
	}
	// parentの下に新しいノードを登録する。
	//右か左かはisLeftChildで判断する
	// 新ノードを生成する。
	BinarySearchNode newNode = new BinarySearchNode(key);
	if (parent == null) {	// 1個もノードがない場合
	    root = newNode;	// 根として登録する
	} else if (isLeftChild) { // parentの左に登録する
	    parent.left = newNode;
	} else {		// parentの右に登録する
	    parent.right = newNode;
	}
	return newNode;		// 新しく登録したノードを返す
    }
    public boolean delete(Integer key) { // 削除する
	BinarySearchNode p = root;		// まず根に注目する
	BinarySearchNode parent = null;	// 現在注目しているノードpの親ノード
	boolean isLeftChild = false;
	while (p != null) {
	    int result = key.compareTo(p.data);	// keyとp.dataを比較する
	    if (result==0) {	// 発見
		if (p.left==null && p.right==null) { // pが葉ノードである場合
		    if (parent == null) root=null;
		    else if (isLeftChild) parent.left = null;
		    else parent.right = null;
		} else if (p.left == null) { // 右部分木だけ存在する場合
		    // 右の子で置き換える
		    if (parent == null) root = p.right;

		    // 自分でコードを書きなさい

		} else if (p.right == null) { // 左部分木だけ存在する場合
		    // 左の子で置き換える
		    if (parent == null) root = p.left;

		    // 自分でコードを書きなさい

		} else {	// 右部分木も左部分木も存在する場合
		    // 右部分木の最小ノードを取り出す
		    BinarySearchNode x = deleteMin(p);
		    // 削除するノードpの替りに入れる
		    if (parent == null) root = x;
		    else if (isLeftChild) parent.left = x;
		    else parent.right = x;
		    x.right = p.right;
		    x.left = p.left;
		}
		return true;	// 削除が成功した
	    } else if (result < 0) { // key < p.data の場合
		parent = p;
		isLeftChild = true;
		p = p.left;
	    } else {		// key > p.data の場合
		parent = p;
		isLeftChild = false;
		p = p.right;
	    }
	}
	return false;		// 削除対象を発見できなかった
    }
    private BinarySearchNode deleteMin(BinarySearchNode parent) {
	BinarySearchNode p = parent.right; // pはparent.rightである
	boolean isLeftChild = false;
	while (p.left != null) {

	    // 自分でコードを書きなさい

	}
	if (isLeftChild == false) { // 与えられたpがいきなり最小の場合
	    parent.right = p.right;
	} else {
	    parent.left = p.right;
	}
	return p;		// 最小のノードを返す
    }
    public String toString() { return inorder(root); }
    private String inorder(BinarySearchNode p) {
	if (p == null) return "";
	return inorder(p.left) + " " + p.data + " " + inorder(p.right);
    }
}
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

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