3.2.8 #

解答 #

假设输入的完全二叉树结点数目为 $n$。

完全二叉树总是可以分成两部分，一个满二叉树，以及多余的结点。

于是完全二叉树中满二叉树的部分层数为 $l = \lfloor \log_2 (n+1) \rfloor$。（根结点位于第一层）

满二叉树占的结点数量为 $n_1 = 2^l -1$，多余结点数量为 $n_2=n-n_1$。

又因为深度等于层数 - 1，多余结点正好在满二叉树的下一层，因此多余结点的深度即为 $l$。

于是多余结点的深度和 $d_2 = l \times n_2$。

接下来计算满二叉树的深度和。

一个层数为 $l$ 的满二叉树，最后一层正好有 $2^{l-1}$ 个结点。

于是深度和为 $d_1 = 0 \times 1 + 1 \times 2+2 \times 4+\cdots+(l-1)2^{l-1} =\sum_{i=1}^{l-1} i2^i$。

用错位相减法，有：

$$ \begin{eqnarray*} d_1&=&1\times 2^1 + &2 \times 2^2 + \cdots + (l-1)2^{l-1} \newline 2d_1&=& &1\times 2^2 + \cdots+(l-2)2^{l-1} +(l-1)2^{l} \newline d_1-2d_1&=& 1 \times2^1+ &1 \times2^2+\cdots+1\times2^{l-1}-(l-1)2^l \newline d_1 &=&(l-1)2^l &-2^l+2 \newline &=&(l-2)2^l &+2 \end{eqnarray*} $$

于是可得总深度和： $d=d_1+d_2=l\times n_2+ (l-2)2^l+2$。

平均查找次数即为：$avgCompare=d / n + 1$ 。

代码 #

int OptCompares(int n)
{
    // 完全二叉树 = 满二叉树 + 多余结点
    // 满二叉树的层数。
    var l = (int)Math.Log(n + 1, 2);
    // 多余结点的个数。
    var extraNodes = n + 1 - (int)Math.Pow(2, l);

    var depthSum =
        extraNodes * l + (l - 2) * (int)Math.Pow(2, l) + 2;
    return depthSum / n + 1;
}