我正在观看 Robert Sedgewick 关于改进快速联合的视频。 ( https://youtu.be/sEo6LlPxpHE?t=267 )
在那里他使用树的大小而不是高度。实际上问题是找到根节点。如果高度很高,将很难找到。所以我们应该想办法减轻高度的影响。只有当我们比较高度时,它才不会按预期工作吗?将较短的树连接到较高的树并不能解决问题,而是执行:将节点数较少的树连接到节点数较多的树?
下面的情况呢?
按照视频中的逻辑:
一棵树的大小 = 4
B 树的大小 = 7
如果您将 A 连接到 B 。实际上我们正在使生成的树更高(高度 4)。但是如果我们根据树的高度来完成它,我们可以通过将树 B 连接到 A 来解决它。因此生成的树的高度为 3。
我说得对吗? 如果错了,我哪里错了?
最佳答案
请记住,不相交集森林的大多数实现都应用了路径压缩优化,其中在每次查找期间,您更改链中所有节点的父指针,以便它们都指向他们的代表。
事实证明,如果您使用路径压缩并在压缩之前跟踪所有节点的高度,那么按高度链接的渐近性能(通常称为按等级联合 ,其中“排名”是任何压缩之前的高度)和重量链接是相同的。两者都给出了逆阿克曼时间复杂度。这个结果来自this paper ,这是高度技术性的,但确实证明了这两个结果。
即使您不这样做,也可以通过另一种方式看出这两种方法(大致)彼此相同。请注意,如果你有一棵高度为 1 的树,它必须至少有两个节点。为什么?嗯,使一棵高度为 1 的树的唯一方法是合并到高度为 0 的树,每个树必须至少有一个节点。使用类似的逻辑,您可以看到,如果您有一棵高度为 2 的树,那么它必须至少有四个节点,因为要形成它,您必须将两棵高度为 1 的树合并在一起。更一般地说,您可以证明一棵高度为 n 的树必须至少有 2n 个节点。因此,按高度合并与按重量合并本质上是相同的,因为树的高度和大小之间存在密切联系。
希望这对您有所帮助!
关于algorithm - 为什么加权快速联合算法考虑树的大小而不是它们的高度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30957644/