gistfile1.txt

PFDS: Ex 3.1

定理：

    Leftistヒープ T において、右のパスの長さが k である場合、
    T のノード数 n は
       n >= 2^(k+1) - 1
    である。

証明：T の高さである h について帰納法で証明する。

基底部： h = 0 の場合。

    T は単一ノードであり、右のパスの長さは k = 0。
    すなわち、n = 1 >= 2^1 - 1。よって成り立つ。

帰納部： h > 0 の場合。

h < i のとき：
    すべての h < i である leftist ヒープに対して
    定理が成り立ちと仮定する。

h = i のとき：

    以下の二つの場合について考える。

    場合1：k=0 (Tが右の部分木を持たない場合)

        明らかに n >= 1 = 2^1 -1 となる。

    場合2：k>0。

        T の左と右の部分木をそれぞれ T_L と T_R と呼ぶ。
        T_L と T_R のノード数をそれぞれ n_L と n_R とおく。
        T_L と T_R の右のパスの長さをぞれぞれ k_L と k_R とおく。
        T_L と T_R は両方とも leftist ヒープである。

        k_R = k - 1 であり、h_R < i であるから仮定より
        n_R >= 2^k - 1

        また、k_L >= k_R であるから、
        n_L >= n_R >= 2^k - 1

        ここで n = n_L + n_R + 1 であるから、
        n >= 2^k - 1 + 2^k - 1 + 1 = 2^(k+1) -1。

        よって h = i のときも成り立つ。

導かれる定理：n ノードの leftist ヒープにおける右のパスの長さは、
n >= 2^(k-1) - 1 より k <= |_ log (n+1) _| - 1 である。

高々 |_ log (n+1) _|