关于路径压缩中rank数组的维护问题
来源：6-6 路径压缩 (Path Compression)
慕村8534111
2020-08-06
刘老师，当我们使用路径压缩时：
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数组，如果要维护该如何写算法？
写回答
1回答
-
对于并查集的结构，加入路径压缩以后，我们无法维护 rank 为实际树的高度。
实际上，我们也不需要维护，可以参考这里：http://coding.imooc.com/learn/questiondetail/7287.html
继续加油！：）
112020-08-07
相似问题