二分探索木の平均計算量(WIP)

二分探索木の形は、要素の数が同じでも、入れる順番によって変わる。
探索に必要な比較の回数も、木の形によって変化する。

1,2,3

  • 要素1を探すときの比較回数は1
  • 要素2を探すときの比較回数は2
  • 要素3を探すときの比較回数は3
  • 平均比較回数は(1+2+3)/3=2

2,1,3

  • 要素1を探すときの比較回数は2
  • 要素2を探すときの比較回数は1
  • 要素3を探すときの比較回数は2
  • 平均比較回数は(2+1+2)/3=1.7

要素n個に対して作れる木の形がxパターンあるとする。
それぞれの木の形T1~Txに対して平均比較回数が求まる。
それらの平均比較回数の平均をT(n)とする。

T(n)をnの関数として表すことはまだできない。
なぜなら木の形から平均比較回数を算出する方法が曖昧だから。
nからxを求める方法がわからないし、木の形(どうやって数学的に表現する!?)から平均比較回数を算出する一般的な方法もまだない。

問題を分割する…

では木の形から平均比較回数を計算する方法を考える。
上でやったように、ひとつひとつの要素に対して何回の比較で到達できるかを求め、その平均を出せばよい。
ここで、木の形を抽象化する。

あらゆる二分探索木は、親と左部分木と右部分木に抽象化できる。

木の形も抽象化する。
つまり、n個の要素からなる二分探索木を、左部分木の要素数(0~n-1)によってn通りに分類する。
部分木の中の形はわからないんだけど、今はわからなくていい。

左の部分木の要素数をiとする。
i=1のとき、この部分木は、親要素があり、左部分木には1つだけ要素があり、右部分木には形はわからないけどn-2個の要素が入っている。そういう木の形をしている。
実はそれだけわかれば、この木の平均比較回数はT(n)を用いて表せる。
繰り返すが、T(n)がどういう関数なのかはまだわかってない。でもT(n)を用いて表す方法はあるということだ。
それはこうなる
(略)

n個の要素を適当な順番で木に挿入したとき、木がどんな形になるかはわからない。
つまりiがどんな値になるかはわからない。
でもここでiは0からn-1まで同じ確率で現れると考える(本当???)と、平均値は求められる。
この平均値というのは、つまりn個の要素からなる二分探索木の平均比較回数だ。つまりT(n)だ。
T(n)をT(n)で表す式ができた。

コメントを残す

メールアドレスが公開されることはありません。