并查集-二项树与快速合并算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了并查集-二项树与快速合并算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1430字，纯文字阅读大概需要3分钟。

内容图文

ALGS4 Exercise 1.5.15

Problem

Binomial trees. Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial coefficients. Compute the average depth of a node in a worst-case tree with \(N = 2^n\) nodes.

---

Solution

从上图中可以看到在 worst-case input 中，

• 倒数第二行的树，每一层的节点自上而下分别为 1, 2, 1
• 倒数第一行的树，每一层的节点自上而下分别为 1, 3, 3, 1

符合二项式系数。

对于加权快速合并算法而言，最坏的情况发生在每一次合并中，两棵树具有相同的权值。在这种情况下，每次合并都会造成树的深度增加。

假设合并前的树第 \(i\) 层的节点数为 \(k_{i}\)，合并的后主树这一层的节点数会增加副树第 \(i - 1\) 层的节点数 \(k_{i - 1}\)，即

\[k_{i}^{\prime} = k_{i} + k_{i - 1} \]

因此，所有节点的总深度和就是每一层上每个节点的深度的总和，即

\[\sum_{i = 0}^{n} i \times C_n^i \]

根据 组合数公式，有

\[C_n^r = \frac{n!}{r!(n - r)!} = \frac{n \times (n - 1)!}{r \times (r - 1)!(n - r)!} = \frac{n}{r} \times C_{n - 1}^{r - 1} \]

\[r \times C_n^r = n \times C_{n - 1}^{r - 1} \]

因此，有

\[\sum_{i = 0}^{n} i \times C_n^i = \sum_{i = 1}^{n} n \times C_{n - 1}^{i - 1} \]

根据 二项式公式，有

\[(x + y)^n = \sum_{i = 0}^{n} C_n^i x^{n - i} y^i \]

取 \(x = y = 1\)，可得

\[(x + y)^n = 2^n = \sum_{i = 0}^{n} C_n^i \]

因此，所有节点的总深度之和为

\[\sum_{i = 1}^{n} n \times C_{n - 1}^{i- 1} = n \times \sum_{i = 1}^{n} C_{n - 1}^{i - 1} = n \times 2^{n - 1} \]

平均深度为

\[\frac{n \times 2^{n - 1}}{2^n} = \frac{n}{2} \]

内容总结

以上是互联网集市为您收集整理的并查集-二项树与快速合并算法全部内容，希望文章能够帮你解决并查集-二项树与快速合并算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---