|
|
cnpwr
| 来自北京
按秩合并真的必要吗
（有类似实验证明其必要性吗？）
总觉得应该按节点度合并的。
比如a作为父节点，有10000个子节点与之相连，而b作为另一个父节点，是一个长度为10001的链
这时候b的秩远大于a，按“按秩合并”的逻辑，a应该作为b的子节点
但如果之后我们还需要对随机元素进行find，可以看出，让b节点作为根节点，对b这条链中任意元素进行find，除第一次之外每次find的执行路径都与以a作为根节点相同——而这么做的我们只节省了一次find
但是这么做的后果是，对原先与a节点相连的全部节点，第一次执行find时（按秩合并比起以a为根节点）要多1次find，也就是，按秩合并在这种情况下会多出10000个find（只是潜在的，不一定会被执行）
为什么这里仍然说“按秩合并”更好呢？
难道不是应该按节点入度合并吗？ |
|
用Deepseek满血版问问看
