保持树高在 $O(\log n)$ 以内
by _5011_ @ 2020-11-25 21:57:57
把一个集合下的节点的父亲都设成祖先节点
by FutureThx @ 2020-11-25 21:58:42
~~logn~~ 不是按秩合并吗（（
by jerry3128 @ 2020-11-25 21:58:47
只加路径压缩是 O(logn)，只加按秩合并也是 O(logn)，两个同时加才是 O(α(n))
by _5011_ @ 2020-11-25 21:59:40
把树压扁就是原理呀
by Forever1507 @ 2020-11-25 21:59:55
$1\rightarrow 2\rightarrow 3$ 这条链如果使用两种写法从 $1$ 开始找都会经过两次递归
但是第一种写法在递归之后会把 $1$ 变成 $3$ 的直接儿子，之后再找的话能少用一次递归
这是 $n$ 比较小的例子，如果 $n$ 比较大的话这种优化效果非常显著
也就是楼上说的保持树高（最长的链长度）在 $O(\log n)$ 以内
by LeavingZ @ 2020-11-25 22:02:28
@[Zephyr_](/user/91127) ~~emm~~ 路径压缩不就直接反阿克曼函数了吗?(或者我学错了((((
by jerry3128 @ 2020-11-25 22:02:42
@[jerry3128](/user/27338) 好像tarjan的论文给的复杂度是这个
by _5011_ @ 2020-11-25 22:03:38
@[Zephyr_](/user/91127) 学到了（
by jerry3128 @ 2020-11-25 22:04:07
@[jerry3128](/user/27338) https://oi-wiki.org/ds/dsu-complexity/
by StudyingFather @ 2020-11-25 22:05:48