路经压缩过程中Rank的变化
来源：6-6 路径压缩 (Path Compression)
Mr_Scorpio
2017-03-17
老师，请问在路径压缩的过程中，不需要维护rank了吗？
写回答
1回答
-
wow，你观察到了一个很深刻的问题：）
事实上，这正是我们将这个变量叫做rank而不是叫诸如depth或者height的原因。因为这个rank只是我们做的一个标志当前节点排名的一个数字，当我们引入了路径压缩以后，维护这个深度的真实值相对困难一些，而且实践告诉我们，我们其实不需要真正维持这个值是真实的深度值，我们依然可以以这个rank值作为后续union过程的参考。因为根据我们的路径压缩的过程，rank高的节点虽然被抬了上来，但是整体上，我们的并查集从任意一个叶子节点出发向根节点前进，依然是一个rank逐渐增高的过程。也就是说，这个rank值在经过路径压缩以后，虽然不是真正的深度值，但仍然可以胜任，作为union时的参考。
1542021-06-02
相似问题