并查集基于路径压缩优化后，是不是基于rank的优化已经没有必要了那？
来源：11-7 更多和并查集相关的话题
Anthony_Duan
2018-07-22
不理解在路径压缩后，为什么rank已经不能准确的代表树的高度后还要保留这个rank的优化策略。
使用路径压缩优化后，尤其是把树的高度压缩为2时，所有树的高度不是1 就是2 这种情况下不能代表高度rank值依旧作为合并方向的标准，会不会产生错误的结果那？
写回答
1回答
-
首先不会产生错误结果。在课程中介绍过，虽然rank不是树的准确高度，但是不会出现a节点的高度比b节点高，但是a节点的rank却比b节点低的情况。所以，rank可以做为添加操作时的合适考量：）
在有了路径压缩后，确实可以不要rank了，性能影响不大（事实上，一般竞赛中的并查集都这么实现）。但是，留着rank，不会拖慢性能，统计意义上是更优的。除非，内存空间是一个concern：）
012018-07-22
相似问题