基于size优化和基于rank优化的对比
来源：11-5 基于rank的优化
何时才能成大佬
2019-10-08
如果采用基于size的优化， 4->3->8是不可能的吧， 基于size优化后三个元素应该是
a -> c <- b的形式吧
基于size优化后,对于森林中的每棵树，当树的节点数size>=3时，这棵树是不会退化为链表形式的吧，每棵树都会有几个分叉吧。
有一点不是太理解
基于size优化是不是因为
假设：树a的结点数 > 树b的结点数，也就意味着树a的深度“很大概率”上比树b的深度要大（应该不是100%，但是我举不出来反例，求bobo老师举个例子），所以将结点数少的集合并入到结点数多的集合。
所以基于size优化和基于rank优化的时间上，rank略小于size吧，因为size不是100%判定正确的，也可能深度大的树并到了深度小的树。
写回答
1回答
-
1）你是对的，不可能。这里只是举例，说明一下这个 size 的含义，我没有用代码重头模拟这个形成过程。抱歉。
2）你的理解是对的。基于 size 的优化是走向基于 rank 的优化的一个思维过渡。实际上，并查集的标准优化形式是基于 rank 的优化。
继续加油！：）
022020-05-03
相似问题