

Splay

本页面将简要介绍如何用 Splay 维护二叉查找树。

简介

Splay 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。它由 Daniel Sleator 和 Robert Tarjan 发明。

结构

二叉查找树的性质

首先肯定是一棵二叉树！

能够在这棵树上查找某个值的性质：左子树任意节点的值 根节点的值 右子树任意节点的值。

节点维护信息

rt	tot	fa[i]	ch[i][0/1]	val[i]	cnt[i]	sz[i]
根节点编号	节点个数	父亲	左右儿子编号	节点权值	权值出现次数	子树大小

操作

基本操作

• maintain(x)：在改变节点位置后，将节点 的 更新。
• get(x)：判断节点 是父亲节点的左儿子还是右儿子。
• clear(x)：销毁节点 。

void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }
bool get(int x) { return x == ch[fa[x]][1]; }
void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0; }

旋转操作

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

旋转需要保证：

• 整棵 Splay 的中序遍历不变（不能破坏二叉查找树的性质）。
• 受影响的节点维护的信息依然正确有效。
• root 必须指向旋转后的根节点。

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

具体分析旋转步骤（假设需要旋转的节点为 ，其父亲为 ，以右旋为例）

1. 将 的左儿子指向 的右儿子，且 的右儿子（如果 有右儿子的话）的父亲指向 ；ch[y][0]=ch[x][1]; fa[ch[x][1]]=y;
2. 将 的右儿子指向 ，且 的父亲指向 ；ch[x][chk^1]=y; fa[y]=x;
3. 如果原来的 还有父亲 ，那么把 的某个儿子（原来 所在的儿子位置）指向 ，且 的父亲指向 。fa[x]=z; if(z) ch[z][y==ch[z][1]]=x;

void rotate(int x) {
  int y = fa[x], z = fa[y], chk = get(x);
  ch[y][chk] = ch[x][chk ^ 1];
  if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
  ch[x][chk ^ 1] = y;
  fa[y] = x;
  fa[x] = z;
  if (z) ch[z][y == ch[z][1]] = x;
  maintain(y);
  maintain(x);
}

Splay 操作

Splay 规定：每访问一个节点后都要强制将其旋转到根节点。此时旋转操作具体分为 种情况讨论（其中 为需要旋转到根的节点）

• 如果 的父亲是根节点，直接将 左旋或右旋（图 ）。
• 如果 的父亲不是根节点，且 和父亲的儿子类型相同，首先将其父亲左旋或右旋，然后将 右旋或左旋（图 ）。
• 如果 的父亲不是根节点，且 和父亲的儿子类型不同，将 左旋再右旋、或者右旋再左旋（图 ）。

Tip

请读者尝试自行模拟 种旋转情况，以理解 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;
}

插入操作

插入操作是一个比较复杂的过程，具体步骤如下（假设插入的值为 ）：

• 如果树空了，则直接插入根并退出。
• 如果当前节点的权值等于 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
• 否则按照二叉查找树的性质向下找，找到空节点就插入即可（请不要忘记 Splay 操作）。

void ins(int k) {
  if (!rt) {
    val[++tot] = k;
    cnt[tot]++;
    rt = tot;
    maintain(rt);
    return;
  }
  int cur = rt, f = 0;
  while (1) {
    if (val[cur] == k) {
      cnt[cur]++;
      maintain(cur);
      maintain(f);
      splay(cur);
      break;
    }
    f = cur;
    cur = ch[cur][val[cur] < k];
    if (!cur) {
      val[++tot] = k;
      cnt[tot]++;
      fa[tot] = f;
      ch[f][val[f] < k] = tot;
      maintain(tot);
      maintain(f);
      splay(tot);
      break;
    }
  }
}

查询 x 的排名

根据二叉查找树的定义和性质，显然可以按照以下步骤查询 的排名：

• 如果 比当前节点的权值小，向其左子树查找。
• 如果 比当前节点的权值大，将答案加上左子树（）和当前节点（）的大小，向其右子树查找。
• 如果 与当前节点的权值相同，将答案加 并返回。

注意最后需要进行 Splay 操作。

int rk(int k) {
  int res = 0, cur = rt;
  while (1) {
    if (k < val[cur]) {
      cur = ch[cur][0];
    } else {
      res += sz[ch[cur][0]];
      if (k == val[cur]) {
        splay(cur);
        return res + 1;
      }
      res += cnt[cur];
      cur = ch[cur][1];
    }
  }
}

查询排名 x 的数

设 为剩余排名，具体步骤如下：

• 如果左子树非空且剩余排名 不大于左子树的大小 ，那么向左子树查找。
• 否则将 减去左子树的和根的大小。如果此时 的值小于等于 ，则返回根节点的权值，否则继续向右子树查找。

int kth(int k) {
  int cur = rt;
  while (1) {
    if (ch[cur][0] && k <= sz[ch[cur][0]]) {
      cur = ch[cur][0];
    } else {
      k -= cnt[cur] + sz[ch[cur][0]];
      if (k <= 0) {
        splay(cur);
        return val[cur];
      }
      cur = ch[cur][1];
    }
  }
}

查询前驱

前驱定义为小于 的最大的数，那么查询前驱可以转化为：将 插入（此时 已经在根的位置了），前驱即为 的左子树中最右边的节点，最后将 删除即可。

int pre() {
  int cur = ch[rt][0];
  if (!cur) return cur;
  while (ch[cur][1]) cur = ch[cur][1];
  splay(cur);
  return cur;
}

查询后继

后继定义为大于 的最小的数，查询方法和前驱类似： 的右子树中最左边的节点。

int nxt() {
  int cur = ch[rt][1];
  if (!cur) return cur;
  while (ch[cur][0]) cur = ch[cur][0];
  splay(cur);
  return cur;
}

合并两棵树

合并两棵 Splay 树，设两棵树的根节点分别为 和 ，那么我们要求 树中的最大值小于 树中的最小值。删除操作如下：

• 如果 和 其中之一或两者都为空树，直接返回不为空的那一棵树的根节点或空树。
• 否则将 树中的最大值 到根，然后把它的右子树设置为 并更新节点的信息，然后返回这个节点。

删除操作

删除操作也是一个比较复杂的操作，具体步骤如下：

首先将 旋转到根的位置。

• 如果 （有不止一个 ），那么将 减 并退出。
• 否则，合并它的左右两棵子树即可。

void del(int k) {
  rk(k);
  if (cnt[rt] > 1) {
    cnt[rt]--;
    maintain(rt);
    return;
  }
  if (!ch[rt][0] && !ch[rt][1]) {
    clear(rt);
    rt = 0;
    return;
  }
  if (!ch[rt][0]) {
    int cur = rt;
    rt = ch[rt][1];
    fa[rt] = 0;
    clear(cur);
    return;
  }
  if (!ch[rt][1]) {
    int cur = rt;
    rt = ch[rt][0];
    fa[rt] = 0;
    clear(cur);
    return;
  }
  int cur = rt, x = pre();
  fa[ch[cur][1]] = x;
  ch[x][1] = ch[cur][1];
  clear(cur);
  maintain(rt);
}

代码实现

#include <cstdio>
const int N = 100005;
int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];
struct Splay {
  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }
  bool get(int x) { return x == ch[fa[x]][1]; }
  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
  }
  void rotate(int x) {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintain(x);
    maintain(y);
  }
  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 ins(int k) {
    if (!rt) {
      val[++tot] = k;
      cnt[tot]++;
      rt = tot;
      maintain(rt);
      return;
    }
    int cur = rt, f = 0;
    while (1) {
      if (val[cur] == k) {
        cnt[cur]++;
        maintain(cur);
        maintain(f);
        splay(cur);
        break;
      }
      f = cur;
      cur = ch[cur][val[cur] < k];
      if (!cur) {
        val[++tot] = k;
        cnt[tot]++;
        fa[tot] = f;
        ch[f][val[f] < k] = tot;
        maintain(tot);
        maintain(f);
        splay(tot);
        break;
      }
    }
  }
  int rk(int k) {
    int res = 0, cur = rt;
    while (1) {
      if (k < val[cur]) {
        cur = ch[cur][0];
      } else {
        res += sz[ch[cur][0]];
        if (k == val[cur]) {
          splay(cur);
          return res + 1;
        }
        res += cnt[cur];
        cur = ch[cur][1];
      }
    }
  }
  int kth(int k) {
    int cur = rt;
    while (1) {
      if (ch[cur][0] && k <= sz[ch[cur][0]]) {
        cur = ch[cur][0];
      } else {
        k -= cnt[cur] + sz[ch[cur][0]];
        if (k <= 0) {
          splay(cur);
          return val[cur];
        }
        cur = ch[cur][1];
      }
    }
  }
  int pre() {
    int cur = ch[rt][0];
    if (!cur) return cur;
    while (ch[cur][1]) cur = ch[cur][1];
    splay(cur);
    return cur;
  }
  int nxt() {
    int cur = ch[rt][1];
    if (!cur) return cur;
    while (ch[cur][0]) cur = ch[cur][0];
    splay(cur);
    return cur;
  }
  void del(int k) {
    rk(k);
    if (cnt[rt] > 1) {
      cnt[rt]--;
      maintain(rt);
      return;
    }
    if (!ch[rt][0] && !ch[rt][1]) {
      clear(rt);
      rt = 0;
      return;
    }
    if (!ch[rt][0]) {
      int cur = rt;
      rt = ch[rt][1];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    if (!ch[rt][1]) {
      int cur = rt;
      rt = ch[rt][0];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    int cur = rt;
    int x = pre();
    fa[ch[cur][1]] = x;
    ch[x][1] = ch[cur][1];
    clear(cur);
    maintain(rt);
  }
} tree;

int main() {
  int n, opt, x;
  for (scanf("%d", &n); n; --n) {
    scanf("%d%d", &opt, &x);
    if (opt == 1)
      tree.ins(x);
    else if (opt == 2)
      tree.del(x);
    else if (opt == 3)
      printf("%d\n", tree.rk(x));
    else if (opt == 4)
      printf("%d\n", tree.kth(x));
    else if (opt == 5)
      tree.ins(x), printf("%d\n", val[tree.pre()]), tree.del(x);
    else
      tree.ins(x), printf("%d\n", val[tree.nxt()]), tree.del(x);
  }
  return 0;
}

例题

以下题目都是裸的 Splay 维护二叉查找树。

• 【模板】普通平衡树
• 【模板】文艺平衡树
• 「HNOI2002」营业额统计
• 「HNOI2004」宠物收养所

习题

• 「Cerc2007」robotic sort 机械排序
• 二逼平衡树（树套树）
• bzoj 2827 千山鸟飞绝
• 「Lydsy1706 月赛」K 小值查询

参考资料与注释

本文部分内容引用于 algocode 算法博客，特别鸣谢！

---

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments