２分探索
データ検索
• 検索：
– 与えれたキー（探索キー）と等しいキーを、あるデータ集合
の中から探す操作
• データの保持状態で検索処理の効率は変わるか？
– データがでたらめの順番で格納されている状態
– データが予めソートされて格納されている状態
• ２つの状態では検索処理の効率の差はどの程度？
– 単語がでたらめな順で並んでいる辞書での検索
– 単語が辞書式順で並んでいる辞書での検索
２分探索法
10を検索
left right
left
1
３
４
７
right
１０ １１ １４ １８
mid mid mid
10を発見
２分探索法
5を検索
left
left right
left
1
３
４
right
７
１０ １１ １４ １８
mid mid mid
探索失敗
２分探索木
５
３
１３
２
８
１４
１０
２
３
５
８
１０
１３
１４
２分探索木
８を探索
８
５
３
２
１３
８
8を発見
１４
１０
２分探索木
７を探索
７
５
３
１３
２
８
１４
１０
探索失敗
検索時間は木の高さに比例
O(log n)
バランスの良い木
O(n)
バランスの悪い木
挿入（２分探索木）
７を挿入
７
５
３
１３
２
８
７
１４
１０
検索時間の期待値（２分探索木）
全ての順列を考える
1,2,3,4,5
…
…
3,2,4,1,5
１
0 ２
1 ３
2 ４
3 ５
4
計 10
３
0
…
２
４
1
1
…
１
５
2
2
計6
Dn = （各計の合計／ n!） = （「深さの合計」の平均）
Tn = （Dn÷n） = 「深さの平均」の平均
検索時間の期待値（２分探索木）
全ての順列を考える
1,2,3,4,5
…
?,?,?,?,?
…
3,2,4,1,5
…
１
0 ２
1 ３
2 ４
3 ５
4
計 10
0 ３
…
?
…
1２
４1
2１
計?
…
５ 2
計6
Dn = （各計の合計／ n!） = （「深さの合計」の平均）は何に対応？
Tn = （Dn÷n） = 「深さの平均」の平均は何に対応？
検索時間の期待値（２分探索木）
根がkの場合を考える
k
• k－１頂点の木
• 各頂点の深さ
の平均＝Tk－1
• n－k頂点の木
• 各頂点の深さ
の平均＝Tn－k
根がkの場合の深さの総和
= （k－1)(1+ Tk－1) + 0 +
（n－k)(1+ Tn－k)
= (n－1) + （k－1)Tk－1
+ （n－k)Tn－k
= (n－1) +Dk－1 + Dn－k
kは1～nまで動くのでそれの平均
Dn
= ∑1≦k≦n (n－1 +Dk－1 + Dn－k ) /n
= n－1 + (2/n)∑1≦k≦n-1 Dk
= 2(n+1) (Hn+1－2)+2 （演習問題5．6）
⇒ Tn = O(log n)
削除（内点の子を持たない場合）
４
６
１０
削除（内点の子を１つ持つ場合）
９
５
２
削除（内点の子を２つ持つ場合）
２
６
１０
４
９
８
７