多种语言网站建设,seo公司是做什么的,网站制作职业,哪里网站建设好 Splay 定义 Splay 树, 或 伸展树#xff0c;是一种平衡二叉查找树#xff0c;它通过 Splay/伸展操作 不断将某个节点旋转到根节点#xff0c;使得整棵树仍然满足二叉查找树的性质#xff0c;能够在均摊 O ( log n ) O(\log n) O(logn) 时间内完成插入#xff0c;查… Splay 定义 Splay 树, 或 伸展树是一种平衡二叉查找树它通过 Splay/伸展操作 不断将某个节点旋转到根节点使得整棵树仍然满足二叉查找树的性质能够在均摊 O ( log n ) O(\log n) O(logn) 时间内完成插入查找和删除操作并且保持平衡而不至于退化为链。
Splay 树由 Daniel Sleator 和 Robert Tarjan 于 1985 年发明。
结构 节点维护信息 x tot fa[i] ch[i][0/1] val[i] cnt[i] sz[i] 根节点编号 节点个数 父亲 左右儿子编号 节点权值 权值出现次数 子树大小 struct Splay{ int fa, ch[2], val, cnt, siz; }tree[MAXN]; 操作 基本操作 maintain(x)在改变节点位置后将节点 x x x 的 size \text{size} size 更新。 get(x)判断节点 x x x 是父亲节点的左儿子还是右儿子。 clear(x)销毁节点 x x x。 void maintain(int x){ tree[x].siz tree[tree[x].ch[0]].siz tree[tree[x].ch[1]].siz tree[x].cnt; } bool get(int x){ if(x tree[tree[x].fa].ch[1])return true; else return false; } void clear(int x){ tree[tree[x].ch[0]].siz 0; tree[tree[x].ch[1]].siz 0; tree[x].fa 0;tree[x].val 0; tree[x].cnt 0;tree[x].siz 0; } 旋转操作 为了使 Splay 保持平衡而进行旋转操作旋转的本质是将某个节点上移一个位置。
旋转需要保证
整棵 Splay 的中序遍历不变(不能破坏二叉查找树的性质)。 受影响的节点维护的信息依然正确有效。 root 必须指向旋转后的根节点。 在 Splay 中旋转分为两种左旋和右旋。
过程 具体分析旋转步骤(假设需要旋转的节点为 x x x其父亲为 y y y以右旋为例)
将 y y y 的左儿子指向 x x x 的右儿子且 x x x 的右儿子(如果 x x x 有右儿子的话)的父亲指向 y y ych[y][0] ch[x][1];fa[ch[x][1]] y; 将 x x x 的右儿子指向 y y y且 y y y 的父亲指向 x x xch[x][chk^1] y;fa[y] x; 如果原来的 y y y 还有父亲 z z z那么把 z z z 的某个儿子(原来 y y y 所在的儿子位置)指向 x x x且 x x x 的父亲指向 z z z。fa[x] z;if(z)ch[z][y ch[z][1]] x; 实现 void maintain(int x){ tree[x].siz tree[tree[x].ch[0]].siz tree[tree[x].ch[1]].siz tree[x].cnt; } bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } Splay 操作 Splay 操作规定每访问一个节点 x x x 后都要强制将其旋转到根节点。
Splay 操作即对 x x x 做一系列的 Splay 步骤。每次对 x x x 做一次 splay 步骤 x x x 到根节点的距离都会更近。定义 p p p 为 x x x 的父节点。Splay 步骤有三种具体分为六种情况
实现 void maintain(int x){ tree[x].siz tree[tree[x].ch[0]].siz tree[tree[x].ch[1]].siz tree[x].cnt; } bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } 插入操作 过程 插入操作是一个比较复杂的过程具体步骤如下(假设插入的值为 k k k)
如果树空了则直接插入根并退出。 如果当前节点的权值等于 k k k 则增加当前节点的大小并更新节点和父亲的信息将当前节点进行 Splay 操作。 否则按照二叉查找树的性质向下找找到空节点就插入即可(请不要忘记 Splay 操作)。 实现 void maintain(int x){ tree[x].siz tree[tree[x].ch[0]].siz tree[tree[x].ch[1]].siz tree[x].cnt; } bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } void insert(int k){ if(!root){ tree[tot].val k;tree[tot].cnt; root tot;maintain(root);return; } int cur root, f 0; while(true){ if(tree[cur].val k){ tree[cur].cnt; maintain(cur);maintain(f); splay(cur);break; } f cur;cur tree[f].ch[tree[f].val k]; if(!cur){ tree[tot].val k;tree[tot].cnt;tree[tot].fa f; tree[f].ch[tree[f].val k] tot; maintain(tot);maintain(f);splay(tot);break; } } } 查询 x 的排名 过程 根据二叉查找树的定义和性质显然可以按照以下步骤查询 x x x 的排名
如果 x x x 比当前节点的权值小向其左子树查找。 如果 x x x 比当前节点的权值大将答案加上左子树( s i z e size size)和当前节点( c n t cnt cnt)的大小向其右子树查找。 如果 x x x 与当前节点的权值相同将答案加 1 1 1 并返回。 注意最后需要进行 Splay 操作。
实现 bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } int getrank(int k){ int res 0, cur root; while(true){ if(k tree[cur].val)cur tree[cur].ch[0]; else{ res tree[tree[cur].ch[0]].siz; if(k tree[cur].val){splay(cur);return res 1;} res tree[cur].cnt;cur tree[cur].ch[1]; } } } 查询排名 x 的数 过程 设 k k k 为剩余排名具体步骤如下
如果左子树非空且剩余排名 k k k 不大于左子树的大小 s i z e size size那么向左子树查找。 否则将 k k k 减去左子树的和根的大小。如果此时 k k k 的值小于等于 0 0 0则返回根节点的权值否则继续向右子树查找。 实现 bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } int getval(int k){ int cur root; while(true){ if(tree[cur].ch[0] k tree[tree[cur].ch[0]].siz)cur tree[cur].ch[0]; else{k - tree[tree[cur].ch[0]].siz tree[cur].cnt; if(k 0){splay(cur);return tree[cur].val;} cur tree[cur].ch[1]; } } } 查询前驱 过程 前驱定义为小于 x x x 的最大的数那么查询前驱可以转化为将 x x x 插入(此时 x x x 已经在根的位置了)前驱即为 x x x 的左子树中最右边的节点最后将 x x x 删除即可。
实现 bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } int getpre(){ int cur tree[root].ch[0]; if(!cur)return cur; while(tree[cur].ch[1])cur tree[cur].ch[1]; splay(cur);return cur; } 查询后继 过程 后继定义为大于 x x x 的最小的数查询方法和前驱类似 x x x 的右子树中最左边的节点。
实现 bool get(int x){ return x tree[tree[x].fa].ch[1]; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } int getnxt(){ int cur tree[root].ch[1]; if(!cur)return cur; while(tree[cur].ch[0])cur tree[cur].ch[0]; splay(cur);return cur; } 合并两棵树 过程 合并两棵 Splay 树设两棵树的根节点分别为 x x x 和 y y y那么我们要求 x x x 树中的最大值小于 y y y 树中的最小值。合并操作如下
如果 x x x 和 y y y 其中之一或两者都为空树直接返回不为空的那一棵树的根节点或空树。 否则将 x x x 树中的最大值 Splay \operatorname{Splay} Splay 到根然后把它的右子树设置为 y y y 并更新节点的信息然后返回这个节点。 删除操作 过程 删除操作也是一个比较复杂的操作具体步骤如下
首先将 x x x 旋转到根的位置。
如果 c n t [ x ] 1 cnt[x]1 cnt[x]1(有不止一个 x x x)那么将 c n t [ x ] cnt[x] cnt[x] 减 1 1 1 并退出。 否则合并它的左右两棵子树即可。 实现 void maintain(int x){ tree[x].siz tree[tree[x].ch[0]].siz tree[tree[x].ch[1]].siz tree[x].cnt; } bool get(int x){ return x tree[tree[x].fa].ch[1]; } void clear(int x){ tree[tree[x].ch[0]].siz 0; tree[tree[x].ch[1]].siz 0; tree[x].fa 0;tree[x].val 0; tree[x].cnt 0;tree[x].siz 0; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } int getrank(int k){ int res 0, cur root; while(true){ if(k tree[cur].val)cur tree[cur].ch[0]; else{ res tree[tree[cur].ch[0]].siz; if(k tree[cur].val){splay(cur);return res 1;} res tree[cur].cnt;cur tree[cur].ch[1]; } } } int getpre(){ int cur tree[root].ch[0]; if(!cur)return cur; while(tree[cur].ch[1])cur tree[cur].ch[1]; splay(cur);return cur; } void remove(int k){ getrank(k); if(tree[root].cnt 1){tree[root].cnt–;maintain(root);return;} if(!tree[root].ch[0] !tree[root].ch[1]){clear(root);root 0;return;} if(!tree[root].ch[0]){ int cur root;root tree[root].ch[1]; tree[root].fa 0;clear(cur);return; } if(!tree[root].ch[1]){ int cur root;root tree[root].ch[0]; tree[root].fa 0;clear(cur);return; } int cur root, x getpre(); tree[tree[cur].ch[1]].fa root; tree[root].ch[1] tree[cur].ch[1]; clear(cur);maintain(root); } 实现 #include #define MAXN 100005 using namespace std; int n, opt, x, root, tot; struct splay{ int fa, ch[2], val, cnt, siz; }tree[MAXN]; int read(){ int t 1, x 0;char ch getchar(); while(!isdigit(ch)){if(ch ‘-’)t -1;ch getchar();} while(isdigit(ch)){x (x 1) (x 3) (ch ^ 48);ch getchar();} return x * t; } void write(int x){ if(x 0){putchar(‘-’);x -x;} if(x 10)write(x/ 10); putchar(x % 10 ^ 48); } void maintain(int x){ tree[x].siz tree[tree[x].ch[0]].siz tree[tree[x].ch[1]].siz tree[x].cnt; } bool get(int x){ return x tree[tree[x].fa].ch[1]; } void clear(int x){ tree[tree[x].ch[0]].siz 0; tree[tree[x].ch[1]].siz 0; tree[x].fa 0;tree[x].val 0; tree[x].cnt 0;tree[x].siz 0; } void rotate(int x){ int y tree[x].fa, z tree[y].fa, chk get(x); tree[y].ch[chk] tree[x].ch[chk ^ 1]; if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa y; tree[x].ch[chk ^ 1] y; tree[y].fa x;tree[x].fa z; if(z ! 0)tree[z].ch[y tree[z].ch[1]] x; maintain(x);maintain(y); } void splay(int x){ for(int f tree[x].fa ; f tree[x].fa, f ; rotate(x)) if(tree[f].fa)rotate(get(x) get(f) ? f : x); root x; } void insert(int k){ if(!root){ tree[tot].val k;tree[tot].cnt; root tot;maintain(root);return; } int cur root, f 0; while(true){ if(tree[cur].val k){ tree[cur].cnt; maintain(cur);maintain(f); splay(cur);break; } f cur;cur tree[f].ch[tree[f].val k]; if(!cur){ tree[tot].val k;tree[tot].cnt;tree[tot].fa f; tree[f].ch[tree[f].val k] tot; maintain(tot);maintain(f);splay(tot);break; } } } int getrank(int k){ int res 0, cur root; while(true){ if(k tree[cur].val)cur tree[cur].ch[0]; else{ res tree[tree[cur].ch[0]].siz; if(k tree[cur].val){splay(cur);return res 1;} res tree[cur].cnt;cur tree[cur].ch[1]; } } } int getval(int k){ int cur root; while(true){ if(tree[cur].ch[0] k tree[tree[cur].ch[0]].siz)cur tree[cur].ch[0]; else{k - tree[tree[cur].ch[0]].siz tree[cur].cnt; if(k 0){splay(cur);return tree[cur].val;} cur tree[cur].ch[1]; } } } int getpre(){ int cur tree[root].ch[0]; if(!cur)return cur; while(tree[cur].ch[1])cur tree[cur].ch[1]; splay(cur);return cur; } int getnxt(){ int cur tree[root].ch[1]; if(!cur)return cur; while(tree[cur].ch[0])cur tree[cur].ch[0]; splay(cur);return cur; } void remove(int k){ getrank(k); if(tree[root].cnt 1){tree[root].cnt–;maintain(root);return;} if(!tree[root].ch[0] !tree[root].ch[1]){clear(root);root 0;return;} if(!tree[root].ch[0]){ int cur root;root tree[root].ch[1]; tree[root].fa 0;clear(cur);return; } if(!tree[root].ch[1]){ int cur root;root tree[root].ch[0]; tree[root].fa 0;clear(cur);return; } int cur root, x getpre(); tree[tree[cur].ch[1]].fa root; tree[root].ch[1] tree[cur].ch[1]; clear(cur);maintain(root); } int main(){ n read(); for(int i 1 ; i n ; i ){ opt read();x read(); switch(opt){ case 1:insert(x);break; case 2:remove(x);break; case 3:write(getrank(x));putchar(‘\n’);break; case 4:write(getval(x));putchar(‘\n’);break; case 5:insert(x);write(tree[getpre()].val);putchar(‘\n’);remove(x);break; case 6:insert(x);write(tree[getnxt()].val);putchar(‘\n’);remove(x);break; default:break; } } return 0; } Splay 操作的时间复杂度 因为 zig 和 zag 是 对称 操作我们只需要对 zigzig−zigzig−zag 操作分析复杂度。采用势能分析定义一个 n n n 个节点的 Splay 树进行了 m m m 次 Splay 步骤。可记 w ( x ) [ log ( size ( x ) ) ] w(x)[\log(\operatorname{size}(x))] w(x)[log(size(x))], 定义势能函数为 φ ∑ w ( x ) \varphi \sum w(x) φ∑w(x), φ ( 0 ) ≤ n log n \varphi (0) \leq n \log n φ(0)≤nlogn在第 i i i 次操作后势能为 φ ( i ) \varphi (i) φ(i), 则我们只需要求出初始势能和每次的势能变化量的和即可。
由此可见三种 Splay 步骤的势能全部可以缩放为 ≤ 3 ( w ′ ( x ) − w ( x ) ) \leq 3(w(x)−w(x)) ≤3(w′(x)−w(x)). 令 w ( n ) ( x ) w ′ ( n − 1 ) ( x ) w^{(n)}(x)w^{(n-1)}(x) w(n)(x)w′(n−1)(x), w ( 0 ) ( x ) w ( x ) w^{(0)}(x)w(x) w(0)(x)w(x), 假设 Splay 操作一次依次访问了 x 1 , x 2 , ⋯ , x n x_{1}, x_{2}, \cdots, x_{n} x1,x2,⋯,xn, 最终 x 1 x_{1} x1 成为根节点我们可以得到 3 ( ∑ i 0 n − 2 ( w ( i 1 ) ( x 1 ) − w ( i ) ( x 1 ) ) w ( n ) − w ( n − 1 ) ( x 1 ) ) 1 3 ( w ( n ) − w ( x 1 ) ) 1 ≤ log n \begin{aligned} 3\left(\sum_{i0}^{n-2}\left(w^{(i1)}(x_{1})-w^{(i)}(x_{1})\right)w(n)−w^{(n-1)}(x_{1})\right)1 3(w(n)−w(x_{1}))1 \\ \leq \log n \end{aligned} 3(i0∑n−2(w(i1)(x1)−w(i)(x1))w(n)−w(n−1)(x1))13(w(n)−w(x1))1≤logn
继而可得 ∑ i 1 m ( φ ( m − i 1 ) − φ ( m − i ) ) φ ( 0 ) n log n m log n \sum_{i1}^m (\varphi (m-i1)−\varphi (m−i)) \varphi (0) n \log nm \log n i1∑m(φ(m−i1)−φ(m−i))φ(0)nlognmlogn
因此对于 n n n 个节点的 Splay 树做一次 Splay 操作的均摊复杂度为 O ( log n ) O(\log n) O(logn)。因此基于 Splay 的插入查询删除等操作的时间复杂度也为均摊 O ( log n ) O(\log n) O(logn)。
