6-6使用路径压缩后rank的作用？
来源：6-6 路径压缩 (Path Compression)
慕运维2948618
2018-02-22
我也总结了一下，其实基于rank和size的优化是写在union方法里的，而路径压缩是写在find方法里的，union方法内使用了find方法，所以优化了find其实也是优化union方法。
我实现了一个只使用路径压缩而不使用基于rank优化的方法，发现效果比使用了rank优化差一点点（这也说明了路径压缩的威力），这时为什么呢？
写回答
1回答
-
主要是rank的优化和路径压缩的优化，本质都是在降低并查集树的高度，所以二者的作用是有重叠的。同时，路径压缩能在更普遍的情况下极大的降低树的高度，所以rank的优化作用在路径压缩下就不明显了。毕竟，即使不考虑rank，就算做出一颗很高的树，在路径压缩的时候，这个很高的“数枝”也会一下子被“压缩”。
确实有很多人实现并查集（尤其是在比赛中），是不实现rank优化的，对结果影响很小：）但在极端测试数据下还是会有差别的，毕竟“压缩”一个“很高的数枝”比压缩一个“相对较矮的数值”要耗时一些。
012018-02-23
相似问题