アルゴリズムイントロダクション第12章「2分探索木」
binomialsheep2分探索木
アルゴリズムイントロダクション第4章「2分探索木」
binomialsheep練習問題12-1
12-1.1
よい
12-1.2
できない。ヒープ構築はO(n)でできるため、走査がO(n)と仮定すると、比較ソートがO(n)でできることになる。これは「比較ソートはo(n lg n)でできない」という定理に反する。
直感的には、ある頂点を取り出したあとの「次に小さい値」が平均O(1)で分からない。
12-1.3
スタックはよい。
スタックを用いなくても、直前の方向が分かれば、次に進む方向とプリントすべきかが分かる（親から来たら左子に進む、左子から来たらプリントして右子に進む、右子から来たら親に進む）
12-1.4
よい
12-1.5
二分探索木の走査はO(n)でできるため、ある構築がo(n lg n)と仮定すると、比較ソートがo(n lg n)でできることになる。これは「比較ソートはo(n lg n)でできない」という定理に反する。よってどんな構築もΩ(n lg n)。
binomialsheep練習問題12-2
練習問題12-2.1
(c)912は911の右側に挿入される
(e)299は347の左側に挿入される
順次insertして、直前にinsertしたものの子になるか判定すればよい。
判定プログラムを書いた。
def func(input):
for i in range(len(input)):
for j in range(1, i):
if (input[j-1] < input[j]) != (input[j-1] < input[i]):
print(input[j-1], input[j], input[i])
return False
return True
a = [2,252,401,398,330,344,397,363]
b = [924,220,911,244,898,258,362,363]
c = [925,202,911,240,912,245,363]
d = [2,399,387,219,266,382,381,278,363]
e = [953,278,347,621,299,392,258,363]
練習問題12-2.2
よい（githubにある）
練習問題12-2.3
よい（githubにある）
練習問題12-2.4
find(31)において、
A = {25}, B = {20, 30}, C = ∅
で、a=25, b=20についてa≦bが成り立たない。
練習問題12-2.5
ある節点aの右の子孫に次節点bがあるケースでは、その次節点bが左の子cを持つと仮定すると、
- 節点cは節点aの右の子孫なので、a<c
- 節点cは節点bの左の子なので、c<b
より、節点bでなく節点cがaの次節点になるので、節点bが次節点であることに矛盾。
先行節点においても同様の議論。
練習問題12-2.6
tree_successorの正当性の話。
練習問題12-2.7
合計で木の長さ分しか移動しないので。
練習問題12-2.8
rootから実行する場合の最初の1回だけΘ(h)。
それ以外はk個の辺をそれぞれたかだか2回しか通らないので、Θ(k)。
練習問題12-2.9
xを挿入した時に満たすことと、そのあとでx<z<yなるzを挿入した時に満たすことを示せばよい。
binomialsheep練習問題12-3
練習問題12-3.1
よい（github参照）
練習問題12-3.2
挿入時は最後はNILになるが、検索の際はそこが挿入要素のkeyとの比較になるので＋１。
練習問題12-3.3
最良：完全二分木のとき、Θ(n lg n)
最悪：鎖のとき、Θ(n^2)
練習問題12-3.4
よい
練習問題12-3.5
10->20の順で削除した場合
20->10の順で削除した場合（次節点を使う場合）
練習問題12-3.6
deleteの時に親を探す（子が自分であるようなNodeを探す）必要がある。
練習問題12-3.7
逆にするだけ。
最後の削除の時に使ったのがleftかrightか変数でもっておけばよい。
binomialsheep章末問題12-1「同一キーを含む二分探索木」
a
平衡でない二分探索木の最悪ケース。毎回Θ(n)掛かるので、Θ(n^2)。
b
ほぼ完全二分木になる。
1回あたりΘ(lg n)、全体でΘ(n lg n)。
c
map<int,int>みたいになる。
木のノードはrootの1個しかない。
1回あたりΘ(1)、全体でΘ(n)。
d
最悪はaと同じ。期待はbと同じ。
証明は章末12-3。
binomialsheep章末問題12-2「基数木」
トライ木を書くだけ。
文字列における構築とよくあるメソッドを実装すると理解が捗る。
解説
問題集
binomialsheep章末問題12-3「ランダムに構成した 2 分探索木の節点の深さの平均」
a
定義より。
つまり、「平均深さがO(lg n)」と「総経路長がO(n lg n)」は同値。
b
Tのrootから各ノードまでの深さが1増える。|T_L|+|T_R| = n-1なので、満たす。
c
各キーがrootになる確率は等しく1/n。
根がi番目に小さいキーの場合、左部分木のサイズはi個, 右部分木のサイズはn-i-1個になり、bより記載式になる。
d
e
章末7-3(c)に当てはまる。
これでP(n)=O(n lg n)が示されたので、平均深さはO(lg n)。
f
同じようにピポット（ルート）を選ぶと、「ピポットの左になる数の集合」と「ルートの左になる数の集合」が完全に一致する。
二分探索木では挿入のたびに1個の要素について高さ回の比較が行われるが、クイックソートの場合はピポットとの比較が（部分木の）全ての要素について1回行われるという順序の違いはあるが、どの再帰の段階でも比較集合は完全に一致する。
binomialsheep章末問題12-4「異なる二分木の個数」
有名問題。
カタラン数の一般項を母関数を使って求める問題
a
左部分木にk個、右部分木にn-k-1個のノードが入る配置を数えるのでこの式になる。
b, c
誘導に乗るか、上の有名証明を見る。
母関数を整理した式が与えられているので、両辺に代入するだけでも証明はできる。
d
スターリング近似