6-6使用路径压缩后rank的作用？

Question

我也总结了一下，其实基于rank和size的优化是写在union方法里的，而路径压缩是写在find方法里的，union方法内使用了find方法，所以优化了find其实也是优化union方法。

我实现了一个只使用路径压缩而不使用基于rank优化的方法，发现效果比使用了rank优化差一点点（这也说明了路径压缩的威力），这时为什么呢？

Answer 1

liuyubobobo 2018-02-23 03:23:50

主要是rank的优化和路径压缩的优化，本质都是在降低并查集树的高度，所以二者的作用是有重叠的。同时，路径压缩能在更普遍的情况下极大的降低树的高度，所以rank的优化作用在路径压缩下就不明显了。毕竟，即使不考虑rank，就算做出一颗很高的树，在路径压缩的时候，这个很高的“数枝”也会一下子被“压缩”。

确实有很多人实现并查集（尤其是在比赛中），是不实现rank优化的，对结果影响很小：）但在极端测试数据下还是会有差别的，毕竟“压缩”一个“很高的数枝”比压缩一个“相对较矮的数值”要耗时一些。

• 提问者 慕运维2948618 #1

  非常感谢！