为什么加权快速联合算法会考虑树的大小而不是它们的高度？

Question

我正在观看Robert Sedgewick关于快速联盟改进的视频.(https://youtu.be/sEo6LlPxpHE?t=267)

在那里他使用树的大小而不是高度.实际上问题是找到根节点.如果高度很高,发现将很困难.所以我们应该找到一种方法来减轻身高的影响.只有我们比较高度才能达到预期的效果？将较短的树连接到较高的树而不是解决问题而是:将具有较少节点数的树连接到具有较大节点数的树？

以下案例怎么样？

根据视频中的逻辑:

树的大小= 4

B树的大小= 7

如果你将A连接到B. 实际上我们正在使结果树更高(高度4).但是,如果我们基于树高度完成它,我们可以通过将树B连接到A来解决它.结果树的高度为3.

我对吗 ？如果错了我在哪里错了？

Answer 1

请记住,不相交集林的大多数实现都应用路径压缩优化,在每次查找期间,您都会更改链中所有节点的父指针,以便它们都指向其代表.

事实证明,如果你使用路径压缩并在压缩它们之前跟踪所有节点的高度,那么按高度链接的渐近性能(通常称为按等级联合,其中"等级"是高度先验对任何按压)和按重量的连接是相同的.两者都给出了逆Ackermann时间复杂度.这个结果来自这篇论文,该论文技术性很强,但确实证明了这两个结果.

但是,即使你不这样做,还有另一种方法可以看出这两种方法(大致)彼此相等.请注意,如果您有一个高度为1的树,则它必须至少有两个节点.为什么？好吧,你可以制作一个高度为一的树的唯一方法是合并到高度为零的树,每个树必须至少有一个节点.使用类似的逻辑,你可以看到,如果你有一个高度为2的树,那么它必须至少有四个节点,因为要形成它,你必须将两个高度为1的树合并在一起.更一般地说,您可以显示高度为n的树必须至少有2 ^个n节点.因此,通过高度合并基本上与按重量合并相同,因为树木的高度和大小之间存在紧密的联系.

希望这可以帮助!