【アルゴリズム】2文探索木の探索及び計算量についてのあれこれ

2019年4月23日

プログラミング系列サムネイル画像1

こんにちは。行未です。

LaTexの練習も兼ねて。 2文探索木での探索の計算量まとめです。

本題に入りましょう。

2分探索木の他に計算量でよく挙げられる例としては、各種ソート(バブルソートとかクイックソート等)があるのですが、こちらについては後日まとめたいと思います。
特にクイックソートの平均計算量なんかは、私の数学力では腰据えて割とゴリゴリやらないと厳しそうでした。

拙いまとめで恐縮ですが、
「ここ間違えてる」とか、「他にもこういう考え方があるよー」等意見があればぜひ頂けますと幸いです。

そもそも2分探索木とは

2分探索木は、2分木の各節にデータをもたせ、2分木の性質を利用して探索を行うことのできる木です。
「木」はデータ構造の1つです。

「木」というデータ群に対して、欲しいデータを探索するわけです。

尚、葉以外の節が全て2つの子を持っており、根から葉までの深さが全て等しい木を完全2分木と言います。

完全2分木イメージ画像
完全2分木

更に、今回のテーマでもある2文探索木の計算量は、

その木の深さに依存します。

完全2分木の最大探索比較回数

完全2分木は前述した通り、「葉以外の節が全て2つの子を持っており、根から葉までの深さが全て等しい木」です。

この完全2分木に対して探索を行うとき、最大で何回比較を行うかを考えます。

上の完全2分木の画像の例でいえば、「6,8,16,18」を探すということです。

まず、ゴールを考えると、最後の到達点(葉)についたとき、その要素数は1です。

次に要素数を\(n\)、探索数を\(s\)とします。

そして、探索範囲は探索を1回行う毎に、比較対象が\(\frac{1}{2}\)で狭まります。
\(s\)回探索を行うとすると、 \(\frac{1}{2^s}\) で狭まります。
以上をまとめると、

$$\frac{n}{2^s}=1$$

となります。
上式について式整理を行い、sを求めます。

$$ \begin{eqnarray*}
n&=&{2^s}\\
\log_2 n&=&\log_2 {2^s}\\
\log_2 n &=&s
\end{eqnarray*}$$

探索木の最悪計算量

次に、一番めんどくさいパターンの木を考えます。

結論から言えば、最悪計算量は\(n\)です。

木のデータ構造に限らずですが、探索を行う場合、探索毎に探索範囲が狭まるとありがたいのです。

逆に言うと、探索範囲が狭まらない木が厄介だということです。

ではその木とは何か。

何も分かれていない木です。

最悪計算量となる木のイメージ画像1
(1)最悪計算量となる木の例
最悪計算量となる木のイメージ画像2
(2)最悪計算量となる木の例

このような木に対しては、探索を行っても探索範囲が狭まることはありません。

結局要素数分の探索を行うため、最悪計算量は \(n\) となります。