講義計画

講義ノート

夜久竹夫

２００２．７．３１記

２００２．８．２７改定
２００２年９月９日改定

データ探索法

１．序論

レベル：基本情報処理技術者試験に準じる

２．二分探索木

２．１　二分探索木のアルゴリズム

２．２　二分探索木の実装

５．Ｂ木

３．１　Ｂ木

３．２　Ｂ木の実装

３．　ハッシュコード

３．１　チェイン法とオープンアドレス法

３．２　ハッシュコードの実装

４．深さ優先探索

４．１　深さ優先探索のアルゴリズム

４．２　深さ優先探索の実装

４．３　深さ優先探索の応用

５．　幅優先探索

５．１　幅優先探索のアルゴリズム

５．２　幅優先探索の実装

５．３　幅優先探索の応用

６．　最短経路探索

５．１　最短道のアルゴリズム

６．２　最短道アルゴリズムの実装

７．　データベース

７．１　データベースの分類

７．２　ＳＱＬ、標準形、

８．　まとめ

演習課題

（１）＜１０月第１週＞　二分探索木

（２）＜１０月末＞　Ｂ木

（３）＜１１月文化祭明け＞　ハッシュ法（チェイン法）（オープンアドレス法）

（４）＜１１月末＞　深さ優先探索

（５）＜年末＞　幅優先探索

（６）＜年明け＞　最短経路探索

（７）＜試験前＞　ＳＱＬ机上演習（例題）

１．序論

レベル：基本情報処理技術者試験に準じる

２．二分探索木

２分探索の利点を採用する手法

	平均値
探索	log n
作成	log n

２．１　二分探索木のアルゴリズム

探索

入力 x

出力 y hit

non hit

作成

入力 x (n data)

出力 T

２．２二分探索木の実装

５．Ｂ木

多分木

二分探索木の改良モデル：常にバランスするように

外部記憶装置で用いられる

最悪時間も log n となる

キー値

３．１　Ｂ木

最大m 個の子を持つ B-木

根は葉であるか、あるいは 2 – m 個の子を持つ

根と葉以外の節は、([m/2]- m 個の子を持つ

根からすべての葉までの経路の長さは等しい

k 個の子を持つ親は (k – 1 )個のキーをもっている

すべての葉は、同じレベルにあって、キー値をもたない。

３．２Ｂ木の実装

３．　ハッシュコード

ハッシュ法。２分探索と逐次探索の良いところを使う手法

目標

　　　　　　探索　　　作成

平均時間　　ｌｏｇｎ　　ｎ

方法

ハッシュ法の表：昇順が基本

（各データに対してあらかじめ格納場所が決められている）

（同じ場所に入るデータが複数あったら別の場所に格納する：その時の格納場所を決めるのがハッシュ関数）

ハッシュ値：ハッシュ関数により定められた格納場所

例

（１）作成

入力データ：数値、１＜ｘ＜１００

出力データ：配列　T(10)

データ構造：１から１０はT(1)。１１から２０はT(2)、。。。

hash(i) = (i-1) mod 10

11 と　12 が来たら、T(11)以降につなげる。

（２）探索

入力 y

T(100)

出力 not hit (if y not in T)

hit (if y in T)

方法

入力データ： 1, 23, 45, 24が来たら→

T	T(i)の内容
T(1)	1
T(2)	23
3
4	45
5
6
7
8
9
10
11	24

３．１　チェイン法とオープンアドレス法

衝突：ハッシュ関数の値が同じデータが現れる

衝突したデータの格納法の例→チェイン法とオープンアドレス法

（１）チェイン法

衝突したとき→リンクにより、本の番地につなげる

利点　元のハッシュ表がくずれていない

欠点データ構造が複雑になる

（２）オープンアドレス法

例：線形走査法

衝突したとき→後ろ側で一番近くで空いている場所に格納する。

利点元のハッシュ表のデータ構造が簡単

欠点ハッシュ表の順番がくずれる