Splay 平衡树旋转的
void splay(int x) {
for (int f = fa[x]; f = fa[x], f; rotate(x))
if (fa[f]) rotate(get(x) == get(f) ? f : x);
rt = x;
}
与
void splay(int x) {
for (int f = fa[x]; f; rotate(x), f = fa[x])
if (fa[f]) rotate(get(x) == get(f) ? f : x);
rt = x;
}
有什么区别吗?
然后有一个疑问就是判断
if(fa[f])
这里会不会 f 存在但是 x 没有办法旋转上来了。(刚学不会求解答谢谢)