路径压缩的问题

Question

问题1、其实使用第一种路径压缩，多次查找集合中元素的话，会逐渐使几乎每个节点都指向根节点的吧。比如虽然将01234一共5层压缩到了3层，第二次再搜索4或者3的时候，会使4或3也指向根节点。那么在数据量大、使用次数多的情况下，第二种压缩是不是根本没优势。

问题2、第二种路径压缩每一层都有递归，没有跳过谁，和原来迭代查找的方式要访问的次数是一样的啊，而且还使用了递归，不是应该要比迭代慢么。

问题3、我看到有同学提到对rank的维护问题，但是回答我没怎么看懂，假设有a和b集合，原本a比b的层数要高，但是经过find的压缩后，它们可能压缩的层数并不同，b比a的层数可能要高了，这时候仍然依据原来的rank是不是没多大意义，而且不论是第一种路径压缩不断的压缩至最优，还是第二种一次性压缩至最优，最后它们都不会超过两层，那么rank是不是可以去掉了。

Answer 1

liuyubobobo 2017-06-17 01:12:06

我们实现的迭代和递归的两种路径压缩，结果是不一样的。迭代的路径压缩方式，每一次会跳过一个节点。而递归的路径压缩不会。以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是不会带来副效果的。

• 提问者 易萧 #1

  我倒不是说考虑递归的消耗。但是第二种路径压缩，在第一次压缩的时候，访问的次数和不采用路径压缩是一样的啊，都是O(n)吧，但课程最后演示的确是比普通查找快了，没看出为什么要比普通查找快。

• liuyubobobo 回复 提问者 易萧 #2

  因为课程演示的是执行多次并查集操作的总时间，而不是一次操作的时间。

• 提问者 易萧 #3

  非常感谢！