RE：从零开始的数据结构生活

今天突然想打打splay，结果发现以前学的都忘光了，所以只能从头开始啦~

splay是基于二叉搜索树的结构，通过旋转来完成各种操作。 所以splay的基本性质：

左儿子的权值都小于父节点的权值， 右儿子的权值都大于父节点的权值

splay的功能：

询问数的排名，查询k大的数，查询一个数的前驱和后继

时间复杂度均摊O(log n)

关于splay的具体实现：

结构体里

struct node { node *ch[2], *f; int sz, cnt, v; void maintain() { sz = cnt + ch[0] -> sz + ch[1] -> sz; } int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } int dir() { return f -> ch[1] == this; } void setc(node *x, int d) { (ch[d] = x) -> f = this; } }T[SZ], *root, *null;

各成员函数的作用：

maintain()：用来更新子树大小和当前数值的个数 cmp() ：比较x和当前节权值的大小，以便继续向儿子方向转移 dir() ：如果当前节点是右儿子则返回真，否则返回假 setc() : 把x置为当前节点的左儿子或右儿子

关于插入操作：

void insert(node *p, int x) { if(root == null) //如果树为空，直接插入 { root = newnode(x, null); return ; } while(p != null) { p -> sz++; int d = p -> cmp(x); if(d == -1) //要插入的值与当前节点的值相等 { p -> cnt++; break; } if(p -> ch[d] == null) //没有儿子了，直接插入 { p -> ch[d] = newnode(x, p); p = p -> ch[d]; break; } p = p -> ch[d]; } splay(p); //把p旋转至根节点位置 }

关于删除操作：

void erase(node *p, int x) { while(p != null) { p -> sz--; int d = p -> cmp(x); if(d == -1) { p -> cnt--; break; } p = p -> ch[d]; } //找到x的过程 if(p -> cnt) return ; //如果x不只一个，直接返回 splay(p); //将x旋转至根节点处 if(p -> ch[0] == null) //如果没有左儿子，则右儿子做根节点 { root = p -> ch[1]; root -> f = null; return ; } if(p -> ch[1] == null) //如果没有右儿子，左儿子做根节点 { root = p -> ch[0]; root -> f = null; return ; } p = p -> ch[0]; //需要满足基本性质 while(p -> ch[1] != null) p = p -> ch[1]; splay(p, root); p -> ch[1] = root -> ch[1]; p -> ch[1] -> f = p; p -> f = null; p -> maintain(); root = p; }

重头戏！！！splay() 和 rotate()!

void splay(node *p, node *rt = null) { while(p -> f != rt) { if(p -> f -> f == rt) //若p的父亲为根节点，直接旋转 rotate(p); else { if(p -> dir() == p -> f -> dir()) //p与它的父亲均为左儿子或右儿子 rotate(p -> f), rotate(p); else rotate(p), rotate(p); //否则 连续旋转两次p } } p -> maintain(); //更新节点 } void rotate(node *p) { node *fa = p -> f; int d = p -> dir(); fa -> f -> setc(p, fa -> dir()); fa -> setc(p -> ch[d ^ 1], d); fa -> maintain(); p -> setc(fa, d ^ 1); p -> maintain(); if(fa == root) root = p; }

之前一直搞不懂结构体里的setc()函数，现在终于理解了。

模拟rotate()的过程：

当前节点为p，p的父节点为黄色，p的左儿子为蓝色，右儿子为红色

首先将p的父节点置为原父节点的父节点

将p的右儿子置为原父节点的右儿子，以保证满足基本性质

将p的原父节点置为p的左儿子

大功告成！

关于查询操作：

int ask_rank(node *p, int x) //查询一个数的排名 { int ans = 0; while(p != null) { int d = p -> cmp(x); if(d == -1) return ans + p -> ch[0] -> sz + 1; if(d == 1) ans += p -> ch[0] -> sz + p -> cnt; p = p -> ch[d]; } return -1; } int ask_num(node *p, int k) //查询k大的数 { while(p != null) { int l = p -> ch[0] -> sz + 1; int r = p -> ch[0] -> sz + p -> cnt; if(l <= k && k <= r) return p -> v; if(k > r) k -= r, p = p -> ch[1]; else p = p -> ch[0]; } } int ask_pre(node *p, int x) //查询前驱 { int ans = 0; while(p != null) { if(p -> v < x) ans = p -> v, p = p -> ch[1]; else p = p -> ch[0]; } return ans; } int ask_suf(node *p, int x) //查询后继 { int ans = 0; while(p != null) { if(p -> v > x) ans = p -> v, p = p -> ch[0]; else p = p -> ch[1]; } return ans; }

最后附一份完整的模板 PS：以BZOJ 3224 为例题

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int SZ = 1000010; const int INF = 1e9 + 10; struct node { node *ch[2], *f; int sz, cnt, v; void maintain() { sz = cnt + ch[0] -> sz + ch[1] -> sz; } int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } int dir() { return f -> ch[1] == this; } void setc(node *x, int d) { (ch[d] = x) -> f = this; } }T[SZ], *root, *null; int Tcnt = 0; node* newnode(int x, node *f) { node *k = T + (++Tcnt); k -> v = x; k -> ch[0] = k -> ch[1] = null; k -> sz = k -> cnt = 1; k -> f = f; return k; } void rotate(node *p) { node *fa = p -> f; int d = p -> dir(); fa -> f -> setc(p, fa -> dir()); fa -> setc(p -> ch[d ^ 1], d); fa -> maintain(); p -> setc(fa, d ^ 1); p -> maintain(); if(fa == root) root = p; } void splay(node *p, node *rt = null) { while(p -> f != rt) { if(p -> f -> f == rt) //若p的父亲为根节点，直接旋转 rotate(p); else { if(p -> dir() == p -> f -> dir()) //p与它的父亲均为左儿子或右儿子 rotate(p -> f), rotate(p); else rotate(p), rotate(p); //否则 } } p -> maintain(); //更新节点 } void insert(node *p, int x) { if(root == null) //如果树为空，直接加入 { root = newnode(x, null); return ; } while(p != null) { p -> sz++; int d = p -> cmp(x); if(d == -1) //要插入的值与当前节点的值相等 { p -> cnt++; break; } if(p -> ch[d] == null) //没有儿子了，直接加入 { p -> ch[d] = newnode(x, p); p = p -> ch[d]; break; } p = p -> ch[d]; } splay(p); //把p旋转至根节点位置 } //RE:从零开始的数据结构生活 void erase(node *p, int x) { while(p != null) { p -> sz--; int d = p -> cmp(x); if(d == -1) { p -> cnt--; break; } p = p -> ch[d]; } if(p -> cnt) return ; splay(p); if(p -> ch[0] == null) { root = p -> ch[1]; root -> f = null; return ; } if(p -> ch[1] == null) { root = p -> ch[0]; root -> f = null; return ; } p = p -> ch[0]; while(p -> ch[1] != null) p = p -> ch[1]; splay(p, root); p -> ch[1] = root -> ch[1]; p -> ch[1] -> f = p; p -> f = null; p -> maintain(); root = p; } int ask_rank(node *p, int x) { int ans = 0; while(p != null) { int d = p -> cmp(x); if(d == -1) return ans + p -> ch[0] -> sz + 1; if(d == 1) ans += p -> ch[0] -> sz + p -> cnt; p = p -> ch[d]; } return -1; } int ask_num(node *p, int k) { while(p != null) { int l = p -> ch[0] -> sz + 1; int r = p -> ch[0] -> sz + p -> cnt; if(l <= k && k <= r) return p -> v; if(k > r) k -= r, p = p -> ch[1]; else p = p -> ch[0]; } } int ask_pre(node *p, int x) { int ans = 0; while(p != null) { if(p -> v < x) ans = p -> v, p = p -> ch[1]; else p = p -> ch[0]; } return ans; } int ask_suf(node *p, int x) { int ans = 0; while(p != null) { if(p -> v > x) ans = p -> v, p = p -> ch[0]; else p = p -> ch[1]; } return ans; } void init() //初始化 { null = newnode(-INF, null); //null为根 null -> sz = null -> cnt = 0; root = null; } int main() { init(); int n; scanf("%d", &n); while(n--) { int op, x; scanf("%d%d", &op, &x); switch(op) { case 1 : insert(root, x); break; case 2 : erase(root, x); break; case 3 : printf("%d\n", ask_rank(root, x)); break; case 4 : printf("%d\n", ask_num(root, x)); break; case 5 : printf("%d\n", ask_pre(root, x)); break; case 6 : printf("%d\n", ask_suf(root, x)); break; } } return 0; }

转载于:https://www.cnblogs.com/Loi-Vampire/p/6017027.html

相关资源：JAVA上百实例源码以及开源项目