萌新求助!

回复帖子

@宗大大 2019-06-11 17:03 回复

哪位大佬能帮忙解释一下Splay操作

void splay(int x, int goal = 0) {
    while (par[x] != goal) {
        int y = par[x], z = par[y];
        if (z != goal) {
            if (chk(x) == chk(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if (!goal) root = x;
}

我太蒻了,这都看不懂

@smarthehe 2019-06-11 18:28 回复 举报

@宗大大

splay操作通过双旋方法把一个节点x旋转到目标节点goal的儿子

如果自己、父亲和爷爷“三点一线”,即

爷爷的左儿子是父亲,父亲的左儿子是自己

爷爷的右儿子是父亲、父亲的右儿子是自己

则先rotate父亲,再rotate自己

否则rotate两次自己

特判:爷爷即为goal的情况,此时只需要rotate一次x即可

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。