２分探索.

Presentation on theme: "２分探索."— Presentation transcript:

1 ２分探索

2 データ検索 検索： データの保持状態で検索処理の効率は変わるか？ ２つの状態では検索処理の効率の差はどの程度？
与えれたキー（探索キー）と等しいキーを、あるデータ集合の中から探す操作 データの保持状態で検索処理の効率は変わるか？ データがでたらめの順番で格納されている状態 データが予めソートされて格納されている状態　 ２つの状態では検索処理の効率の差はどの程度？ 単語がでたらめな順で並んでいる辞書での検索 単語が辞書式順で並んでいる辞書での検索

3 ２分探索法 10を検索 left left right right 1 ４ ７ １０ １１ １４ １８ ３ mid mid mid
10を発見

4 ２分探索法 5を検索 left left left right right 1 ４ ７ １０ １１ １４ １８ ３ mid mid mid
探索失敗

5 ２分探索木 ３ ２ ８ １４ １３ ５ １０ ２ ３ ５ ８ １０ １３ １４

6 ２分探索木 ８を探索 ８ ３ ２ ８ １４ １３ ５ １０ 8を発見

7 ２分探索木 ７を探索 ７ ３ ２ ８ １４ １３ ５ １０ 探索失敗

8 検索時間は木の高さに比例 バランスの悪い木 O(n) バランスの良い木 O(log n)

9 挿入（２分探索木） ７を挿入 ７ ５ ３ １３ ２ ８ １４ ７ １０

10 検索時間の期待値（２分探索木） … … … … 1,2,3,4,5 3,2,4,1,5 全ての順列を考える 1 2 3 4 1 2 計 10
１ 1 2 3 4 ２ ３ 1 2 … ２ ４ … ３ ４ １ ５ ５ 計 10 計 6 Dn = （各計の合計／ n!） = （「深さの合計」の平均） Tn = （Dn÷n） = 「深さの平均」の平均

11 検索時間の期待値（２分探索木） … … … … … … 1,2,3,4,5 ?,?,?,?,? 3,2,4,1,5 全ての順列を考える 1
１ 1 2 3 4 ２ ３ … … … ３ 1 1 ? ２ ４ ４ ５ 2 １ ５ 2 計 10 計 ? 計 6 Dn = （各計の合計／ n!） = （「深さの合計」の平均）は何に対応？ Tn = （Dn÷n） = 「深さの平均」の平均は何に対応？

12 検索時間の期待値（２分探索木） k 根が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 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) k－１頂点の木 各頂点の深さ の平均＝Tk－1 n－k頂点の木 の平均＝Tn－k

13 削除（内点の子を持たない場合） ４ ６ １０

14 削除（内点の子を１つ持つ場合） ９ ５ ２

15 削除（内点の子を２つ持つ場合） ２ ６ ４ １０ ９ ８ ７