老师，基于size的优化有什么不适用的场景吗？

Question

基于size和基于rank优化的问题：

我的理解是：
基于size是因为：被同化的树的所有节点 迭代找根的次数会+1，而size小的话受影响的节点就少，合并后整个树的 平均迭代找root的次数 更少；

但另一个方面：如果基于rank，会尽可能避免合并后树的 最大高度 增加；

我觉得，每次查询都是从某个节点出发，到所在根停止的，那从以上的分析来看，基于size的思路不应该更贴切吗？ 难道说其实基于size的优化会出现某些极端场景吗？？可是我按代码思路大概画了画，好像并不会出现很长的近似于链表般的情况？

测试来测试去，两种思路似乎拉不开差距。 但我有看到bobo老师在别的问答下边说过：并查集的标准优化形式是基于 rank 的优化，而基于size的优化只是向基于rank优化的过渡。 所以我想我可能是思路就有问题，因为现在是在复习代码，视频已经挺久没再看了。

Answer 1

liuyubobobo 2020-04-03 14:59:39

基于 size 的优化的问题就在于，我们希望树的高度尽量低，但是 size 小不意味着高度低。而相较而言，rank 可以更好地衡量高度。

其实，对于大部分情况，size 是够用的。但是从原理上，size 并非最优。

继续加油！：）

• 提问者 慕虎3444883 #1

  我们不应该更希望树的所有节点的平均高度更低吗？ 我觉得size正是这个思路呀？基于rank是让树的最大高度更低吧？

• liuyubobobo 回复 提问者 慕虎3444883 #2

  不能完全看平均，要看最坏情况。算法考虑的是最坏情况。

• 提问者 慕虎3444883 回复 liuyubobobo #3

  emm┗|｀O′|┛；bobo说的有道理，我可能犹豫的是，因为这里的最坏情况并不是像二叉搜索树退化成链表一样致命，而只是某些个节点相对于基于rank优化会深度较大，至于这些节点是占多数还是少数。。我学的还不够熟练，有点感觉不出来。。那我就用rank好了。。