スライド タイトルなし

データ構造とアルゴリズム
第9回
優先度つき待ち行列,ヒープ,二分探索木
1
(問1)解答 (チェイン法)
23 mod 5 = 3
48 mod 5 = 3
35 mod 5 = 0
4 mod 5 = 4
10 mod 5 = 0
ポインタの配列
table[0]
連結リスト
10
35
table[1]
バケット数 5の
ハッシュ表
NULLの
ところは斜線
table[2]
table[3]
48
table[4]
4
23
2
(問1)なぜ先頭に挿入するの?
table
挿入位置の計算O(1)
f
c
[0]
[1]
[2]
a
先頭への挿入なら一定時間でできる
g
b
挿入位置の計算O(n)
末尾はどこ?
table
[0]
c
a
g
b
f
[1]
[2]
3
(問2)解答オープンアドレス法


ハッシュ関数 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!
Table[0]~table[5]まで
描いた人が結構いた!!
バケット数 5の
ハッシュ表
配列
table[0]
35
table[1]
4
table[2]
10
table[3]
23
table[4]
48
4
本日の内容

優先度つき待ち行列

半順序木,ヒープ

二分探索木
5
集合
A4
A1
A3
Ai
A : 集合の要素


A2
集合
探索の「キー」は,必ず
重複しない(ユニークなID)
⇒ 集合の要素
要素の重複は無い
×{1, 4, 1}
要素を並べる順序は不問 ○{1, 4} {4, 1}
6
順序つき集合

集合Aの要素間に全順序が定義されているもの
Pr4
Pr1
Pr3
Pr :

Pri
Pr2
順序つき集合
のある要素
以後の説明では、同じ要素を複数個もつことを許す多重集合
を考えるものとする
9
順序つき集合の操作




集合の基本的操作の他に以下の操作がよく行われ
る
MIN(A):A≠φならば、≦に関し最小の要素を返す
DELETEMIN(A): A≠φのとき最小の要素(複数個あ
る場合はその1つ)をAから取り除く
順序つき集合のデータ構造


優先度つき待ち行列:
2分探索木:
10
優先度つき待ち行列の例 その1
病院の待ち合い室
重症
優先
患者の集合
11
優先度つき待ち行列の例 その2
タイムシェアリングシステム中でサービスを待っているプロセス
時間 t
プロセスA
プロセスB
プロセスC
プロセスの集合
経過時間の短いプロセスを優
先して処理する
12
DeleteMinの手順
1.根にあった3を削除
3
5
9
6
10
8
18
9
10
9
18
DeleteMin, Insertの計算量


根の削除(DeleteMin) O (1),
要素の追加(Insert) O (1)
半順序の回復 O ( log2 n )
3
例
8≦n≦15の場合は
木の高さ:3  log2 8
半順序の回復に
( log2 n ステップ)
かかる
22
疑問


最小だけでなく最大も見つけるのに便利な方法
はないだろうか?
木を使って,その他の要素も効率よく探索するに
はどうしたらよいだろう?
27
2分探索木の例
15
14
18
1
2
5
3
10
4
7
12
31
2分探索木の実現
構造は2分木のときと同じ
left_child
element
right_child
10
10
root
5
5
14
7
12
NODE型のセル
14
7 12
18
18
15
15
32
Member
10
xはAの要素か?
5




Aが空の木 → false
x = Aの根 → true
→ xは
→ xは
14
7 12
要素か?
要素か?
18
15
33
Insert
10
xをAに挿入する
5




Aが空の木 → Aの根をxとする
x=Aの根 → 挿入する必要なし
7
または2重登録として
エラーとする
→ xを
に挿入
→ xを
に挿入
14
12
18
15
34
Delete
xをAから削除
 xのある節点は葉
→

10
5
14
にする
xのある節点は子が一人
7 12
18
→

15
xのある節点は子が二人
→xを根とする部分木において,
 根を削除
を

根に入れる
36
左部分木の最大値と右部分木の最小値
Lmax < x < Rmin
x
L
R
37
2分探索木操作の時間解析

探索の計算量は木の形状によって変化する
1
4
2
1
6
3
5
7
最良のパターン(完全2分木)
2
昇順にデータが
挿入された場合
3
4
5
6
最悪のパターン
7
ランダムな順番でデータを挿入し木を作ったと仮定すると
平均の計算量 O (log n )
39
半順序木との効率比較
半順序木
2分探索木
Insert
DeleteMin
(平均,最悪とも)
(最悪でO ( n ))
Delete
-
Member
半順序木は優先度つき待ち行列の
実現に適している.
その他の操作の効率はよくない
41
本日の課題
(問1) 以下の数列は,半順序のついた2分木をヒープで表現したもので
ある.この数列が表している木を描け.また,この木からDeleteMinを
行った結果の木を描け.
数列 2, 7, 4, 9, 7, 4, 12, 10, 13, 11
数列が表わす木
DeleteMinの結果の木
(問2) 下図 (a) (b) は3要素{1, 2, 3}から成る5種類の2分探索木の
うちの2種である.残りの3種を描け.また,それぞれ,行きがけ順,通
りがけ順,帰りがけ順で走査した結果を示せ.
1
3
2
2
3
1
(a)
( c )
(b)
( d )
( e )
42