还是没办法理解这里的rank为什么不用更新~~~~

Question

还是没办法理解这里的rank为什么不用更新~~~

Answer 1

liuyubobobo 2019-01-30 15:13:24

事实上，这正是我们将这个变量叫做rank而不是叫诸如depth或者height的原因。因为这个rank只是我们做的一个标志当前节点排名的一个数字。当我们引入了路径压缩以后，维护这个深度的真实值相对困难一些（可以思考一下要如何维护？）

而实际上，这个rank的作用，只是在union的过程中，比较两个节点的深度。换句话说，我们完全可以不知道每个节点具体的深度，只要保证每两个节点深度的大小关系可以被rank正确表达即可。而这个rank确实可以正确表达两个节点之间深度的大小关系。因为根据我们的路径压缩的过程，rank高的节点虽然被抬了上来（深度降低），但是不可能降低到比原先深度更小的节点还要小。所以，rank足以胜任比较两个节点的深度，进而选择合适的节点进行union这个任务：）

继续加油！：）

• IMUHERO #1

  哇，终于懂了，幸好来看了问答区

• 慕虎3444883 #2

  老师，为什么 不可能降低到比原先深度更小的节点还要小 啊？
  我画了图模拟了一下过程，确实是这样子，但就是不理解没有头绪！
  
  根据路径压缩的过程，rank高的节点虽然被抬了上来（深度降低），但是不可能降低到比原先深度更小的节点还要小。

• 慕虎3444883 #3

  好困惑。。不知道是哪一步的理解出了问题

点开查看后面1条评论