我一直在阅读有关联合查找问题的内容。两个主要改进是路径压缩和按等级并集。据我了解,按等级并集用于确定如何组合不相交的树。如果我们有两棵不相交的树 T1 和 T2,那么我们将具有较小等级的树的根附加到具有较高等级的树。如果我们不使用路径压缩,那么排名只是树的深度。这是有道理的,因为我们不想增加树的深度,因为它直接影响查找和并集。
我的问题是当我们也使用路径压缩时。我一直读到这两种优化是相辅相成的,但我没有看到这一点。由于路径压缩,等级不再是树的深度(它成为深度的上限)。假设T1有2个分支(令T1的秩为3),T2的深度为2,秩为2。现在假设我们对下面标有“*”的T1叶子执行查找操作(带有路径压缩)。现在,如果我们合并 T1 的根和 T2 的根,那么 T2 将附加到 T1 的根(因为查找不会更新排名)。生成的树的深度为 3。但是如果我们将 T1 附加到 T2,我们可能会获得更好的性能。
T1: o (Rank = 3) T2: o (Rank = 2)
/ \ |
o o o
| |
o o
|
*
在 T1 的叶子上查找后(“*”),然后对 T1 和 T2 的根进行联合,我们得到
T1: o (Rank = 3) T2: o (Rank = 2)
/| |\ |
* o o o o
|
o
Result of T1 union T2
o
/ | | |\
* o o o o Rank = 3 and Max Depth = 3
|
o
|
o
我在这里错过了什么吗?路径压缩和按等级合并如何相辅相成?我知道等级只是树深度的上限,但我不知道按等级并集如何提高结构的整体性能。这比随机组合根的并集好在哪里?
我在这里先向您的帮助表示感谢。
按等级并集可确保树的最大深度为 log N,因此它对每个操作设置 O(log N) 的最坏情况上限。
没有任何特殊联合规则的路径压缩上限为 O(log N)摊销的每次操作的成本,但是不限制最坏情况的成本。 (摊余成本甚至可能有更严格的界限,但我知道如何证明 O(log N))
结合使用两者,您可以得到最坏情况下的 O(log N) 限制and摊销边界提高到 O(
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)