并查集基于路径压缩优化后，是不是基于rank的优化已经没有必要了那？

Question

不理解在路径压缩后，为什么rank已经不能准确的代表树的高度后还要保留这个rank的优化策略。

使用路径压缩优化后，尤其是把树的高度压缩为2时，所有树的高度不是1 就是2 这种情况下不能代表高度rank值依旧作为合并方向的标准，会不会产生错误的结果那？

Answer 1

liuyubobobo 2018-07-22 14:39:26

首先不会产生错误结果。在课程中介绍过，虽然rank不是树的准确高度，但是不会出现a节点的高度比b节点高，但是a节点的rank却比b节点低的情况。所以，rank可以做为添加操作时的合适考量：）

在有了路径压缩后，确实可以不要rank了，性能影响不大（事实上，一般竞赛中的并查集都这么实现）。但是，留着rank，不会拖慢性能，统计意义上是更优的。除非，内存空间是一个concern：）

• 提问者 Anthony_Duan #1

  非常感谢！