3.2.8

上次更新:2019-06-14
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

假设输入的完全二叉树结点数目为 $ 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} \\
2d_1&=& &1\times 2^2 + \cdots+(l-2)2^{l-1} +(l-1)2^{l} \\
d_1-2d_1&=& 1 \times2^1+ &1 \times2^2+\cdots+1\times2^{l-1}-(l-1)2^l \\
d_1 &=&(l-1)2^l &-2^l+2 \\
&=&(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 $ 。

代码

private static 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;
}
上一题 下一题