关于路径压缩中rank数组的维护问题

Question

刘老师，当我们使用路径压缩时：
int find(int x){
assert(x >= 0 && x < count);
int r = x;//r root
while (r != p[r]){//如果是根结点，那么父结点就是自身
p[r] = p[p[r]];//因为根结点指向自身，所以永远不会出现索引超范围的错误，画图演示。
r = p[r]; //如果不相等，那么就让r不断地等于他的父节点
}
return r;
}
这时候，树的高度显然就发改变了，为什么这里不需要维护rank数组，如果要维护该如何写算法？

Answer 1

liuyubobobo 2020-08-06 18:22:39

对于并查集的结构，加入路径压缩以后，我们无法维护 rank 为实际树的高度。

实际上，我们也不需要维护，可以参考这里：http://coding.imooc.com/learn/questiondetail/7287.html

继续加油！：）

• 提问者 慕村8534111 #1

  非常感谢！