二叉搜索树是一种二叉树的树形数据结构,其定义如下: 空树是二叉搜索树。 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 二叉搜索树上的基本操作所花费的时间与这棵树的高度成\(\color{#40c0bb}{正比}\)。对于一个有 \(n\) 个结点的二叉搜索树中,这些操作的最优时间复杂度为 \(O(\log n)\),最坏为 \(O(n)\)。随机构造这样一棵二叉搜索树的\(\color{#40c0bb}{期望高度}\)为 \(O(\log n)\)。 其实也就是定义 设 \(x\) 是二叉搜索树中的一个结点。 如果 \(y\) 是 \(x\) 左子树中的一个结点,那么 \(y.key≤x.key\)。 如果 \(y\) 是 \(x\) 右子树中的一个结点,那么 \(y.key≥x.key\)。 在二叉搜索树中: 若任意结点的左子树不空,则左子树上所有结点的值均不大于它的根结点的值。 若任意结点的右子树不空,则右子树上所有结点的值均不小于它的根结点的值。 任意结点的左、右子树也分别为二叉搜索树。 二叉搜索树通常可以高效地完成以下操作: 查找最小/最大值 搜索元素 插入一个元素 删除一个元素 求元素的排名 查找排名为 k 的元素 由二叉搜索树的复杂度分析可知:操作的复杂度与树的高度 \(h\) 有关。 那么我们可以通过一定操作维持树的高度(平衡性)来降低操作的复杂度,这就是\(\color{#40c0bb}{平衡树}\)。 \(\color{#40c0bb} \large \textbf{平衡性}\) 树旋转是在二叉树中的一种子树调整操作, 每一次旋转并\(\color{#40c0bb}{不影响}\)对该二叉树进行\(\color{#40c0bb}{中序遍历}\)的结果。 对于结点 \(A\) 的右旋操作是指:将 \(A\) 的左孩子 \(B\) 向右上旋转,代替 \(A\) 成为根节点,将 \(A\) 结点向右下旋转成为 \(B\) 的右子树的根结点,\(B\) 的原来的右子树变为 \(A\) 的左子树。 完全同理$\LARGE {一些无聊的定义}$
二叉搜索树(BST树)
定义
复杂度
性质
操作
平衡树
定义
通常指每个结点的左右子树的高度之差的绝对值(平衡因子)最多为 \(1\)。平衡的调整过程——树旋转
定义
树旋转通常应用于需要调整树的局部平衡性的场合。树旋转包括两个不同的方式,分别是\(\color{#40c0bb}{左旋(Left Rotate 或者 zag)}\)和 \(\color{#40c0bb}{右旋(Right Rotate 或者 zig)}\)。 两种旋转呈镜像,而且互为逆操作。具体操作
右旋
左旋
至此,正片结束
背景
不难发现\(BST树\)的一种极端情况:\(\color{#40c0bb}{退化情况}\)
这种毒瘤数据让时间复杂度从\(O(log(n))\)退化到了恐怖的\(O(n)\)
于是就有各种各样的科学家们,开始思考人生,丧心病狂地创造出了各种优化BST的方法...
Splay
原理
啥是\(Splay\)?
她实际上就是一种可以旋转的平衡树。
她可以通过旋转保持\(\color{#40c0bb}{平衡性}\)从而解决退化情况。
(方框表示子树,圆框表示节点)
现在,我们要将 \(x\) 节点往上爬一层到他的父节点 \(y\) ,为了保证不改变中序遍历顺序,我们可以让 \(y\) 成为 \(x\) 的右儿子。
但是原来的 \(x\) 节点是有右儿子 \(B\) 的,显然我们要把 \(B\) 换一个位置才能达到目的。
我们知道: \(x\) 节点的右子树必然是大于 \(x\) 节点的; \(y\) 节点必然是大于 \(x\) 节点的右子树和 \(x\) 节点本身的(因为 \(x\) 节点及其右子树都是原来 \(y\) 的左子树,肯定比 \(y\) 小(根据二叉搜索树性质))
因此我们可以把 \(x\) 节点原来的右子树放在 \(y\) 的左儿子的位置上,达成目的。
实际上,这也就是\(\color{#40c0bb}\textbf{右旋}\)的原理。
对于通解:
若节点 \(x\) 为 \(y\) 节点的位置 \(z\)(\(z=0\) 为左节点,\(z=1\) 为右节点 )
-
将 \(y\) 节点放到 \(x\) 节点的 \(z \oplus 1\) 的位置.(也就是, \(x\) 节点为 \(y\) 节点的右子树,那么 \(y\) 节点就放到左子树, \(x\) 节点为 \(y\) 节点左子树,那么 \(y\) 节点就放到右子树位置)
-
如果说 \(x\) 节点的 \(z \oplus 1\) 位置上,已经有节点,或者一棵子树,那么我们就将原来 \(x\) 节点 \(z \oplus 1\) 位置上的子树,放到 \(y\) 节点的位置 \(z\) 上面.
操作
才不是因为我懒得写注释所以直接把代码粘过来了...
基本操作
- \(maintain(x)\):在改变节点位置后,将节点 \(x\) 的 \(\text{size}\) 更新。
- \(get(x)\):判断节点 \(x\) 是父亲节点的左儿子还是右儿子。
- \(clear(x)\):清空节点 \(x\)。
void maintain(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
bool get(int x){
return x==ch[fa[x]][1];
}
void clear(int x){
ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
}
旋转操作
void rotate(int x){
int y=fa[x],z=fa[y],chk=get(x);
ch[y][chk]=ch[x][chk^1];
if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y;
fa[y]=x;
fa[x]=z;
if(z) ch[z][y==ch[z][1]]=x;
maintain(y);
maintain(x);
}
Splay操作
单点操作
void splay(int x) {
for (int f = fa[x]; f = fa[x], f; rotate(x))
if (fa[f]) rotate(get(x) == get(f) ? f : x);
rt = x;
}
区间操作
对应 \(a_{R + 1}\) 的节点的左子树中序遍历为序列 \(a[L, R]\),故其为区间 \([L, R]\) 代表的子树。
void splay(int x,int goal=0){
if(goal==0) rt=x;
while(fa[x]!=goal){
int f=fa[x];
if(fa[fa[x]]!=goal){
rotate(get(x)==get(f)?f:x);
}
rotate(x);
}
}
插入操作
void ins(int k){//insert
if(!rt){
val[++tot]=k;
cnt[tot]++;
rt=tot;
maintain(rt);
return;
}
int cur=rt,f=0;
while(1){
if(val[cur]==k){
cnt[cur]++;
maintain(cur);
maintain(f);
splay(cur);
break;
}
f=cur;
cur=ch[cur][val[cur]<k];
if(!cur){
val[++tot]=k;
cnt[tot]++;
fa[tot]=f;
ch[f][val[f]<k]=tot;
maintain(tot);
maintain(f);
splay(tot);
break;
}
}
}
查询 \(x\) 的排名
int rk(int k){//the rank of "k"
int res=0,cur=rt;
while(1){
if(k<val[cur]){
cur=ch[cur][0];
}else{
res+=sz[ch[cur][0]];
if(!cur) return res+1;
if(k==val[cur]){
splay(cur);
return res+1;
}
res+=cnt[cur];
cur=ch[cur][1];
}
}
}
查询排名 \(x\) 的数
int kth(int k){//the number whose rank is "k"
int cur=rt;
while(1){
if(ch[cur][0] && k<=sz[ch[cur][0]]){
cur=ch[cur][0];
}else{
k-=cnt[cur]+sz[ch[cur][0]];
if(k<=0){
splay(cur);
return val[cur];
}
cur=ch[cur][1];
}
}
}
查询前驱&后继
前驱
int pre(){//precursor
int cur=ch[rt][0];
if(!cur) return cur;
while(ch[cur][1]) cur=ch[cur][1];
splay(cur);
return cur;
}
后继
其实就是查前驱的反面
int nxt(){//next or successor
int cur=ch[rt][1];
if(!cur) return cur;
while(ch[cur][0]) cur=ch[cur][0];
splay(cur);
return cur;
}
查前驱后继有好多种写法,如果想偷懒只写一遍就可以酱紫
int prenxt(int x,int k){//0 pre 1 nxt
find(x);
int cur=rt;
if(val[cur]<x && !k) return cur;
if(val[cur]>x && k) return cur;
cur=ch[cur][k];
while(ch[cur][!k]){
cur=ch[cur][!k];
}
return cur;
}
删除操作
void del(int k){//delete
rk(k);
if(cnt[rt]>1){
cnt[rt]--;
maintain(rt);
return;
}
if(!ch[rt][0] && !ch[rt][1]){
clear(rt);
rt=0;
return;
}
if(!ch[rt][0]){
int cur=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cur);
return;
}
if(!ch[rt][1]){
int cur=rt;
rt=ch[rt][0];
fa[rt]=0;
clear(cur);
return;
}
int cur=rt,x=pre();
fa[ch[cur][1]]=x;
ch[x][1]=ch[cur][1];
clear(cur);
maintain(rt);
}
Code
Elaina's Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rd read()
#define inf 0x3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mst(a,b) memset((a),(b),sizeof((a)))
#define Elaina 0
inline int read(){
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x*f;
}
const int N=1e7+100;
struct Slpay{
int rt;//根
int tot;//节点编号
int fa[N];//父节点
int ch[N][2];//子节点 左0右1
int val[N];//权值
int cnt[N];//节点大小
int sz[N];//子树大小
void maintain(int x){//更新编号为x的结点的子树大小
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
bool get(int x){//判断节点x是父亲节点的左儿子还是右儿子
return x==ch[fa[x]][1];
}
void clear(int x){//清空x节点
ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
}
void rotate(int x){
int y=fa[x],z=fa[y],chk=get(x);
ch[y][chk]=ch[x][chk^1];
if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y;
fa[y]=x;
fa[x]=z;
if(z) ch[z][y==ch[z][1]]=x;
maintain(y);
maintain(x);
}
void splay(int x,int goal=0){
if(goal==0) rt=x;
while(fa[x]!=goal){
int f=fa[x];
if(fa[fa[x]]!=goal){
rotate(get(x)==get(f)?f:x);
}
rotate(x);
}
}
void ins(int k){//insert
if(!rt){
val[++tot]=k;
cnt[tot]++;
rt=tot;
maintain(rt);
return;
}
int cur=rt,f=0;
while(1){
if(val[cur]==k){
cnt[cur]++;
maintain(cur);
maintain(f);
splay(cur);
break;
}
f=cur;
cur=ch[cur][val[cur]<k];
if(!cur){
val[++tot]=k;
cnt[tot]++;
fa[tot]=f;
ch[f][val[f]<k]=tot;
maintain(tot);
maintain(f);
splay(tot);
break;
}
}
}
int rk(int k){//the rank of "k"
int res=0,cur=rt;
while(1){
if(k<val[cur]){
cur=ch[cur][0];
}else{
res+=sz[ch[cur][0]];
if(!cur) return res+1;
if(k==val[cur]){
splay(cur);
return res+1;
}
res+=cnt[cur];
cur=ch[cur][1];
}
}
}
int kth(int k){//the number whose rank is "k"
int cur=rt;
while(1){
if(ch[cur][0] && k<=sz[ch[cur][0]]){
cur=ch[cur][0];
}else{
k-=cnt[cur]+sz[ch[cur][0]];
if(k<=0){
splay(cur);
return val[cur];
}
cur=ch[cur][1];
}
}
}
int pre(){//precursor
int cur=ch[rt][0];
if(!cur) return cur;
while(ch[cur][1]) cur=ch[cur][1];
splay(cur);
return cur;
}
int nxt(){//next or successor
int cur=ch[rt][1];
if(!cur) return cur;
while(ch[cur][0]) cur=ch[cur][0];
splay(cur);
return cur;
}
void del(int k){//delete
rk(k);
if(cnt[rt]>1){
cnt[rt]--;
maintain(rt);
return;
}
if(!ch[rt][0] && !ch[rt][1]){
clear(rt);
rt=0;
return;
}
if(!ch[rt][0]){
int cur=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cur);
return;
}
if(!ch[rt][1]){
int cur=rt;
rt=ch[rt][0];
fa[rt]=0;
clear(cur);
return;
}
int cur=rt,x=pre();
fa[ch[cur][1]]=x;
ch[x][1]=ch[cur][1];
clear(cur);
maintain(rt);
}
void find(int x){
int cur=rt;
if(!cur) return;
while(ch[cur][x>val[cur]]&&x!=val[cur]){
cur=ch[cur][x>val[cur]];
}
splay(cur,0);
}
int get_pre(int x){
find(x);
int cur=rt;
if(val[cur]<x) return cur;
cur=ch[cur][0];
while(ch[cur][1]){
cur=ch[cur][1];
}
return cur;
}
int get_nxt(int x){
find(x);
int cur=rt;
if(val[cur]>x) return cur;
cur=ch[cur][1];
while(ch[cur][0]){
cur=ch[cur][0];
}
return cur;
}
int prenxt(int x,int k){//0 pre 1 nxt
find(x);
int cur=rt;
if(val[cur]<x && !k) return cur;
if(val[cur]>x && k) return cur;
cur=ch[cur][k];
while(ch[cur][!k]){
cur=ch[cur][!k];
}
return cur;
}
}tr;
signed main(){
int m=rd;
while(m--){
int opt=rd,x=rd;
if(opt==1){
tr.ins(x);
}else if(opt==2){
tr.del(x);
}else if(opt==3){
printf("%lld\n",tr.rk(x));
}else if(opt==4){
printf("%lld\n",tr.kth(x));
}else if(opt==5){
tr.ins(x),printf("%lld\n",tr.val[tr.pre()]),tr.del(x);
}else{
tr.ins(x),printf("%lld\n",tr.val[tr.nxt()]),tr.del(x);
}
}
return Elaina;
}