关于并查集的路径压缩课程的问题
来源：6-6 路径压缩 (Path Compression)
YoooooooA
2018-02-11
老师，路径压缩可以与rank优化一起使用吗？路径压缩对find方法进行优化，将树的高度减少了；而在union方法中又使用rank数组来表示树的高度。假设在union方法中调用find方法前某根节点为x的树高为3，调用find之后路径压缩高度变为了2。只是parent数组发生变化了，而rank数组没变化，那么这时rank［x］此时不还是3吗？我不明白的地方是这样树的高度已经与实际的不匹配，不会出现问题吗？
希望老师能解惑，不知道是不是我哪里想错了，先谢谢老师啦😁
写回答
1回答
-
liuyubobobo
2018-02-11
大赞！你想得完全没有问题：）
可以参考这个问答：https://coding.imooc.com/learn/questiondetail/7287.html
132018-02-11
相似问题
路径压缩的问题
回答 1
关于find路径压缩后对应并查集的结构
回答 1
并查集路径压缩比rank版本要慢
回答 1
关于路径压缩中rank数组的维护问题
回答 1
6-6使用路径压缩后rank的作用？
回答 1