这是一个创建于 771 天前的主题，其中的信息可能已经有所发展或是发生改变。
并查集问题中，有一种按树大小（节点总数）合并树的算法。也就是用数组写树，合并两棵树时总是将小树（节点总数较小的树）的根节点连接到大树的根节点上。
该算法的一个性质是，其构造的森林中的任意节点的深度最多为 lgN 。
我不清楚为什么它的最坏情况是不断合并节点总数相同的两颗树，比如 2-2 （合并节点总数都为 2 的两棵树）、4-4 、8-8... 想着是因为树的深度越大，find 操作可能的最坏情况就越耗时，然而，一颗不平衡的二叉树难道不比平衡的二叉树有更差的最坏情况吗？
不知道该怎样理解？谢谢。
 |
1
sengxian 2022-03-14 22:14:26 +08:00
首先不是按照节点数量，而是按照深度启发式合并；其次你的问题的答案是：如果每次合并的树深度不一样，那么合成新树的深度并不会改变，也就不影响最坏情况
|
 |
2
Higurashi OP @sengxian #1 感谢回复。是的，更常见的似乎的确是按高度合并，但按大小合并也是一种可行（而且效率同样较高）的方法。我知道在该情况下深度不变，但这一点如何真正说明连续合并两棵树大小相等时是最坏的？能给些更详细些的提示吗？
|
|
3
sengxian 2022-03-15 16:54:16 +08:00
|
|
4
Higurashi OP @sengxian #3 虽然没有细看，也没有看懂，但知道这是在作均摊分析，似乎并没有直接分析“最坏”情形。但是在 https://oi-wiki.org/ds/dsu/ 的引用中，有一篇论文（ https://www.researchgate.net/publication/220430653_Worst-case_Analysis_of_Set_Union_Algorithms/link/0a85e53cd28bfdf5eb000000/download ）对此进行了分析，这篇论文中应该有想要的答案。显然对这个问题的解释并不是一两句话所能够说清楚的，有一种直观的理解方法当然最好，没有的话问题就到此为止。谢谢。
|
Select Language