基于size优化和基于rank优化的对比

Question

如果采用基于size的优化， 4->3->8是不可能的吧， 基于size优化后三个元素应该是
a -> c <- b的形式吧

基于size优化后,对于森林中的每棵树，当树的节点数size>=3时，这棵树是不会退化为链表形式的吧，每棵树都会有几个分叉吧。

有一点不是太理解
基于size优化是不是因为
假设：树a的结点数 > 树b的结点数，也就意味着树a的深度“很大概率”上比树b的深度要大（应该不是100%，但是我举不出来反例，求bobo老师举个例子），所以将结点数少的集合并入到结点数多的集合。

所以基于size优化和基于rank优化的时间上，rank略小于size吧，因为size不是100%判定正确的，也可能深度大的树并到了深度小的树。

Answer 1

liuyubobobo 2019-10-09 14:53:07

1）你是对的，不可能。这里只是举例，说明一下这个 size 的含义，我没有用代码重头模拟这个形成过程。抱歉。

2）你的理解是对的。基于 size 的优化是走向基于 rank 的优化的一个思维过渡。实际上，并查集的标准优化形式是基于 rank 的优化。

继续加油！：）

• 慕粉3458977 #1

  我也思考了这个问题，仍然没有想到size优化下的UF会出现大树更浅，小树更深的场景，还请老师指导一下。
  而且我在别的提问中有看到测试出size优于rank的场景，如果抛去jvm、环境等影响不讨论，我想他们之间的性能差异，可能在于：rank多一次比较，而size多一些sz的维护吧？

• liuyubobobo 回复 慕粉3458977 #2

  一个节点下10000个节点，只有两层；100个节点深度排列，就有100层。前者大树更浅；后者小树更深。