1.5.15

1.5.15 #

解答 #

首先证明在最坏情况下加权 quick-union 算法生成的树中的每一层结点数均为二项式系数。

最坏情况下,每次 union 操作都是合并相同大小的树,如下图所示:

设第 i 层的结点数为 ki,那么最坏情况下每次合并后的 ki’ = ki + ki-1 。

这符合二项式系数的构造特点(详情可以搜索杨辉三角),

第一个结论证明完毕。

接下来求平均深度,首先根据二项式的求和公式,一棵深度为 n 的树(根结点的深度为零)结点总数为:

$$ \sum_{k=0}^{n} \begin{pmatrix} n \newline k \end{pmatrix} =2^n $$

每层结点数 × 该层深度后的和为:

$$ \sum_{k=0}^{n}k \cdot \begin{pmatrix} n \newline k \end{pmatrix}=n\sum_{k=1}^{n} \begin{pmatrix} n-1 \newline k-1 \end{pmatrix}=n\sum_{s=0}^{n-1} \begin{pmatrix} n-1 \newline s \end{pmatrix}=n2^{n-1} $$

这里用到了这个公式化简:

$$ \begin{pmatrix} n \newline k \end{pmatrix}=\frac{n}{k} \begin{pmatrix} n-1 \newline k-1 \end{pmatrix} $$

相除可以求得平均深度:

$$ \bar{D} = \frac{\sum_{k=0}^{n}k\cdot\begin{pmatrix}n\newline k\end{pmatrix}}{\sum_{k=0}^{n}\begin{pmatrix}n\newline k\end{pmatrix}}=\frac{n2^{n-1}}{2^n}=\frac{n}{2} $$