データ構造とアルゴリズム
第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
図示に必要な
配列の長さは５！
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
Pri
Pr2
順序つき集合
Pr ： 優先度(Priority) のある要素
以後の説明では、同じ要素を複数個もつことを許す多重集合
を考えるものとする
9
順序つき集合の操作
集合の基本的操作の他に以下の操作がよく行われ
る
MIN(A)：A≠φならば、≦に関し最小の要素を返す
DELETEMIN（A): A≠φのとき最小の要素（複数個あ
る場合はその１つ）をAから取り除く
順序つき集合のデータ構造
優先度つき待ち行列：INSERT、DELETEMIN
２分探索木： INSERT、DELETE、MEMBER、MIN
10
優先度つき待ち行列の例 その１
病院の待ち合い室
重症
優先
患者の集合
11
優先度つき待ち行列の例 その２
タイムシェアリングシステム中でサービスを待っているプロセス
時間 ｔ
プロセスA
プロセスB
プロセスC
プロセスの集合
経過時間の短いプロセスを優
先して処理する
12
DeleteMinの手順
１．根にあった３を削除 O (1)
3
5
9
6
10
8
18
9
10
9
18
DeleteMin, Insertの計算量
根の削除(DeleteMin) O (1)，
要素の追加(Insert) O (1)
半順序の回復 O ( log2 n )
3
例
８≦ｎ≦15の場合は
木の高さ：３ 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
ｘはＡの要素か？
5
Ａが空の木 → false
ｘ＝Ａの根 → true
7
ｘ ＜ Ａの根 → ｘは左部分木の要素か？
ｘ ＞ Ａの根 → ｘは右部分木の要素か？
14
12
18
15
33
Insert
10
ｘをＡに挿入する
5
Ａが空の木 → Ａの根をｘとする
ｘ＝Ａの根 → 挿入する必要なし
7
または２重登録として
エラーとする
ｘ ＜ Ａの根 → ｘを左部分木に挿入
ｘ ＞ Ａの根 → ｘを右部分木に挿入
14
12
18
15
34
Delete
ｘをＡから削除
ｘのある節点は葉
10
5
14
→その節点を指すポインタをNULLにする
ｘのある節点は子が一人
7 12
18
→ｘを削除し、その子をｘがいた節点に入れる
ｘのある節点は子が二人
15
→ｘを根とする部分木において，
根を削除
右部分木の最小値，または，左部分木の最大値を
根に入れる
36
左部分木の最大値と右部分木の最小値
Lmax ＜ ｘ ＜ Rmin
x
L
R
右部分木の最小値 Rmin
左部分木の最大値 Lmax
37
2分探索木操作の時間解析
探索の計算量は木の形状によって変化する
1
4
2
1
6
3
5
7
最良のパターン(完全2分木)
O ( log n )
2
昇順にデータが
挿入された場合
3
4
5
6
最悪のパターン
O(n)
7
ランダムな順番でデータを挿入し木を作ったと仮定すると
平均の計算量 O (log n )
39
半順序木との効率比較
半順序木
2分探索木
O ( log n )
Insert
DeleteMin
(平均，最悪とも)
O ( log n )
(最悪でO ( n ))
Delete
－
O ( log n )
Member
O(n)
O ( log n )
半順序木は優先度つき待ち行列の
実現に適している．
その他の操作の効率はよくない
41
本日の課題
(問1) 以下の数列は，半順序のついた２分木をヒープで表現したもので
ある．この数列が表している木を描け．また，この木から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
© Copyright 2024 ExpyDoc
