并查集问题中,有一种按树大小(节点总数)合并树的算法。也就是用数组写树,合并两棵树时总是将小树(节点总数较小的树)的根节点连接到大树的根节点上。
该算法的一个性质是,其构造的森林中的任意节点的深度最多为 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 )对此进行了分析,这篇论文中应该有想要的答案。显然对这个问题的解释并不是一两句话所能够说清楚的,有一种直观的理解方法当然最好,没有的话问题就到此为止。谢谢。
|