アルゴリズムとデータ構造1 2006年7月3日酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html 配列上の探索添え字を用いて直接アクセス先頭から順に調べる直接探索線形探索 public class Array { public Array(int aMaxSize) { this.array = new String[aMaxSize]; this.number = 0; } } public int search(String aTarget) { for(int count = 0; count < this.number; count++){ if(aTarget.equals(this.array[count])){ return count + 1; } } return -1; } private String[] array; 配列の要素が尽きたかどうかの判定 private int number; 目的のデータであるかどうかの判定１つのデータを探すのに2回も判定番兵 • 計算量は減らないが、実行時間は減る • アルゴリズムではなくテクニックのひとつ • 線形探索では番兵を最後尾に置く – 線形探索における番兵では、探索したいデータと等しい値のデータを用いることが多い – 探索は目的のデータか番兵いずれかの発見で終了 – 探索対象が無くなったかどうかの判定が不要になる • 番兵は最も後に探索され、そして必ず一致する public class Array { public Array(int aMaxSize) { this.array = new String[aMaxSize+1]; this.number = 0; } } public int search(String aTarget) { int count=0; これが番兵 this.array[this.number] = aTarget; while( !aTarget.equals(this.array[count]) ){ count++; } if(count != this.number){ return count + 1; } 配列の要素が尽きたかどうかの判定 return -1; 目的のデータであるかどうかの判定 } private String[] array; 配列の要素が尽きたかどうかの判定 private int number; を最後に1回だけにした二分探索ノード数をNとすると O(log N) の計算量で探索できる 29 20 木が偏っているときは最悪O(N)になるが… 14 7 32 24 19 21 30 48 31 public class BinarySearchTree { public BinarySearchTree() { this.root = null; public MyNode search(MyData aData) } { private MyNode root; if(null == this.root){ } return null; } MyNode currentNode = this.root; while(true){ if(0 == currentNode.getData().compareTo(aData)){ return currentNode; } if(0 < currentNode.getData().compareTo(aData)){ if(null == currentNode.getLeft()){ return null; } currentNode = currentNode.getLeft(); }else{ if(null == currentNode.getRight()){ return null; } currentNode = currentNode.getRight(); } } } 最悪の形（二分探索木） 48 32 31 ノード数をNとすると O(log N) の計算量で探索できる 30 29 木が偏っているときは最悪O(N)になるが… 24 21 20 19 木の深さをバランスよくしたものを平衡木という 14 7 次は平衡木について述べる B木（B-tree） 二分木ではないが、探索用のｍ分木 いわゆる平衡木 順序木である B木を構成するためのルール 根から葉までの深さはどの葉についても同じである 各頂点（葉以外）の子の数は最大mである 各頂点（葉以外）の子の数は最小である  は切り上げを意味する記号である 根は例外で、最小2である頂点の構造頂点にはデータは置かない探索キーだけをおくキーは枝をたどるときの境目 B木の探索 途中の頂点にはデータは入ってない 入ってる値は部分枝の選択のためのキー値 データは葉の部分におかれている そうしない実装もある 根から部分木を選択しながら下降する 部分木の選択にはO(log m)必要 葉に達したら探索は終了 葉の値と一致すれば成功、そうでなければ失敗 B木の頂点に置く境界値 • 頂点に置かれる値は部分木選択に使われる • 境界値の条件は次の２つを満たす – 左に位置する部分木の最大値以上 – 右に位置する部分木の最小値以下 • 条件を満たす値は複数あるがどれでもいい境界値境界値の左部分木境界値の右部分木 29を探索 3を探索 44を探索 7 7以上31未満の数 7未満の数 3 0 22 6 3 31 6 7 31以上の数 29 22 49 29 31 - - 49 探索失敗 •未満, less than, より小さい •以上, greater than or equal to •以下, less than or equal to 新しいデータ（子）を追加するとき 1. 追加すべき位置（親の頂点）を決定します 2. 親の頂点に空きがあるか調べます 3. 空きがない場合は親の頂点を分割します親の親の頂点から新たに枝を増やします親が根である場合は、新たな根を親の親として増やします 4. 子を頂点に追加しますデータ（子）を削除するとき 1. 削除すべきデータを探索し、削除します 2. 親からの枝の本数が最少数を満たすかどうか調べます 3. 最少数に満たない場合は隣の頂点と子を按分します按分した結果最少数を満たせない場合は隣の頂点と併合します親が根である場合に最少数２を割ったら、根を削除します計算量の考察 • キー値の比較を1回行うと候補は半減する – 候補が半減する場合がもっとも効率が良い – 半減するようにデータを保持する • 例：平衡木を使う • ちょうど半分ずつ絞りこめばO(log N) • キーの比較という手法を使う限りはこれ以上探索の効率はよくならない。