关于并查集的路径压缩课程的问题

Question

    老师，路径压缩可以与rank优化一起使用吗？路径压缩对find方法进行优化，将树的高度减少了；而在union方法中又使用rank数组来表示树的高度。假设在union方法中调用find方法前某根节点为x的树高为3，调用find之后路径压缩高度变为了2。只是parent数组发生变化了，而rank数组没变化，那么这时rank［x］此时不还是3吗？我不明白的地方是这样树的高度已经与实际的不匹配，不会出现问题吗？

  希望老师能解惑，不知道是不是我哪里想错了，先谢谢老师啦😁

Answer 1

liuyubobobo 2018-02-11 15:47:29

大赞！你想得完全没有问题：）

可以参考这个问答：https://coding.imooc.com/learn/questiondetail/7287.html

• 提问者 YoooooooA #1

  谢谢老师解惑，rank可以作为参考值去使用，又明白一个知识点。老师，那如果路径压缩与size的优化组合的去使用也是可以的对吗？

• liuyubobobo 回复 提问者 YoooooooA #2

  可以，不过因为size本身和并查集的树的高度无关，所以通常不用size做优化。rank+路径压缩是并查集最经典的实现：）

• 提问者 YoooooooA #3

  嗯嗯，谢谢老师，明白了。