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

来源:11-5 基于rank的优化

慕虎3444883

2020-04-03

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

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

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

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

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

写回答

1回答

liuyubobobo

2020-04-03

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


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


继续加油!:)

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

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程