２分探索
データ検索 検索： データの保持状態で検索処理の効率は変わるか？ ２つの状態では検索処理の効率の差はどの程度？ 与えれたキー（探索キー）と等しいキーを、あるデータ集合の中から探す操作 データの保持状態で検索処理の効率は変わるか？ データがでたらめの順番で格納されている状態 データが予めソートされて格納されている状態 ２つの状態では検索処理の効率の差はどの程度？ 単語がでたらめな順で並んでいる辞書での検索 単語が辞書式順で並んでいる辞書での検索
２分探索法 10を検索 left left right right 1 ４ ７ １０ １１ １４ １８ ３ mid mid mid 10を発見
２分探索法 5を検索 left left left right right 1 ４ ７ １０ １１ １４ １８ ３ mid mid mid 探索失敗
２分探索木 ３ ２ ８ １４ １３ ５ １０ ２ ３ ５ ８ １０ １３ １４
２分探索木 ８を探索 ８ ３ ２ ８ １４ １３ ５ １０ 8を発見
２分探索木 ７を探索 ７ ３ ２ ８ １４ １３ ５ １０ 探索失敗
検索時間は木の高さに比例 バランスの悪い木 O(n) バランスの良い木 O(log n)
挿入（２分探索木） ７を挿入 ７ ５ ３ １３ ２ ８ １４ ７ １０
検索時間の期待値（２分探索木） … … … … 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） = 「深さの平均」の平均
検索時間の期待値（２分探索木） … … … … … … 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） = 「深さの平均」の平均は何に対応？
検索時間の期待値（２分探索木） 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
削除（内点の子を持たない場合） ４ ６ １０
削除（内点の子を１つ持つ場合） ９ ５ ２
削除（内点の子を２つ持つ場合） ２ ６ ４ １０ ９ ８ ７