此博客为补档博客,只做简单讲解。

对于一个平衡树,保证复杂度的最重要的操作就是旋转操作。

而 Splay 的旋转操作比较简单,我们依次完成以下的操作即可:

  • 把节点 $x$ 更换到父节点。
  • 把父节点和 $x$ 的另一个子节点交换。

代码实现

void rotate(int x) {
  int y = tr[x].fa, z = tr[y].fa, r = get(x);
  tr[z].son[get(y)] = x;
  tr[x].fa = z;
  tr[tr[x].son[r ^ 1]].fa = y;
  tr[y].son[r] = tr[x].son[r ^ 1];
  tr[x].son[r ^ 1] = y;
  tr[y].fa = x;
  pushup(y);
  pushup(x);
}

伸展操作,是 Splay 特有的保证复杂度的操作,主要功能是将其中一个节点一直旋转到目标节点,并且更改子树的形状,可以证明单次操作复杂度均摊为 $\mathcal O(\log n)$

void splay(int x, int g) {
  while (tr[x].fa != g) {
    int y = tr[x].fa, z = tr[y].fa;
    if (z != g) 
      rotate(get(x) != get(y) ? x : y);
    rotate(x);
  }
  if (g == 0)
    root = x;
}

Splay 的删除操作,可以找到目标数值的前驱和后继,分别旋转到根节点和前驱节点的右子节点。

根据二叉搜索树的性质,后继节点的左节点为目标节点。

void erase(int val) {
  int pre = getPre(val), suf = getSuf(val);
  splay(pre, 0);
  splay(suf, pre);
  int k = tr[suf].son[0];
  if (tr[k].cnt > 1) {
    tr[k].cnt--, tr[k].sz--;
    splay(k, 0); 
  } else {
    tr[suf].son[0] = 0;
    tr[suf].sz--;
    pushup(suf), pushup(pre);
  }
}

普通平衡树的操作具体可以参考代码:链接

Splay 特有的对于序列进行区间翻转操作也比较好理解。

把序列的下标作为二叉搜索树的第一关键字。

对于一个旋转区间 $[l,r]$,我们考虑把这个区间单独领出来,也就是将 $l-1$ 号节点旋转到根节点,$r$ 号节点旋转到 $l-1$ 节点的右儿子,那么 $r$ 号节点的左子树内就是这个区间,然后我们对节点打上旋转懒标记即可。

最后修改:2020 年 08 月 28 日 01 : 22 PM
如果觉得我的文章对你有用,请随意赞赏