正在回答
1回答
liuyubobobo
2017-03-18 01:54:58
wow，你观察到了一个很深刻的问题：）
事实上，这正是我们将这个变量叫做rank而不是叫诸如depth或者height的原因。因为这个rank只是我们做的一个标志当前节点排名的一个数字，当我们引入了路径压缩以后，维护这个深度的真实值相对困难一些，而且实践告诉我们，我们其实不需要真正维持这个值是真实的深度值，我们依然可以以这个rank值作为后续union过程的参考。因为根据我们的路径压缩的过程，rank高的节点虽然被抬了上来，但是整体上，我们的并查集从任意一个叶子节点出发向根节点前进，依然是一个rank逐渐增高的过程。也就是说，这个rank值在经过路径压缩以后，虽然不是真正的深度值，但仍然可以胜任，作为union时的参考。
15
有任何疑惑可以回复我~
相似问题
路径压缩的问题
1011
1
1
6-6使用路径压缩后rank的作用？
712
0
2
压缩后文件变大
1010
0
4
还是没办法理解这里的rank为什么不用更新~~~~
1057
7
5
并查集基于路径压缩优化后，是不是基于rank的优化已经没有必要了那？
1507
0
2
登录后可查看更多问答，登录/注册
