Preface BST 的问题 解决方案之一——Splay 右旋 (Zig)、左旋 (Zag) 如何判断是要左旋还是右旋？ Splay 操作【上旋 (旋转到根)】 代码层面的数据结构维护 一些辅助函数 旋转的代码实现 Splay 的代码实现 插入操作 两种查询寻 删除操作、寻找前继、寻找后继 代码 Reference Preface 昨天写了最普通的 BST，今天来写一下 Splay。注意：这一节建立在已经能够理解普通的二叉搜索树的基础上，若有疑问，见上一篇博客。 BST 的问题 首先我们要意识到，最普通的 BST 可能会退化成链。通过插入大小递减的数，我们就可以轻易地让二叉树退化成链，从而是复杂度达到最坏复杂度 $O(n)$。 解决方案之一——Splay Splay 可以解决这样的问题，最然最坏复杂度也是 $O(n)$，但是可以证明，连续的 $m$ 个操作的复杂可以降到 $O(m\log n)$，即均摊复杂度为 $O(\log n)$。这里不给出 Splay 复杂度的证明，可由势能分析证明。我们主要讲一下 Splay 的思想。 Splay 的核心在于，每次操作之后，我们都将该操作对应的节点旋转到根的位置。注意：这里使用了 旋转 一词。接下来我们来解释旋转的过程。 右旋 (Zig)、左旋 (Zag) 要解释「旋转到根」，我们先要引入两个概念：左旋与右旋。 为什么叫右旋和左旋？因为我们是把位置较低的元素 (x / y) 向 (右 / 左) 旋转，达到了较高的位置。 注意：在这张图中，我画了两个 R，意思是 x / y 无论是 R 的左儿子还是右儿子，这个旋转的结果都是不变的。 接下来我们来证明右旋和左旋不会改变二叉树的性质，能让其依旧满足二叉搜索树的定义。 证明： 由于二叉搜索树是递归定义的，所以我们只需要证明图中出现的有限个节点的大小关系保持不变即可。 左图的关系： $$ A < x < B $$ $$ x < y < C $$ $$ B < y $$ 右图的关系： $$ A < x < y $$ $$ B < y < C $$ $$ B > x $$ 不难发现，通过代数变换，就能证明这两个不等式组是完全等价的。 如何判断是要左旋还是右旋？ 答案很简单，如果我们要往上旋转的儿子是左儿子，那就右旋，如果是右儿子，那就左旋。 Splay 操作【上旋 (旋转到根)】 我们之前已经介绍了左旋与右旋，其可以把一个节点 x 降低一个深度 (上移一个单位)。那如果我们想要把一个节点上移使之成为根节点，那我们就需要进行若干个左旋和右旋操作来达成这一问题。 接下来我们来介绍迭代过程中的三种大类型。 (1) 该节点的父亲就是根节点：旋一次，结束迭代 (2) 根节点不是父亲，并且父亲的儿子类型和该节点的儿子类型相同【比方说：父亲是祖父的左儿子，这个节点也是父亲的左儿子】 这种情况下，先旋一次父亲，再旋一次自身 (3) 根节点不是父亲，并且父亲的儿子类型和该节点的儿子类型不同【比方说：父亲是祖父的左儿子，这个节点也是父亲的右儿子】 这种情况下，直接自旋两次即可。 有一张图可以很好地解释 (2) 和 (3)，分别对应图中的 Case 1 和 Case 2 代码层面的数据结构维护 为了方便维护，我们定义如下 struct 以及数据: int cnt = 0; // 维护节点数 int rt = 0; // 根的节点编号 struct node { int val, // 这个节点所代表的值 cnt, // 这个值出现的次数 sz, // 以这个节点为根的子树的大小 fa, // 父节点编号 ch[2]; // ch[0] 左儿子；ch[1] 右儿子 } t[maxn]; 一些辅助函数 // 调试用，遍历 Splay void print(int u) { if (!u) return; print(t[u].ch[0]); for (int i = 0; i < t[u].cnt; i ++) cout << t[u].val << ' '; print(t[u].ch[1]); } // 更新 u 的 size（重新计算） void update_sz(int u) { t[u].sz = t[t[u].ch[0]].sz + t[u].cnt + t[t[u].ch[1]].sz; } // 查询 u 是其父亲的左儿子还是右儿子 int identify(int u) { return t[t[u].fa].ch[1] == u; } // 清除编号为 u 的所有值（在删除节点的时候会用到） void clear(int u) { t[u] = (node) {0, 0, 0, 0, 0, 0}; } // let u be fa's [ch] son // 让 u 成为 fa 的 [ch] (0, 1 左右) 儿子 void connect(int u, int fa, int ch) { t[u].fa = fa; t[fa].ch[ch] = u; } 旋转的代码实现 这里有一张非常不错的图： 可以用我们前面定义的 connect 函数来进行右旋。左旋也是类似的。 这里有一个技巧：B 对于 x 和 x 对于 y 的儿子类型总归是相反的。所以我们可以使用位运算技巧，一次性写完左旋和右旋。 void rotate(int x) { int y = t[x].fa; int R = t[y].fa; int R_ch = identify(y), y_ch = identify(x); // B 为 x 的儿子 // 若 x 为 y 的左儿子，则 B 为 x 的右儿子，执行右旋 zig // 若 x 为 y 的右儿子，则 B 为 x 的左儿子，执行左旋 zag int B = t[x].ch[y_ch ^ 1]; connect(B, y, y_ch); connect(y, x, y_ch ^ 1); connect(x, R, R_ch); update_sz(y); update_sz(x); } Splay 的代码实现 void splay(int u) { // 解释一下下面这个循环： // 1. 只要有父亲就至少会旋 1 次 (先 rotate(u) 再更新 fa 然后判断新 fa) // 2. 如果父亲没有父亲就只旋 1 次 // 这个循环对应了 splay 的三种操作 // 1. 若父亲是根，也就是父亲没有父亲，只旋 1 次 // 2. 若父亲不是根，且当前节点的儿子类型和父亲的儿子类型相同，先旋父亲再旋自己 // 3. 若父亲不是根，且当前节点的儿子类型和父亲的儿子类型不同，旋两次自己 for (int fa = t[u].fa; fa = t[u].fa, fa; rotate(u)) if (t[fa].fa) rotate(identify(u) == identify(fa) ? fa : u); rt = u; } 插入操作 我写的插入操作和普通的 BST 几乎没有区别，只不过有以下要点需要注意： 插入后要以插入完成的节点为目标进行 Splay 插入值可能已经存在，所以要 Splay 的目标并不一定是 cnt int insert(int &u, int fa, int val) { if (!u) { t[u = ++ cnt] = (node) {val, 1, 1, fa, 0, 0}; return u; } t[u].sz ++; if (t[u].val == val) { t[u].cnt ++; return u; } else return insert(t[u].ch[val > t[u].val], u, val); } void insert_splay(int val) { if (!cnt) { rt ++; t[++ cnt] = (node) {val, 1, 1, 0, 0, 0}; return; } int u = insert(rt, 0, val); splay(u); } 两种查询寻 两种查询操作和标准 BST 基本上一样，除了要添加 Splay 操作。 int query_rank(int u, int val) { if (u == 0) { splay(t[u].fa); return 1; } if (t[u].val == val) { int ans = t[t[u].ch[0]].sz + 1; splay(u); return ans; } if (val < t[u].val) return query_rank(t[u].ch[0], val); return t[t[u].ch[0]].sz + t[u].cnt + query_rank(t[u].ch[1], val); } int query_val(int u, int rank) { if (rank > t[t[u].ch[0]].sz && rank <= t[t[u].ch[0]].sz + t[u].cnt) return t[u].val; if (rank <= t[t[u].ch[0]].sz) return query_val(t[u].ch[0], rank); return query_val(t[u].ch[1], rank - t[t[u].ch[0]].sz - t[u].cnt); } 删除操作、寻找前继、寻找后继 删除非常有讲究。在写删除之前，我们不妨先考虑一下前继和后继怎么寻找。借助 Splay，我们发现，寻找前继就等于： (1) 先插入一个我们要寻找的数 (2) 把我们要寻找的数 Splay 到根（插入的时候已经自动帮我们做了） (3) 根的左子树的最大值便是前继（先往左跳，再不停地往右跳直到结束） (4) 删除插入的值 而寻找后继就是： (1) 先插入一个我们要寻找的数 (2) 把我们要寻找的数 Splay 到根（插入的时候已经自动帮我们做了） (3) 根的右子树的最大值便是前继（先往右跳，再不停地往左跳直到结束） (4) 删除插入的值 所以，我们可以给出除了 splay, 插入和删除这三个模块以外地寻找前后继的代码： int pre() { int cur = t[rt].ch[0]; if (!cur) return cur; while (t[cur].ch[1]) cur = t[cur].ch[1]; splay(cur); return cur; } int nxt() { int cur = t[rt].ch[1]; if (!cur) return cur; while (t[cur].ch[0]) cur = t[cur].ch[0]; splay(cur); return cur; } 接下来，我们再来谈删除。我们不妨先把需要删除的节点 Splay 到根，然后分类讨论。 (1) 出现次数大于 1，直接 cnt --，结束。 (2) 需要删除这个节点。 第二种情况又有三种情况： (1) 就剩他一个节点，那就全部删光 (2) 只剩一个儿子，左儿子或者右儿子，这种情况下很容易就能够构造，具体操作见代码 (3) 两个儿子都在。这种情况比较复杂，我们着重讨论。我们可以证明：如下的操作是正确的： 寻找左子树的最大值，即需删除节点的前继 将这个前继 Splay 到根 将原来的右儿子作为现在根的右儿子 我们不妨画个图来证明这样做的正确性。下图是最初始的情况： 我们第一步要进行的操作是要将 x Splay 到根。那我们不妨考察其 Splay 到根之前的情况。由于 x 是前继的性质，所以 x 就是 rt 先向左然后一路向右，所以最后我们必然会达到这样的情况： 经过右旋，自然而然就能达到： 证明了结论的正确性。 代码： void del(int k) { query_rank(rt, k); // 将待删除的元素 Splay 到根 if (t[rt].cnt > 1) { t[rt].cnt --; t[rt].sz --; return; } // 全没了 if (!t[rt].ch[0] && !t[rt].ch[1]) { clear(rt); rt = cnt = 0; return; } if (!t[rt].ch[0]) { int old_rt = rt; rt = t[rt].ch[1]; t[rt].fa = 0; clear(old_rt); return; } if (!t[rt].ch[1]) { int old_rt = rt; rt = t[rt].ch[0]; t[rt].fa = 0; clear(old_rt); return; } int old_rt = rt, y = t[rt].ch[1]; int x = pre(); t[x].ch[1] = y; t[y].fa = x; clear(old_rt); update_sz(rt); } 代码 测试传送门：https://www.luogu.com.cn/problem/P3369 #include <iostream> #define fuck cout << __LINE__ << endl using namespace std; const int maxn = 1e5+5; int cnt = 0, rt = 0; struct node { int val, cnt, sz, fa, ch[2]; } t[maxn]; void print(int u) { if (!u) return; print(t[u].ch[0]); for (int i = 0; i < t[u].cnt; i ++) cout << t[u].val << ' '; print(t[u].ch[1]); } void update_sz(int u) { t[u].sz = t[t[u].ch[0]].sz + t[u].cnt + t[t[u].ch[1]].sz; } int identify(int u) { return t[t[u].fa].ch[1] == u; } void clear(int u) { t[u] = (node) {0, 0, 0, 0, 0, 0}; } // let u be fa's [ch] son // 让 u 成为 fa 的 [ch] (0, 1 左右) 儿子 void connect(int u, int fa, int ch) { t[u].fa = fa; t[fa].ch[ch] = u; } void rotate(int x) { int y = t[x].fa; int R = t[y].fa; int R_ch = identify(y), y_ch = identify(x); // B 为 x 的儿子 // 若 x 为 y 的左儿子，则 B 为 x 的右儿子，执行右旋 zig // 若 x 为 y 的右儿子，则 B 为 x 的左儿子，执行左旋 zag int B = t[x].ch[y_ch ^ 1]; connect(B, y, y_ch); connect(y, x, y_ch ^ 1); connect(x, R, R_ch); update_sz(y); update_sz(x); } void splay(int u) { // 解释一下下面这个循环： // 1. 只要有父亲就至少会旋 1 次 (先 rotate(u) 再更新 fa 然后判断新 fa) // 2. 如果父亲没有父亲就只旋 1 次 // 这个循环对应了 splay 的三种操作 // 1. 若父亲是根，也就是父亲没有父亲，只旋 1 次 // 2. 若父亲不是根，且当前节点的儿子类型和父亲的儿子类型相同，先旋父亲再旋自己 // 3. 若父亲不是根，且当前节点的儿子类型和父亲的儿子类型不同，旋两次自己 for (int fa = t[u].fa; fa = t[u].fa, fa; rotate(u)) if (t[fa].fa) rotate(identify(u) == identify(fa) ? fa : u); rt = u; } int insert(int &u, int fa, int val) { if (!u) { t[u = ++ cnt] = (node) {val, 1, 1, fa, 0, 0}; return u; } t[u].sz ++; if (t[u].val == val) { t[u].cnt ++; return u; } else return insert(t[u].ch[val > t[u].val], u, val); } void insert_splay(int val) { if (!cnt) { rt ++; t[++ cnt] = (node) {val, 1, 1, 0, 0, 0}; return; } int u = insert(rt, 0, val); splay(u); } int pre() { int cur = t[rt].ch[0]; if (!cur) return cur; while (t[cur].ch[1]) cur = t[cur].ch[1]; splay(cur); return cur; } int nxt() { int cur = t[rt].ch[1]; if (!cur) return cur; while (t[cur].ch[0]) cur = t[cur].ch[0]; splay(cur); return cur; } int query_rank(int u, int val) { if (u == 0) { splay(t[u].fa); return 1; } if (t[u].val == val) { int ans = t[t[u].ch[0]].sz + 1; splay(u); return ans; } if (val < t[u].val) return query_rank(t[u].ch[0], val); return t[t[u].ch[0]].sz + t[u].cnt + query_rank(t[u].ch[1], val); } int query_val(int u, int rank) { if (rank > t[t[u].ch[0]].sz && rank <= t[t[u].ch[0]].sz + t[u].cnt) return t[u].val; if (rank <= t[t[u].ch[0]].sz) return query_val(t[u].ch[0], rank); return query_val(t[u].ch[1], rank - t[t[u].ch[0]].sz - t[u].cnt); } void del(int k) { query_rank(rt, k); if (t[rt].cnt > 1) { t[rt].cnt --; t[rt].sz --; return; } // 全没了 if (!t[rt].ch[0] && !t[rt].ch[1]) { clear(rt); rt = cnt = 0; return; } if (!t[rt].ch[0]) { int old_rt = rt; rt = t[rt].ch[1]; t[rt].fa = 0; clear(old_rt); return; } if (!t[rt].ch[1]) { int old_rt = rt; rt = t[rt].ch[0]; t[rt].fa = 0; clear(old_rt); return; } int old_rt = rt, y = t[rt].ch[1]; int x = pre(); t[x].ch[1] = y; t[y].fa = x; clear(old_rt); update_sz(rt); } int main() { int n, opt, x; cin >> n; while (n --> 0) { cin >> opt >> x; if (opt == 1) insert_splay(x); else if (opt == 2) del(x); else if (opt == 3) cout << query_rank(rt, x) << endl; else if (opt == 4) cout << query_val(rt, x) << endl; else if (opt == 5) { insert_splay(x); cout << t[pre()].val << endl; del(x); } else { insert_splay(x); cout << t[nxt()].val << endl; del(x); } } return 0; } Reference https://oi-wiki.org/ds/splay/ https://www.luogu.com.cn/blog/pks-LOVING/more-senior-data-structure-te-bie-qian-di-qian-tan-splay https://www.luogu.com.cn/blog/user19027/solution-p3369
引言 二叉搜索树其实非常常用，但是......我好像从来没写过，一直用的 STL 的模板。为一手写过的二叉树可能就是堆了吧。趁着可靠大先辈学的时候稍微看了一下，大致理解了。（这么晚看这个真的该自裁） Reference 由于内容...十分基础，所以直接放链接了，我觉得写的比较好的教程： https://oi-wiki.org/ds/bst/ 模板题：洛谷 P5076 传送门: https://www.luogu.com.cn/problem/P5076 // 普通二叉搜索树模板 #include <iostream> #define fuck cout << __LINE__ << endl using namespace std; const int maxn = 1e4+5; int cnt = 0; struct node { int val, cnt, size, l, r; } t[maxn]; void print(int u) { if (!u) return; print(t[u].l); for (int i = 0; i < t[u].cnt; i ++) cout << t[u].val << " "; print(t[u].r); } // 引用 u 的好处是能够在最后直接把新建的节点的编号赋给父亲的某个儿子 void insert(int &u, int val) { if (!u) { t[u = ++ cnt] = (node) {val, 1, 1, 0, 0}; return; } t[u].size ++; if (t[u].val == val) t[u].cnt ++; else if (val < t[u].val) insert(t[u].l, val); else insert(t[u].r, val); } int query_last(int u, int val, int ans) { if (val > t[u].val) { if (!t[u].r) return t[u].val; return query_last(t[u].r, val, t[u].val); } else { if (!t[u].l) return ans; return query_last(t[u].l, val, ans); } } int query_next(int u, int val, int ans) { if (val < t[u].val) { if (!t[u].l) return t[u].val; return query_next(t[u].l, val, t[u].val); } else { if (!t[u].r) return ans; return query_next(t[u].r, val, ans); } } int query_rank(int u, int val) { if (u == 0) return 1; if (t[u].val == val) return t[t[u].l].size + 1; if (val < t[u].val) return query_rank(t[u].l, val); return t[u].cnt + t[t[u].l].size + query_rank(t[u].r, val); } int query(int u, int rank) { if (rank > t[t[u].l].size && rank <= t[t[u].l].size + t[u].cnt) return t[u].val; if (rank <= t[t[u].l].size) return query(t[u].l, rank); return query(t[u].r, rank - t[t[u].l].size - t[u].cnt); } signed main() { int n; cin >> n; while (n --> 0) { int a, m; cin >> a >> m; if (a == 1) { cout << query_rank(1, m) << endl; } else if (a == 2) { cout << query(1, m) << endl; } else if (a == 3) { cout << query_last(1, m, -2147483647) << endl; } else if (a == 4) { cout << query_next(1, m, 2147483647) << endl; } else if (a == 5) { if (!cnt) { t[++ cnt] = (node) {m, 1, 1, 0, 0}; } else { int a = 1; insert(a, m); } } // print(1); } return 0; } 说几个要注意的点： 插入第一个点的时候要特判 插入使用了一个引用传参的 trick，可以用于方便的给新建节点的父节点赋值 前继搜索和后继搜索的时候情况比较复杂，可能出现「如果递归下去就可能不再是答案的情况」，比方说「寻找后继，当前的节点的值却比搜索值小，但却没有右儿子（即这个节点不能作为答案，并且没有符合要求的子节点可以递归）」，所以我们会使用第三个参数 ans 记录上一个符合要求的答案，碰到这种情况直接 return