Splay rotate操作 图解

Splay 的旋转操作比较难理解，因此我在这里画了一张详细的图解。

首先是旋转部分的代码，完整代码见 OI模板-数据结构

void rotate(int x)
{
    int y=t[x].fa, z=t[y].fa, k=t[y].ch[1]==x;
    t[z].ch[t[z].ch[1]==y]=x; t[x].fa=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].fa=y;
    t[x].ch[k^1]=y; t[y].fa=x;
    push_up(y); push_up(x); // 维护子树信息，图里没有画
}

这里是图解，我们只要考虑一般的情况即可（记起来方便 qwq）

Powered by Diagrams