第9回 優先度つき待ち行列，ヒープ，二分探索木

Presentation on theme: "第9回 優先度つき待ち行列，ヒープ，二分探索木"— Presentation transcript:

1 第9回 優先度つき待ち行列，ヒープ，二分探索木
データ構造とアルゴリズム 第9回 優先度つき待ち行列，ヒープ，二分探索木

2 (問1)解答 (チェイン法) 23 mod 5 = 3 48 mod 5 = 3 35 mod 5 = 0 4 mod 5 = 4
ポインタの配列 連結リスト 10 35 table[0] table[1] NULLの ところは斜線 バケット数 5の ハッシュ表 table[2] 48 23 table[3] table[4] 4

3 (問1)なぜ先頭に挿入するの？ f c a g b c a f g b 挿入位置の計算O(1) 先頭への挿入なら一定時間でできる
table [0] c a [1] 先頭への挿入なら一定時間でできる g b [2] 挿入位置の計算O(n) 末尾はどこ？ table [0] c a f [1] g b [2]

4 (問2)解答オープンアドレス法 ハッシュ関数 h(x)= x mod 5 再ハッシュ hi (x)= (h(x)+i) mod 5
図示に必要な 配列の長さは５！ Table[0]～table[5]まで 描いた人が結構いた!! ハッシュ関数 h(x)= x mod 5 再ハッシュ hi (x)= (h(x)+i) mod 5 h(23) = 23 mod 5 = 3 h(48) = 48 mod 5 = 3 再 h1(48)=(h(48)+1) mod 5 = 4 mod 5 = 4 h(35) = 35 mod 5 = 0 h( 4) = 4 mod 5 = 4 再 h1(4)= (h(4)+1) mod 5 = 5 mod 5 = 0 再 h2(4)= (h(4)+2) mod 5 = 6 mod 5 = 1 h(10) = 10 mod 5 = 0 再 h1(10)= (h(10)+1) mod 5 = 1 mod 5 = 1 再 h2(10)= (h(10)+2) mod 5 = 2 mod 5 = 2 バケット数 5の ハッシュ表 配列 35 table[0] 4 table[1] 10 table[2] 23 table[3] 48 table[4]

5 本日の内容 優先度つき待ち行列 半順序木，ヒープ 二分探索木

6 集合 A4 A1 A2 A3 集合 Ai A ： 集合の要素 要素の重複は無い ×{1, 4, 1}
探索の「キー」は，必ず 重複しない(ユニークなID) ⇒　集合の要素 要素の重複は無い　　　　　×{1, 4, 1} 要素を並べる順序は不問　○{1, 4}　{4, 1}

7 Pr ： 優先度(Priority) のある要素
順序つき集合 集合Aの要素間に全順序が定義されているもの 以後の説明では、同じ要素を複数個もつことを許す多重集合を考えるものとする Pr4 Pr1 Pr2 Pr3 順序つき集合 Pri Pr　：　優先度(Priority)　のある要素

8 順序つき集合の操作 集合の基本的操作の他に以下の操作がよく行われる MIN(A)：A≠φならば、≦に関し最小の要素を返す
順序つき集合の操作　　 集合の基本的操作の他に以下の操作がよく行われる MIN(A)：A≠φならば、≦に関し最小の要素を返す DELETEMIN（A): A≠φのとき最小の要素（複数個ある場合はその１つ）をAから取り除く 順序つき集合のデータ構造 優先度つき待ち行列：INSERT、DELETEMIN ２分探索木： INSERT、DELETE、MEMBER、MIN

9 優先度つき待ち行列の例　その１ 病院の待ち合い室 重症 優先 患者の集合

10 優先度つき待ち行列の例 その２ プロセスの集合 タイムシェアリングシステム中でサービスを待っているプロセス 時間 ｔ プロセスA プロセスB
優先度つき待ち行列の例　その２ タイムシェアリングシステム中でサービスを待っているプロセス 時間 ｔ プロセスA プロセスB プロセスC 経過時間の短いプロセスを優先して処理する プロセスの集合

11 DeleteMinの手順 １．根にあった３を削除　O (1) 3 5 9 6 8 9 10 10 18 9

12 DeleteMin, Insertの計算量 3 例 ８≦ｎ≦15の場合は 木の高さ：３ 半順序の回復に最悪でも 木の高さのステップ数かかる
根の削除(DeleteMin)　O (1)，要素の追加(Insert) O (1) 　 半順序の回復　O ( log2 n ) 3 例 ８≦ｎ≦15の場合は 木の高さ：３　 半順序の回復に最悪でも 木の高さのステップ数かかる (　　　　　　ステップ)

13 疑問 最小だけでなく最大も見つけるのに便利な方法はないだろうか？ 木を使って，その他の要素も効率よく探索するにはどうしたらよいだろう？

14 2分探索木の例 5 7 14 18 15 12 10 1 3 2 4

15 2分探索木の実現 5 7 14 18 10 15 12 10 5 14 7 12 18 15 left_child right_child
構造は2分木のときと同じ left_child right_child element 5 7 14 18 10 15 12 root 10 5 14 7 12 18 15 NODE型のセル

16 Member 10 5 14 7 12 18 15 ｘはＡの要素か？ Ａが空の木 → false ｘ＝Ａの根 → true
ｘ ＜ Ａの根　→　ｘは左部分木の要素か？ ｘ ＞ Ａの根　→　ｘは右部分木の要素か？ 5 14 7 12 18 15

17 Insert 10 5 14 7 12 18 15 ｘをＡに挿入する Ａが空の木 → Ａの根をｘとする ｘ＝Ａの根 → 挿入する必要なし
Ａが空の木　→　Ａの根をｘとする ｘ＝Ａの根　→　挿入する必要なし または２重登録として エラーとする ｘ ＜ Ａの根　→　ｘを左部分木に挿入 ｘ ＞ Ａの根　→　ｘを右部分木に挿入 5 14 7 12 18 15

18 Delete 10 5 14 7 12 18 15 ｘをＡから削除 ｘのある節点は葉 →その節点を指すポインタをNULLにする
ｘのある節点は子が一人 →ｘを削除し、その子をｘがいた節点に入れる ｘのある節点は子が二人 →ｘを根とする部分木において， 根を削除 右部分木の最小値，または，左部分木の最大値を根に入れる 5 14 7 12 18 15

19 左部分木の最大値と右部分木の最小値 Lmax ＜ ｘ ＜ Rmin x L R 右部分木の最小値 Rmin 左部分木の最大値 Lmax

20 ランダムな順番でデータを挿入し木を作ったと仮定すると
2分探索木操作の時間解析 探索の計算量は木の形状によって変化する 2 1 3 4 5 6 7 昇順にデータが挿入された場合 7 2 3 6 4 5 1 最良のパターン(完全2分木) O ( log n ) 最悪のパターン O ( n ) ランダムな順番でデータを挿入し木を作ったと仮定すると 平均の計算量　O (log n )

21 半順序木は優先度つき待ち行列の実現に適している．
半順序木との効率比較 半順序木 2分探索木 Insert DeleteMin O ( log n ) (平均，最悪とも) (最悪でO ( n )) Delete － Member O ( n ) 半順序木は優先度つき待ち行列の実現に適している． その他の操作の効率はよくない

22 本日の課題 (問1) 以下の数列は，半順序のついた２分木をヒープで表現したものである．この数列が表している木を描け．また，この木からDeleteMinを行った結果の木を描け． 数列　2, 7, 4, 9, 7, 4, 12, 10, 13, 11 数列が表わす木 DeleteMinの結果の木 (問2) 下図 (a) (b) は3要素｛1, 2, 3｝から成る5種類の2分探索木のうちの2種である．残りの3種を描け．また，それぞれ，行きがけ順，通りがけ順，帰りがけ順で走査した結果を示せ． ( c ) ( d ) ( e )