1.5.15

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

解答

首先证明在最坏情况下加权 quick-union 算法生成的树中的每一层结点数均为二项式系数。
最坏情况下,每次 union 操作都是合并相同大小的树,如下图所示:

设第 i 层的结点数为 ki,那么最坏情况下每次合并后的 ki’ = ki + ki-1 。
这符合二项式系数的构造特点(详情可以搜索杨辉三角),
第一个结论证明完毕。

接下来求平均深度,首先根据二项式的求和公式,一棵深度为 n 的树(根结点的深度为零)结点总数为:
$$
\sum_{k=0}^{n}
\begin{pmatrix}
n \\
k
\end{pmatrix}
=2^n
$$
每层结点数 × 该层深度后的和为:
$$
\sum_{k=0}^{n}k \cdot
\begin{pmatrix}
n \\
k
\end{pmatrix}=n\sum_{k=1}^{n}
\begin{pmatrix}
n-1 \\
k-1
\end{pmatrix}=n\sum_{s=0}^{n-1}
\begin{pmatrix}
n-1 \\
s
\end{pmatrix}=n2^{n-1}
$$
这里用到了这个公式化简:
$$
\begin{pmatrix}
n \\
k
\end{pmatrix}=\frac{n}{k}
\begin{pmatrix}
n-1 \\
k-1
\end{pmatrix}
$$
相除可以求得平均深度:
$$
\bar{D} = \frac{\sum_{k=0}^{n}k\cdot\begin{pmatrix}n\\k\end{pmatrix}}{\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}}=\frac{n2^{n-1}}{2^n}=\frac{n}{2}
$$

上一题 下一题