Splay

· · 算法·理论

定义

Splay 树，是一种平衡二叉查找树，它通过 伸展（splay）操作，不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，能够在均摊 \operatorname{O}(\operatorname{log}N) 时间内完成插入、查找和删除操作，并且保持平衡而不至于退化为链。

基本结构与操作

Splay 树是一棵二叉查找树，查找某个值时满足性质：左子树任意节点的值 < 根节点的值 < 右子树任意节点的值。

维护信息

本文使用数组模拟指针来实现 Splay 树，需要维护如下信息： rt id fa_i son_{i ,0/1} val_i cnt_i sz_i
根节点编号 已使用节点个数 父亲 左右儿子编号 节点权值 权值出现次数 子树大小

辅助操作

首先是一些简单的辅助操作： 

bool dir(int x){
    return x==son[fa[x]][1];
}
void push_up(int x){
    sz[x]=cnt[x]+sz[son[x][0]]+sz[son[x][1]];
}

旋转操作

为了使 Splay 保持平衡，需要进行旋转操作。旋转的作用是将某个节点上移一个位置。

旋转需要保证：

在 Splay 中旋转分为两种：左旋和右旋。

观察图示可知，如果要通过旋转将节点 x（左旋时的 1 和右旋时的 2）上移，则旋转的方向由该节点是其父节点的左节点还是右节点唯一确定。因此，实现旋转操作时，只需要将要上移的节点 x 传入即可。

具体分析旋转步骤：（假设需要上移的节点为 x，以右旋为例）

  1. 首先，记录节点 x 的父节点 y，以及 y 的父节点 z（可能为空），并记录 x 是 y 的左子节点还是右子节点；
  2. 按照旋转后的树中自下向上的顺序，依次更新 y 的左子节点为 x 的右子节点，x 的右子节点为 y，以及若 z 空，z 的子节点为 x；
  3. 按照同样的顺序，依次更新当前 y 的左子节点（若存在）的父节点为 y，y 的父节点为 x，以及 x 的父节点为 z；
  4. 自下而上维护节点信息。