路径压缩的问题
来源：6-6 路径压缩 (Path Compression)
易萧
2017-06-17
问题1、其实使用第一种路径压缩，多次查找集合中元素的话，会逐渐使几乎每个节点都指向根节点的吧。比如虽然将01234一共5层压缩到了3层，第二次再搜索4或者3的时候，会使4或3也指向根节点。那么在数据量大、使用次数多的情况下，第二种压缩是不是根本没优势。
问题2、第二种路径压缩每一层都有递归，没有跳过谁，和原来迭代查找的方式要访问的次数是一样的啊，而且还使用了递归，不是应该要比迭代慢么。
问题3、我看到有同学提到对rank的维护问题，但是回答我没怎么看懂，假设有a和b集合，原本a比b的层数要高，但是经过find的压缩后，它们可能压缩的层数并不同，b比a的层数可能要高了，这时候仍然依据原来的rank是不是没多大意义，而且不论是第一种路径压缩不断的压缩至最优，还是第二种一次性压缩至最优，最后它们都不会超过两层，那么rank是不是可以去掉了。
1回答
-
我们实现的迭代和递归的两种路径压缩，结果是不一样的。迭代的路径压缩方式，每一次会跳过一个节点。而递归的路径压缩不会。以n=5为例。如下面的并查集：
0 / 1 / 2 / 3 / 4
现在假设我们要查找4这个节点。
当使用迭代的路径压缩时，结果如下：
0 / \ 1 2 / \ 3 4
当使用递归的路径压缩时，结果如下：
0 / / \ \ 1 2 3 4
总体而言，当并查集的层数为n时，迭代的路径压缩将层数压缩为n/2，而递归的路径压缩将层数压缩为2。所以，从压缩结果上看，递归的路径压缩更优。但是，一方面递归调用拥有额外消耗；另一方面，我们在实际使用中，也并不是总要查找最远的那个元素。即使查找最远的元素，由于路径压缩的作用，这个距离也变得越来越近。所以当n很大时，递归的路径压缩的性能依然不是最优的。但完全可以接受。不过也正是因为这个原因，我们在课程中实现的最后一版路径压缩，最终保留了非递归版本的路径压缩。对于这两种结果，可以使用手动跟踪代码的方式，或者用纸笔模拟程序的运行，理解这两种实现方式的区别。
另外，虽然递归调用确实有额外的开销，但是对于现代高级语言的编译器而言，已经优化的非常好了。很多时候，递归调用的额外开销近乎可以忽略不计。通常我们在实现一个算法的时候，需要优先考虑两种算法本身的差异，而不是重点考虑在具体实现上使用递归和非递归的差异。
对于这两种路径压缩的性能效率差异，可以通过这个代码进行试验： https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/06-Union-Find/Course%20Code%20(C%2B%2B)/Optional-01-Same-Cases-Test-for-UF
对于你的问题三：是的。从你列举的不断find的过程中看，rank的意义并不大。但由于使用了路径压缩，整棵树的层数很浅，所以有这个rank影响也不大。而当我们使用了rank，在初始对整个并查集不断使用union的过程中，可以尽量让整个并查集的层数小一些。所以保留这个rank是不会带来副效果的。
132017-06-18
相似问题
回答 1
回答 1
回答 1
回答 1
回答 2