アルゴリズムとデータ構造

(1)

アルゴリズムとデータ構造

第14週データ探索：木構造探索法

2014年1月16日金岡晃

(2)

授業計画

第1週 (9/26)

データ構造とアルゴリズムの基礎

第2週 (10/3)

アルゴリズムの効率、線形構造第3週

(10/10)

スタックと待ち行列第4週

(10/17)

文字列照合（KMP法、BM法）

第5週 (10/24)

木構造、木の走査

→文字列照合（BM法）、木構造

第6週 (10/31)

木の走査、二分木、決定木 第7週中間試験

第8週 (11/21)

休講第9週

(11/28)

グラフ構造と最短路問題第10週

(12/5)

解の探索：Aアルゴリズム第11週

(12/12)

データ整列：ヒープソート法

第12週 (12/19)

データ整列：クイックソート法

第13週 (1/9)

データ探索：ハッシュ法第14週

(1/16)

データ探索：木構造探索法

(3)

試験について

• 日時

– 2014 年 1 月 30 日（木） 3 限・ 4 限

• 形式

– 筆記試験

• 持ち込みあり

– PC の持ち込みも可

• この教室（ III 号館 204 ）で実施

• 時間

– 13:00-14:30 の 90 分

• 試験範囲

– 初回から今回までの配布資料と教科書内の該当する箇所

(4)

【復習】第 13 週

データ探索：ハッシュ法

アルゴリズムとデータ構造

(5)

単純な探索方法：線型探索と二分探索

線型探索

• 目的のキーを求めて表の先頭番地から順に調べていくもっとも単純な方法

• 逐次検索ともいわれる。

• 追加は効率的に行える（データの最後に追加する）が、探索と削除に時間がかかる追加：𝑂(1)

探索と削除：それぞれ𝑂(𝑛)

二分探索

• キーの値が昇順に並んでいるときに適用可能な手法

• 中央のキー（データが𝑛個ある場合は 𝑛 + 1 /2（の四捨五入か切り上げか切り捨て）番目のキー）との大小関係を調べる

• 一致なら探索終了

• 探索キーが大なら、後半の中での中央のキーを選択し、調べる

• 探索キーが小なら、前半の中での中央のキーを選択し、調べる

• 追加は効率的ではないが探索が効率的

追加：𝑂(𝑛)

探索：それぞれ𝑂(log 𝑛)

(6)

ハッシュ法

ハッシュ関数を用意し、キーを入力にしてハッシュ関数により得られた結果を番地として使う

衝突が起きた場合には対応が必要

• 空いている番地を探す：開番地法（開アドレス法）

• 衝突が起こったときに代わりの番地へのポインタを入れるようにする：連鎖法

開番地法の具体例：線型走査法（Linear Search）

• 得られた結果に一定の間隔𝑑を足し、空いているか確認し、空いていればその番地を使う

• 空いていない場合、間隔𝑑をさらに足すことを繰り返す

この手法での一定の間隔をハッシュ増分（Hash Increment）と呼ぶ

(7)

開番地法

線型走査法（Linear Search）

• 得られた結果に一定の間隔𝑑を足し、空いているか確認し、空いていればその番地を使う

• 空いていない場合、間隔𝑑をさらに足すことを繰り返す

• この手法での一定の間隔をハッシュ増分（Hash Increment）と呼ぶ

• クラスタが発生する

ℎ

_𝑖

𝐾 = ℎ

₀

𝐾 + 𝑑𝑖 𝑚𝑜𝑑 𝑁

2次走査（Quadratic Search）法

• クラスタの発生を抑える

ℎ

_𝑖

𝐾 = ℎ

₀

𝐾 + 𝑎𝑖 + 𝑏𝑖

²

𝑚𝑜𝑑 𝑁

(8)

連鎖法

• キーKの番地を調べるときにh0(K)にすでにほかのキーが入っている場合、同じ値を持つキーが次にどこに入っているかの番地（ポインタ）を持つ

連鎖リスト

連合連鎖（Coalesced Chaining）法：

• 連鎖リストをたどって最後の要素を見つける

• 空き番地を見つけ、そこに格納

• 最後の要素のポインタ部に格納した番地を入れる

分離連鎖（Separate Chaining）法：

• 先に入っている同族でないキーを追い出してキーKを格納

• 同族が連鎖するようにする

• 追い出されたキーを空き番地に格納

(9)

演習

スライド「ハッシュ法：具体例」と同じデータを、同じく𝑁 = 11の表にハッシュ法を用いて格納するとする。この場合、以下の問に答えよ。

１）ハッシュ関数を以下とした場合の、ハッシュ表への格納状態（表）と、平均探索回数を求めよ

２）ハッシュ関数を以下とした場合の、ハッシュ表への格納状態（表）と、平均探索回数を求めよ

ℎ₀ 𝐾 = #𝐶1 × 26 + #𝐶2 𝑚𝑜𝑑 𝑁 ℎ_𝑖 𝐾 = ℎ₀ 𝐾 + 3𝑖 𝑚𝑜𝑑 𝑁

ℎ₀ 𝐾 = #𝐶1 × 26 + #𝐶2 𝑚𝑜𝑑 𝑁 ℎ_𝑖 𝐾 = ℎ₀ 𝐾 + 𝑖 + 𝑖² 𝑚𝑜𝑑 𝑁

(10)

第 14 週

データ探索：木構造探索法

アルゴリズムとデータ構造

(11)

本日の到達目標と概要

• 到達目標

– データ探索における木構造探索法の理解

• 概要

– 二分木探索法 – 平衡二分木 – AVL 木

– B 木

– 桁探索木

(12)

二分木探索法

• 各節に1つのキーを格納

• 節の左部分木にはその節のキーよりも小さい値のキーを格納

• 節の右部分木にはその節のキーよりも大きい値のキーを格納 60, 30, 75, 45 ,15 ,90

というキーを順に格納

キーの削除：

• 削除したいキー𝐾の検索

• 𝐾が葉であれば即座に消去

• 𝐾が節であれば直前あるいは直後の大きさのキーを𝐾の節に持ってくる

(13)

平衡二分木

二分探索木の問題点：

登録順序により木の形状が大きくかわる

60, 30, 75, 45 ,15 ,90

というキーを順に格納する場合 90, 75, 15, 60 30, 45

というキーを順に格納する場合節のレベル＝探索時に木のポインタをたどる回数

平衡係数（Balance Factor）

• 二分木の任意の節での、(左部分木の高さ-右部分木の高さ）の値

• どの節においても平衡係数がある一定の範囲に収まっている場合、高さ平衡二分木（Height Balanced Binary Tree）あるいは単に平衡二分木という

(14)

AVL 木

• G Adelson-VelskiiとY.Landisの２人により提案された

• キーを追加していく過程で、平衡性が破れたら直ちに二分木の構造を手直ししてつねに平衡性を維持できるような機構を備える

(15)

AVL 木

単回転（Single Rotation）と複回転（Double Rotation）

• 節Aを根の方向に移動し、それに押し出されるように節Pを節Aの右の子に移動する操作

• 単回転を２回行うことを複回転と言う

(16)

B 木

• R. BayerとE. McCreightにより提案された順序付き多進木

• 定義

• 根以外の節には、 𝑚個以上、 2𝑚個以下のキーが格納される。それらのキー（ 𝑛個とする）を𝑎 1 , 𝑎 2 , 𝑎 3 , ⋯ , 𝑎[𝑛]とする。

• 根には１個以上2𝑚個以下のキーが格納される

• 葉はすべて同一レベルにある

• 葉以外の節には、部分木へのポインタが𝑛 + 1個ある。これらのポインタを𝑝 0 , 𝑝 1 , ⋯ , 𝑝 𝑛 とする。

• 任意の節において、キー列𝑎 1 , 𝑎 2 , 𝑎 3 , ⋯ , 𝑎[𝑛]は昇順に整列している。また、葉以外の任意の節について、キー𝑎 𝑖 の大きさは、 𝑝 𝑖 − 1 の指す部分木内のどのキーよりも大きく、 𝑝 𝑖 の指す部分木内のどのキーよりも小さい 1 ≤ 𝑖 ≤ 𝑛

(17)

B 木の構成

(18)

B 木：キー追加

キー45の追加（単純追加の場合）

キー20の追加（分割による場合）

(19)

B 木：キー削除（１）

キー15の削除（単純削除の場合）

キー32の削除（アンダーフローによる場合）

(20)

B 木：キー削除（２）

キー70の削除（連結による場合）

(21)

桁探索（ Digital Search ）木

• 目的のキーを構成している英数字やビット（桁）を順に見つつ、分岐先を判断しながら探索や格納を進めていく方法

(22)

桁探索木：トライ

• キーを格納するのは葉のみに限定し、内部節には桁に関する分岐情報のみを保持するようにしたもの

(23)

演習問題

下図のような2次のB木があるものとする。これに、まずキー50を追加し、その後、

キー10を削除し、さらにその後にキー43を削除するものとする。それぞれの処理が終わった直後のB木を図示せよ。