Splay

学习记录

Splay

Splay 是一个基于 BST (Binary Search Tree 二叉搜索树) 的动态数据结构。
Splay 所操作的对象必须要有 $key$ 且 $key$ 严格弱序（可以计算排名）。
它支持以均摊单次 $\mathcal O(\log n)$ 的时间复杂度进行如下操作：

  1. insert(x) 插入一个元素，以 $x$ 为 $key$。
  2. erase(x) 删除 $key=x$ 的元素。
  3. find(x) 查找值为 $x$ 的元素的信息。
  4. at(k) 查找排名第 $k$ 的元素的信息。
  5. range(l, r) 提取出排名在 $l \sim r$ 的区间
  6. merge(tr) 将另外一颗 splay 树拼接到这颗 splay 树上。
    要求：若要将 $Tb$ merge 到 $Ta$，必须满足 $\max\{i : i \in Tb\} \le \min\{j : j \in Ta\}$ 或者 $\min\{i : i \in Tb\} \ge \max\{j : j \in Ta\}$

性质

假设现在 Splay 维护了一个有序的序列，以 $key$ 为关键字。
这里，给出 Splay 的几条性质：

  1. Splay 树上的每一个节点都代表原序列中的一段区间。
  2. Splay 树上的每一颗子树都是 Splay 树。
  3. Splay 树的中序遍历就是排好序的原序列。
  4. Splay 树支持缓存，即访问越频繁，访问速度越快。
  5. Splay 不支持可持久化。

算法流程

节点构造

我们使用一个三元组 $(size, key, ch_0, ch_1, fa, dat)$ 来表示 Splay 树上的一个节点。

  • $size$：当前子树内元素个数。
  • $key$：当前节点对应元素的键值。
  • $ch_{0/1}$：左/右孩子。
  • $fa$：父亲。
  • $dat$：节点的附加信息。

建树

如果我们有一个已经有序的序列 $a_{1…n} = (key_1, dat_1), (key_2, dat_2), \dots, (key_n, dat_n)$，
那我们直接根据 BST 的性质建树即可，即建一颗只有右孩子的二叉树。

  • 通常来说，为了方便之后的操作，我们会设置两个哨兵节点，一首一尾。
graph TD
    A{Root} --> B[NULL]; A --> C(1);
    C --> D[NULL]; C --> E(2);
    E --> F[NULL]; E --> G(3);
    G --> H[NULL]; G --> I{Guard}

维护

在节点上

分为 pushup 和 pushdown，其中 pushup 需要统计 $size$ 即 $size := size_0 + 1 + size_1$。

在树的结构上

分为 zig、zig-zig、zig-zag。

flowchart LR
subgraph Before[ ]
    direction TB
    f0((anc)) <--> y0((y))
    y0 <--> x0((x))
    x0 <--> a0(A)
    x0 <--> b0(B)
    y0 <--> c0(C)
end

subgraph After[ ]
    direction TB
    f1((anc)) <--> x1((x))
    x1 <--> a1(A)
    x1 <--> y1((y))
    y1 <--> b1(B)
    y1 <--> c1(C)
end

Before -->|右旋| After
Before <---|左旋| After
linkStyle 0,1,3,10 stroke:red,stroke-width:2px
linkStyle 5,7,8,11 stroke:cyan,stroke-width:2px
flowchart LR
subgraph Beg1[ ]
    direction TB
    x0((x)) --> y0((y)) --> z0((z)) --> c0(C)
    x0 --> a0(A)
    y0 --> b0(B)
    z0 --> d0(D)
end
subgraph Mid1[ ]
    direction TB
    y1((y)) --> x1((x)) --> a1(A)
    x1 --> b1(B)
    y1 --> z1((z)) --> c1(C)
    z1 --> d1((D))
end
subgraph End1[ ]
    direction TB
    z2((z)) --> a2(A)
    z2 --> y2((y)) --> b2(B)
    y2 --> x2((x)) --> c2(C)
    x2 --> d2(D)
end
Beg1 -->|右旋| Mid1 -->|右旋| End1
Beg1 <---|左旋| Mid1 <---|左旋| End1
linkStyle 18,19 stroke:red,stroke-width:2px
linkStyle 20,21 stroke:green,stroke-width:2px
style y0 fill:red
style x1 fill:red
style z1 fill:green
style y2 fill:green
flowchart LR
subgraph Beg[ ]
    direction TB;
    x0((x)) --> y0((y)) --> a0(A); y0 --> z0((z)) --> b0(B); z0 --> c0(C); x0 --> d0(D);
end
subgraph Mid[ ]
    direction TB;
    x1((x)) --> z1((z)) --> y1((y)) --> a1(A); y1 --> b1(B); z1 --> c1(C); x1 --> d1(D);
end
subgraph End[ ]
    direction TB;
    z2((z)) --> x2((x)) --> a2(A); x2 --> b2(B); z2 --> y2((y)) --> c2(C); y2 --> d2(D);
end
subgraph iMid[ ]
    direction TB;
    x3((x)) --> a3(A); x3 --> z3((z)) --> b3(B); z3 --> y3((y)) --> c3(C); y3 --> d3(C);
end
subgraph iBeg[ ]
    direction TB;
    x4((x)) --> a4(A); x4 --> y4((y)) --> z4((z)) --> b4(B); z4 --> c4(C); y4 --> d4(D);
end
Beg -->|右旋| Mid -->|右旋| End
iBeg -->|左旋| iMid -->|左旋| End
linkStyle 30,31 stroke:red,stroke-width:2px
linkStyle 32,33 stroke:green,stroke-width:2px
style z0 fill:red
style z1 fill:red
style z3 fill:green
style z4 fill:green

如你所见，我们这么大费周折地进行旋转，无非就是为了在保证 BST 的性质下尽可能地降低当前节点的深度。
所以只要我们一直做 zig-zig 或者 zig-zag，直到不行为止。最后判断要不要补一个 zig 就可以将给定节点旋转到根了。
其实 rotate 关键就是重建 3 条边（有的时候因为空节点没那么多），注意双向（$ch,fa$），记牢了不容易忘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node {
    Node *ch[2], *fa;
    bool type() const { return fa->ch[1] == this; } // 返回节点的类型（左/右）
    // Data & Func decl here.....
    void rotate() {
        fa->pushdown(), pushdown();
        auto anc = fa->fa;
        int tp = type(), ftp = anc ? fa->type() : -1;
        fa->ch[tp] = ch[tp ^ 1]; if (ch[tp ^ 1]) ch[tp ^ 1]->fa = fa;
        ch[tp ^ 1] = fa; fa->fa = this;
        if (anc) anc->ch[ftp] = this; fa = anc;
        ch[tp ^ 1]->pushup(), pushup();
    }
}
void splay(Node *u, Node *goal = nullptr) {
    while (u->fa != goal) {    // 这两行里面外面一样的
        if (u->fa->fa != goal) // 一般喜欢放里面，情况少
            u->type() == u->fa->type() ? u->fa->rotate() : u->rotate();
        u->rotate();
    }
    if (!goal) root = u; // 注意如果旋转到真的树根，要更新 Splay 的 root
}

查询

$\tt{find(x)}$

令 $\text{value}_{0/1}$ 表示左/右孩子的 $\text{value}$，
直接使用类似于二分的策略，当前节点 $\begin{cases}
size_0 + 1 = x && \text{Ret} & \texttt{this} \\
x \le size_0 && \text{Ret} & \texttt{find(x)} \text{ of } ch_0 \\
x \gt size_0 + 1 && \text{Ret} & \texttt{find(x} - sz_0 - 1\texttt{)} \text{ of } ch_1
\end{cases}$。所以还是很简单的。
注意，为了确保正确的时间复杂度和 Splay 的缓存机制，请你必须将查询节点旋转到根。

$\tt{at(x)}$

这个就是直接 BST 上搜索就可以了。如果 $x \le key$ 就返回 $ch_0.\tt{at(x)}$，否则就是 $ch_1.\tt{at(x)}$。如果发现 $ch_{0/1}$ 是空的那就结束。
注意最后旋转到根。

重点注意

  • 需要在访问节点的 $ch_?$ 的时候进行 pushdown，不要忘记。

修改

先调用 $\tt{find(x)}$，对他的 $dat$ 进行修改，然后旋转到根。

合并

注意到我们将排名为 $size$ 的节点旋转到根后，右子树为空，直接把另外一颗 Splay 树接上去就可以了（反之亦然）。