2分探索木の計算量

『アルゴリズムとデータ構造』（石畑清） 2.4 2分探索木 (c) 計算量　より

2分探索木の平均計算量の計算式がよくわからなかったので頑張って自分なりに途中式を埋めてみました。

完全2分木のdと深さ

でもその前に、自分が地味に「？？？」となったところから備忘録として書いておきます。

完全2分木は$${2^d - 1(d=0,1,2,…)}$$の時しか作れない

『アルゴリズムとデータ構造』（石畑清）：以下すべての引用元

とあり、これを考えると
$${d=0}$$ のとき　データの個数は 0 
$${d=1}$$ のとき　データの個数は 1
$${d=2}$$ のとき　データの個数は 3
…
となるので根しかないときが$${d=1}$$と考えられます。なので「なるほど、根の高さのところが$${d=1}$$なんだな、その次の高さは$${d=2}$$なんだな」と思いながら読んでました。
これと、この後出てくる「深さ」の数値は一致してないので注意です。
根の深さは0です。
私は数式に具体的な数値を入れないといまいちイメージがつかない文系の人間なのでこのあたりで若干無駄な時間を食いましたｗ
では本題に入ります。

2分探索木の平均計算量

2分木探索の最善の場合（完全2分木）の計算量は$${O(\log n)}$$、最悪の場合（どの頂点にも子供が1つしかない）の計算量は$${O(n)}$$なのはそのままなので割愛。

この本で「平均」がどう定義されているかというと、

• $${n}$$個のデータを挿入する$${n!}$$通りの順序（順列）がそれぞれ等しい確率で起こると考える（＝挿入がランダムな順序に行われる）

• 探索は$${n}$$個のデータのいずれかを当確率で与えて行うものとする（＝見つかる場合だけを扱う）

となっています。つまりは$${n}$$個のデータの挿入パターンをすべて列挙して、その全パターンでの$${n}$$個のデータすべての探索されるときの計算量を算出して平均しよう、ということです。

探索数の平均

始めに定義されるものは
$${P_n}$$ : $${n}$$個のデータからなる木の探索の際に調べる頂点数の平均
ですが、これは例えば$${d=3}$$(深さ2)の位置にあるデータまで探索するときは
根→頂点→頂点 ( = 目標の頂点の深さに1を加えたもの)
で見つかるけど、すべての頂点の値が等確率で見つかるという前提なので、全頂点までの深さの平均を出して1を足せば平均探索数がわかるね、ということです。
そして、
$${T_n}$$ : 木の各頂点の深さの総和（を$${n!}$$通りの順列に関して平均したもの）
と定義されているので、これを計算式であらわすと

$${P_n = \dfrac{1}{n}T_n + 1}$$

となると言っています。この$${n!}$$通りの順列に関して平均したものが大事で、これは

挿入がランダムな順序に行なわれると考えた

のでこういう定義になってるのですね。

深さの総和（とあるkについて）

$${T_n}$$はどのように求めているのでしょうか？
$${n}$$個のデータのうち$${k}$$番目の大きさのものを始めに挿入した場合について考えると、

$$
(k - 1 + T_{k-1}) + 0 + (n - k + T_{n-k}) = n - 1 + T_{k-1} + T_{n-k}
$$

だと言っています。
つまり$${k}$$(番目の値)が根(=深さ0)ということです。
なので、根の左側の深さの総和が$${(k - 1 + T_{k-1})}$$で、右側の深さの総和が$${(n - k + T_{n-k})}$$ということですね。
日本語で表すと上の左辺の式は
{根の左側の深さの総和} + {根}(=0) + {根の右側の深さの総和}
となります。

具体的な数字で考えてみましょう。
$${n=15}$$, $${k=8}$$ としてみます。きれいに2つに分けてみました。
すると根の左側には$${k - 1 = 8 - 1= 7}$$個のデータがあります。
根の右側は$${n - k = 15 - 8 = 7}$$個のデータがあります。
$${T_{k-1}}$$や$${T_{n-k}}$$も同じ考え方ですね。
つまりはこの場合はどちらも$${T_7}$$が根の左（右）の子までの深さの総和です。すべての頂点に+1をしないと根までの深さがでないので、それぞれ$${k - 1}$$, $${n - k}$$(=7=データの個数分）を足していたというわけです。

これ、一瞬完全2分木の場合を考えてそうに見えるのですが完全2分木の場合も含まれているが正しいです。というのも、根の部分できれいに7:7に分けましたが、この7個のデータがどのように挿入されたかは$${T_7}$$によってすべての挿入のパターンを考えているからです。
そして本来根は$${k}$$で表してました。データの数も本来$${n}$$です。
つまり、$${k=1}$$から$${k=n}$$までの全パターンを考えないといけないのです。と言うわけで$${\sum}$$の登場です。

[FYI] Σの計算覚えてる？

ぶっちゃけ私は「あーやったね」くらいでしたｗ
でもある日とある方が「Σはfor文だ」と言っていてスッとわかった気がしました。試しに適当にΣの数式をfor文に変換してみます。
$${\displaystyle\sum_{i=1}^n(i+1)}$$をfor文にすると

integer total = 0;
for(integer i = 1; i <= n; i++) {
    total += i + 1;
}

こんな感じでしょうか。コンパイルとかしてないので細かいところ違ってもご容赦ください（－人－）
閑話休題。

深さの総和（すべてのkについて）

ここからが本番です。
$${\sum}$$が何かがわかれば、

$$
T_n = \dfrac{1}{n}\displaystyle\sum_{k=1}^n(n-1+T_{k-1}+T_{n-k})
\\ = n-1+\dfrac{1}{n}\displaystyle\sum_{k=1}^nT_{k-1}+\dfrac{1}{n}\displaystyle\sum_{k=1}^nT_{n-k}
$$

ここまではふむふむという感じでしょう。
・・・いえ待ってください。$${n-1}$$はなんで$${\sum}$$がはずれるんでしたっけ？（T_T）
そもそも$${\sum}$$の公式で、足し算引き算は分解できる、定数の掛け算割り算は外に出せるんでしたね（覚えとらんわい）。
と言うわけで丁寧に分解すると

$$
T_n = \dfrac{1}{n}\displaystyle\sum_{k=1}^n(n-1+T_{k-1}+T_{n-k})
\\ =  \dfrac{1}{n}\displaystyle\sum_{k=1}^nn-\dfrac{1}{n}\displaystyle\sum_{k=1}^n1+\dfrac{1}{n}\displaystyle\sum_{k=1}^nT_{k-1}+\dfrac{1}{n}\displaystyle\sum_{k=1}^nT_{n-k}
$$

$${\dfrac{1}{n}\displaystyle\sum_{k=1}^nn}$$何これ？となっちゃいますがこれもfor文にするとわかりやすいです。

integer total = 0;
for(integer k = 1; k <= n; k++) {
    total += n;
}

こういうことですね。つまりこれは$${n}$$回$${n}$$を足してるというわけです。$${n^2}$$ですね。それに$${\dfrac{1}{n}}$$をかけるので$${n}$$だけ残りました。
$${\dfrac{1}{n}\displaystyle\sum_{k=1}^n1}$$も同じ要領で

integer total = 0;
for(integer k = 1; k <= n; k++) {
    total += 1;
}

となって$${\dfrac{1}{n}n=1}$$とわかります。
これで$${n-1+\dfrac{1}{n}\displaystyle\sum_{k=1}^nT_{k-1}+\dfrac{1}{n}\displaystyle\sum_{k=1}^nT_{n-k}}$$まで理解できました。

最後の二つの項は同じ範囲について和をとるから

これはどういう意味でしょう？
また具体的な数字で考えてみます。
$${n=15}$$だったとすると、$${k}$$は1→15までをとります。このとき、
$${k-1}$$は0→14を、
$${n-k}$$は14→0をとりますね。
よって、順番が逆なだけでとっている値は同じです。これを$${n}$$と$${k}$$であらわすと

$${T_n=n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}T_k}$$

となるということでした。

急展開

ここで、$${S_n=T_n-2}$$とおく

なぜ・・・？
ここから先は「なぜ？」だらけなので「多分そうするとのちのち計算がラクなんだろうなぁ～」という生暖かい目で追っていきます。（数学得意な人の頭の中はわからん）
一旦元の式を確認してから展開していきましょう。

$${T_n=n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}T_k}$$
$${T_n}$$を$${S_n}$$に変換するにはどうすればいいのか？を考えます。
$${T_n-2+2=n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}(T_k-2+2)}$$
$${S_n=T_n-2}$$なので、余計な2を引いてる分$${+2}$$して帳尻を合わせました。以下細かく変形していきます。

$$
(T_n-2)+2=n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}((T_k-2)+2)
\\S_n=n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}(S_k+2)-2
\\ =n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}S_k+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}2-2
\\ =n-1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}S_k+4-2
\\ =n+1+\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}S_k
$$

$${\dfrac{2}{n}\displaystyle\sum_{k=0}^{n-1}2}$$が4になったところで「ん？」となったらfor文で考えてみてください。

両辺を$${n}$$倍して

これもなんでやってるんでしょうね？$${\dfrac{2}{n}}$$の分母を消すためでしょうか？？（謎）

$${nS_n=n(n+1)+2\displaystyle\sum_{k=0}^{n-1}S_k}$$…(Aとする)
$${n}$$を$${n-1}$$に置き換えると、

$${(n-1)S_{n-1}=(n-1)(n-1+1)+2\displaystyle\sum_{k=0}^{n-1-1}S_k}$$

$${(n-1)S_{n-1}=n(n-1)+2\displaystyle\sum_{k=0}^{n-2}S_k}$$…(Bとする)
が得られる. 両辺の引算をすると、

ここの「両辺の引算」がよくわからなかったのですがたぶんAとBの各辺を引算するって意味だったっぽいです。

$$
nS_n-(n-1)S_{n-1}=n(n+1)+2\displaystyle\sum_{k=0}^{n-1}S_k-\{n(n-1)+2\displaystyle\sum_{k=0}^{n-2}S_k\}
\\ =n^2+n+2\displaystyle\sum_{k=0}^{n-1}S_k-n^2+n-2\displaystyle\sum_{k=0}^{n-2}S_k
$$

$${2\displaystyle\sum_{k=0}^{n-1}S_k-2\displaystyle\sum_{k=0}^{n-2}S_k}$$の計算ぱっとわかりましたか？
また具体例で考えてみます。
$${n=15}$$だったとすると、$${2\displaystyle\sum_{k=0}^{14}S_k-2\displaystyle\sum_{k=0}^{13}S_k}$$です。
よって、$${k=0}$$から$${k=13}$$までの足し算はすべてカットできて、$${k=14}$$、つまり$${k=n-1}$$の分しか残らないということです。
なので、

$$
nS_n-(n-1)S_{n-1}=n^2+n+2\displaystyle\sum_{k=0}^{n-1}S_k-n^2+n-2\displaystyle\sum_{k=0}^{n-2}S_k
\\=2n+2S_{n-1}
\\
\\ nS_n=2n+2S_{n-1}+(n-1)S_{n-1}
\\ =(n-1+2)S_{n-1}+2n
\\ =(n+1)S_{n-1}+2n
$$

したがって,
$${nS_n=(n+1)S_{n-1}+2n}$$

調和級数を目指す

また謎操作（$${n(n+1)}$$で割る）ですが無心でやります。

$$
\dfrac{nS_n}{n(n+1)}=\dfrac{(n+1)S_{n-1}}{n(n+1)}+\dfrac{2n}{n(n+1)}
\\ \dfrac{S_n}{(n+1)}=\dfrac{S_{n-1}}{n}+\dfrac{2}{n+1}
$$

ここで、$${\dfrac{S_{n-1}}{n}}$$について考えます。
$${nS_n=(n+1)S_{n-1}+2n}$$なので、この式の$${n}$$を$${n-1}$$にすると

$$
(n-1)S_{n-1}=(n-1+1)S_{n-1-1}+2(n-1)
\\ = nS_{n-2}+2(n-1)
\\ S_{n-1}=\dfrac{nS_{n-2}}{(n-1)}+\dfrac{2(n-1)}{n-1}
\\ = \dfrac{nS_{n-2}}{(n-1)}+2
$$

よって 

$$
\\ \dfrac{S_{n-1}}{n}=\dfrac{nS_{n-2}}{n(n-1)}+\dfrac{2}{n}
\\ =\dfrac{S_{n-2}}{n-1}+\dfrac{2}{n}
$$

となります。
戻って$${\dfrac{S_n}{(n+1)}=\dfrac{S_{n-1}}{n}+\dfrac{2}{n+1}}$$について考えます。

$$
\dfrac{S_n}{(n+1)}=\dfrac{S_{n-1}}{n}+\dfrac{2}{n+1}
\\ = \dfrac{S_{n-2}}{n-1}+\dfrac{2}{n}+\dfrac{2}{n+1}
$$

と展開できるので、これを $${S_1}$$になるまでくりかえします。
$${S_1=S_{3-2}}$$つまり$${n=3}$$になるまでなので
$${\dfrac{S_{3-2}}{3-1}+\dfrac{2}{3}=\dfrac{S_1}{2}+\dfrac{2}{3}}$$で展開が終わります。
よって

$$
\dfrac{S_n}{n+1}=\dfrac{S_1}{2}+\dfrac{2}{3}+…+\dfrac{2}{n+1}
$$

となりました。

$${S_1}$$の値が知りたいですね。
$${T_1}$$とは、$${n=1}$$、つまりデータが1つしかないとき＝根にしか値がないときの深さの総和のことなのでこれは$${0}$$です。
これをかつて定義した$${S_n=T_n-2}$$に代入すると、$${S_1=-2}$$になります。
なので、上の式は
$${\dfrac{S_n}{n+1}=\dfrac{-2}{2}+\dfrac{2}{3}+…+\dfrac{2}{n+1}}$$
となります。
ここで唐突に調和級数（$${H_n}$$）というものが登場するのですが、これは

$${H_n=1+\dfrac{1}{2}+\dfrac{1}{3}+…+\dfrac{1}{n}}$$

というものらしいです。
先程の式にちょっとにてますね。寄せてみます。
$${2H_{n+1}=2+\dfrac{2}{2}+\dfrac{2}{3}+…+\dfrac{2}{n+1}}$$
$${\dfrac{2}{3}}$$以降は同じになりました。なので、
$${2+\dfrac{2}{2}}$$が$${\dfrac{-2}{2}}$$にできる値$${x}$$を考えます。$${x}$$で帳尻合わせちゃおう、ということです。

$${-\dfrac{2}{2}=2+\dfrac{2}{2}+x}$$
$${x=-4}$$
よって

$$
\dfrac{S_n}{n+1}=2H_{n+1}-4
\\=2(H_{n+1}-2)
$$

ゴール

$${S_n}$$について整理すると
$${S_n=2(n+1)(H_{n+1}-2)}$$
$${T_n=2(n+1)(H_{n+1}-2)+2}$$
$${P_n=\dfrac{1}{n}[2(n+1)(H_{n+1}-2)+2]+1}$$
$${H_{n+1}=H_n+\dfrac{1}{n+1}}$$を代入して整理すると

ここもわかりにくかったので1つずつ片付けます。
まず、$${(H_{n+1}-2)}$$部分（$${X}$$とする）を考えます。

$$
H_{n+1}-2=H_n+\dfrac{1}{n+1}-2
\\=H_n+\dfrac{1-2n-2}{n+1}
\\=H_n-\dfrac{2n+1}{n+1}
$$

この結果を$${T_n}$$の式に当てはめます

$$
T_n=2(n+1)X+2
\\=2(n+1)(H_n-\dfrac{2n+1}{n+1})+2
\\=2(n+1)H_n-2(n+1)\dfrac{2n+1}{n+1}+2
\\=2(n+1)H_n-2(2n+1)+2
\\=2(n+1)H_n-4n-2+2
\\=2(n+1)H_n-4n
$$

最後に$${P_n}$$にこの$${T_n}$$の結果をあてはめると

$$
P_n=\dfrac{1}{n}T_n+1
\\=\dfrac{1}{n}[2(n+1)H_n-4n]+1
\\=\dfrac{2(n+1)H_n}{n}-\dfrac{4n}{n}+1
\\=\dfrac{2(n+1)}{n}H_n-3
$$

これで計算式理解することができました！！

宿題

このあとの「調和級数が$${\log_en+\gamma}$$で近似できる」というところはさらに難しそうなので現時点ではそういうものなんだなぁ〜と思うにとどめて理解できたら書こうと思います。