日沖様の叡智 - ほかんじょ

b)
正則な二分木であり、ノードは対象潤である。左の子＜親＜右の子の関係を持つ

c)
ⅰ）どのノードにも赤と黒が割り当てられている
ⅱ）赤いノードは必ず黒い親を持ち、外点と根は必ず黒である。
ⅲ）根から外点へのパスはどのようなパスを通ってもどう数個の黒いノードを通る。

d)
外点の深さの最小値をcとすると、子の木の深さdはd≦2cとなる。
またk≦cのときの内点の個数は2^k個であるので、この木の内点の総数nはn=2^c-1となる
よって　d≦2c≦2[logn+1]となり
深さはo(logn)

b)
ヒープの深さdとして、あるノードをvとおくと、vまでのノード数がd-depth(n)となるのでn=Σ(v,n)(d-depth(v))となって、子が２つあることからΣ(v,n)(d-depth(n))≦2n

c)
ⅰ）まず、幅優先順位の最小値を削除し、ソートのあいているところの最後のほうへ入れる
ⅱ）ⅰ）で削除したところに、幅優先順位の最大のところを入れ替える
ⅲ）入れた幅優先順位のところから下移動し、ヒープを再構成する
ⅳ）以上をサイズnとするとn-1回繰り返す。
以上より計算時間はo(logn)となりヒープ構成の時間を入れると
o(nlogn)となる