一、二叉搜索树(二叉排序树、二叉查找树) BST
BST基本性质
BST是一棵二叉树
若这棵树的左子树不为空，则左子树上所有节点的值都小于根节点的值
若这棵树的右子树不为空，则右子树上所有节点的值都大于根节点的值
这棵树若存在左、右子树，则左右子树也分别是BST
BST的构建/插入
每个新元素的插入从BST的根节点开始，进行如下操作:
①若当前位置为空，则在当前位置插入此元素，退出函数
②若当前位置的值等于新元素值，则此元素已被插入过，退出函数
③若此元素的值小于当前位置的值，则对当前位置的左子树进行以上操作;若此元素的值大于当前位置的值，则对当前位置的右子树进行以上操作
void Insert(BST *&x,int v)
{
if(!x)//若当前节点为空
{
x=new BST;//新建一个节点
x->Left=x->Right=NULL,x->num=v;//将这个新节点设定为插入元素
return;
}
if(v==x->num) return;//若已插入过，则退出函数
if(v<x->num) Insert(x->Left,v);//若插入元素小于当前节点元素，则继续对当前节点的左子树进行操作
else Insert(x->Right,v);//反之，继续对当前节点的右子树进行操作
}BST的查询(查询一个值是否在BST上)
BST的查询过程与插入类似，从BST根节点开始，进行如下操作:
若当前位置为空，则该值不在BST上，返回false
若当前位置的数值等于该值，则数值被找到，返回true
若该值小于当前位置的值，则继续查询当前位置的左子树;若该值大于当前位置的值，则继续查询当前位置的右子树
bool Query(BST *x,int v)
{
if(!x) return false;//若当前节点为空，则返回0
if(v==x->num) return true;//若查询元素与当前节点相等，则返回1
return v<x->num?Query(x->Left,v):Query(x->Right,v);
}BST的删除
删除BST上的一个数值，首先找到该数值，成功找到该值后，分情况讨论：
①该节点没有左右子树，直接删除该节点
②该节点仅有左子树或仅有右子树，则删除该节点后，将左/右子树移至原先位置
③若该节点有左右子树，则需要找到该节点的直接前驱/后继(即它的子树中最大的小于它的数/最小的大于它的数)，删除该节点后，将直接前驱/后继移至它的原先位置
void DeleteNode(BST *&x)
{
BST *tmp=x;
if(x->Left==NULL&&x->Right==NULL)//叶子节点
x=NULL;
else if(x->Left==NULL)//仅有右子树
x=x->Right;
else if(x->Right==NULL)//仅有左子树
{
x=x->Left;
}
else//左右子树都在
{
BST *LMax = x->Left; //查找最大的小于x节点的节点
while(LMax->Right!=NULL)LMax=LMax->Right;
x->num=LMax->num;
tmp=LMax;
}
free(tmp);
}理论上，查询BST上的节点时间效率为O(logN)，但因为BST结构不确定，实际效率往往大于O(logN)，最坏情况下，BST退化成一条链，时间效率退化为O(N)
为解决这一效率问题，我们需要调整BST的结构，使其变成平衡树(Balance Tree)
平衡树算法有
替罪羊树
Treap(树堆)
Splay
AVL树
红黑树
等
算法竞赛中一般使用较为好写的Treap、Splay(要求不高的话可以直接用STL中的set)，工程一般使用效率更高的红黑树，其他算法一般不常用
二、替罪羊树 ScapegoatTree
替罪羊树，英文名Scapegoat ，是平衡树中最简单的一种。
替罪羊树可以当作一棵非常暴力的二叉搜索树，因为它除了在子树不平衡时会暴力重构以外几乎和BST没有任何区别。
替罪羊树的插入、查询和BST一致，在删除节点时，我们并不会将其暴力删除（虽然替罪羊树在重构时非常暴力，但它的暴力是有选择性的），而是标记这个节点不存在，并在计算它所在子树大小时将实际大小减1
替罪羊树的重构
假设这是一个需要被重构的替罪羊树子树
那么第一步，先暴力将它拍扁
第二步，将最中间的节点提起来，作为新的根
重构完成。
替罪羊树代码略。
三、旋转
旋转是平衡树一种常用的平衡手段。
对于一个节点o，不妨设其左子树为a，其右子节点为o1，o1左子树b，右子树b
用o1节点取代o原有位置，而o作为o1的新左子节点，其左子树为a，右子树为b，o1的右子树仍为c
(蓝书上的图，网上没找到就临时画图画了个，表示子树的三角偷懒省掉了)
可以看出，在这样操作后，平衡树仍然平衡(a所有数值<o<b所有数值<o1<c所有数值)
这就是一个左旋操作，反过来就是右旋，不同平衡树使用旋转的思路基本一致，但写法可能会因为算法不同而有一些区别。
四、树堆Treap
树堆，顾名思义，平衡树(左<根<右)+堆(孩子<父亲)
这样的结构上，每个节点有两个权值，一个实际数字作为平衡树的依据，一个插入时创建的随机数字作为堆的依据
这个算法的思想就是通过随机数来维护平衡树，能基本避免树退化成链的最坏情况但不能确保实际效率有多高，在平衡树算法中属于写法轻松但效率较低。
树堆在插入新数据的过程同时根据随机权值对树进行旋转，按一般平衡树的插入思想向下进行插入，并在插入结束后依次向上比较随机权值，通过旋转调整为大/小顶堆
//本段代码取自HDU的ACM-ICPC模板整理
struct node
{
int val,cnt,sum,p;node *l,*r;
node(){val=cnt=sum=p=0;l=r=NULL;}
void up(){sum=cnt+l->sum+r->sum;}
}*blank=new(node),*root; //val为决定平衡树的权值，p为决定堆的权值
void Init()
{
blank->l=blank->r=blank;
root=blank;
}
void Rotatel(node*&x){node*y=x->r;x->r=y->l;x->up();y->l=x;y->up();x=y;} //左旋
void Rotater(node*&x){node*y=x->l;x->l=y->r;x->up();y->r=x;y->up();x=y;} //右旋
//插入一个p
void Insert(node*&x,int p)
{
if(x==blank)
{
x=new(node);x->val=p;x->l=x->r=blank;x->cnt=x->sum=1;x->p=rand();
return;
}
x->sum++;
if(p==x->val){x->cnt++;return;}
if(p<x->val)
{
Insert(x->l,p);
if(x->l->p>x->p)Rotater(x);
}
else
{
Insert(x->r,p);
if(x->r->p>x->p)Rotatel(x);
}
}
//删除一个p
void Delete(node*&x,int p)
{
x->sum--;
if(p==x->val){x->cnt--;return;}
if(p<x->val)Delete(x->l,p);else Delete(x->r,p);
}
//查询大于p的数字的个数
int Ask(node*&x,int p)
{
if(x==blank)return 0;
if(p==x->val)return x->r->sum;
if(p<x->val)return x->cnt+x->r->sum+Ask(x->l,p);
return Ask(x->r,p);
}
//查询在[c,d]范围内的数字的个数
int Ask(node*&x,int a,int b,int c,int d)
{
if(x==blank)return 0;
if(c<=a&&b<=d)return x->sum;
int t=c<=x->val&&x->val<=d-x->cnt:0;
if(c<x->val)t+=Ask(x->l,a,x->val-1,c,d);
if(d>x->val)t+=Ask(x->r,x->val+1,b,c,d);
}五、伸展树Splay
Splay算法基于这样一个思想:刚刚被访问的内容，接下来这个内容以及这个内容在平衡树上附近的内容被访问的概率较高，换句话说，这个算法的策略就是被查询频率较高的结点应尽量靠近根
因此，Splay中，在每次插入/查询/修改/计算等操作后，将操作的节点向上旋转至根
Splay在左旋、右旋的基础上，引入了Zig、Zig-Zig、Zig-Zag操作
(以下图片资源取自hihoCoder，代码采用数组模拟二叉树)
Zig：
根据x所在位置（是其根节点的左/右子节点），对x进行一次右旋/左旋，使其位置在树中提升一层
Zig-Zig：
若p不是根节点，还有父亲节点g，x为p的子节点，且p和x同为左子节点或右子节点，则进行Zig-Zig操作：
当x,p同为左子节点时，依次将p和x右旋；
当x,p同为右子节点时，依次将p和x左旋。
此操作使x在树中位置提升两层
Zig-Zag：
若p不是根节点，还有父亲节点g，x为p的子节点。且p和x不同为左子节点或右子节点，则进行Zig-Zag操作：
当p为左子节点，x为右子节点时，将x节点先左旋再右旋；
当p为右子节点，x为左子节点时，将x节点先右旋再左旋。
此操作使x在树中位置提升两层
在Zig、Zig-Zig、Zig-Zag操作的基础上，Splay定义了“splay”操作:
对于x以及x的祖先y，splay(x,y)，表示对x位置进行调整，使得x是y的孩子节点
splay操作策略:
不妨设x的父节点为p
当p的父节点为y时，对x进行一次Zig操作，完成操作
否则，根据x和p的位置，进行Zig-Zig/Zig-Zag操作，直到x或p的父节点为y
void splay(int x,int y)
{
while(node[x].father!=y)
{
int p=node[x].father;
if(node[p].father==y)
{
if(node[p].left==x)
rotater(x);
else
rotatel(x);
}
else
{
int g=node[p].father;
if(node[g].left==p)
{
if(node[p].left==x) //p,x同为左子节点,Zig-Zig操作
{
rotater(p);
rotater(x);
}
else //p为左子节点,x为右子节点,Zig-Zag操作
{
rotatel(x);
rotater(x);
}
}
else
{
if(node[p].right==x) //p,x同为右子节点,Zig-Zig操作
{
rotatel(p);
rotatel(x);
}
else //p为右子节点,x为左子节点,Zig-Zag操作
{
rotater(x);
rotatel(x);
}
}
}
}
}在拥有了splay操作和，Splay树的插入和查询都和一般平衡树一致，但是需要在操作结束后进行一次splay(key,NULL)将刚访问的节点移至根节点处
根据splay操作的性质，Splay树能方便地进行一些Treap不方便做到的功能：
查询key的前后数字:
查询指定数key在树中数值大小紧邻的前一个数和后一个数
首先将key旋转至根节点，则key的左子树的最右子孙一定是key的前一个数;key的右子树的最左子孙一定是key的后一个树
删除key:
从平衡树中删去key节点
首先找到key的前一个数prev和后一个数next
然后将prev旋转至根，再将next旋转至prev的孩子节点
此时，prev的右子节点是next，而next的左子树表示"大于prev且小于next的元素"，有且仅有一个key，也就是说，此时next的左节点即是key且此时key为叶子节点，可以直接删去
删除[a,b]区间所有数:
从平衡树中删去[a,b]所有树，思路为把这些数字旋转到同一棵子树上，再全部删去
先找到a的前一个数prev，再找到b的后一个数next
将prev旋转至根，再将next旋转至prev的孩子节点
则此时next的左子树为全部[a,b]区间内元素
//本段代码取自HDU的ACM-ICPC模板整理
/*
1.ADD x y D：区间 [x, y] 加 D。
2.REVERSE x y：将区间 [x, y] 翻转。
3.REVOLVE x y T：将区间 [x, y] 向右旋转 T 个单位。
4.INSERT x P：在第 x 个数后插入 P。
5.DELETE x：删去第 x 个数。
6.MIN x y：查询区间 [x, y] 内的最小值。
*/
int n,m,a[N],val[N],mn[N],tag[N],size[N],son[N][2],f[N],tot,root;bool rev[N];
void rev1(int x){if(!x)return;swap(son[x][0],son[x][1]);rev[x]^=1;}
void add1(int x,int p){if(!x)return;val[x]+=p;mn[x]+=p;tag[x]+=p;}
void pb(int x)
{
if(rev[x])
{
rev1(son[x][0]);
rev1(son[x][1]);
rev[x]=0;
}
if(tag[x])
{
add1(son[x][0],tag[x]);
add1(son[x][1],tag[x]);
tag[x]=0;
}
}
void up(int x)
{
size[x]=1,mn[x]=val[x];
if(son[x][0])
{
size[x]+=size[son[x][0]];
if(mn[x]>mn[son[x][0]])mn[x]=mn[son[x][0]];
}
if(son[x][1])
{
size[x]+=size[son[x][1]];
if(mn[x]>mn[son[x][1]])mn[x]=mn[son[x][1]];
}
}
void rotate(int x)
{
int y=f[x],w=son[y][1]==x;
son[y][w]=son[x][w^1];
if(son[x][w^1])f[son[x][w^1]]=y;
if(f[y])
{
int z=f[y];
if(son[z][0]==y)son[z][0]=x;
if(son[z][1]==y)son[z][1]=x;
}
f[x]=f[y];son[x][w^1]=y;f[y]=x;up(y);
}
void splay(int x,int w)
{
int s=1,i=x,y;a[1]=x;
while(f[i])a[++s]=i=f[i];
while(s)pb(a[s--]);
while(f[x]!=w)
{
y=f[x];
if(f[y]!=w){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
rotate(x);
}
if(!w)root=x;
up(x);
}
int build(int l,int r,int fa)
{
int x=++tot,mid=(l+r)>>1;
f[x]=fa;val[x]=a[mid];
if(l<mid)son[x][0]=build(l,mid-1,x);
if(r>mid)son[x][1]=build(mid+1,r,x);
up(x);
return x;
}
int kth(int k)
{
int x=root,tmp;
while(1)
{
pb(x);
tmp=size[son[x][0]]+1;
if(k==tmp)return x;
if(k<tmp)x=son[x][0];else k-=tmp,x=son[x][1];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
root=build(0,n+1,0);
scanf("%d",&m);
while(m--)
{
char op[9];int x,y,z;
scanf("%s%d",op,&x);
if(op[0]=='A')
{
scanf("%d%d",&y,&z);
x=kth(x),y=kth(y+2);
splay(x,0),splay(y,x),add1(son[y][0],z);
}
if(op[0]=='R'&&op[3]=='E')
{
scanf("%d",&y);
x=kth(x),y=kth(y+2);
splay(x,0),splay(y,x),rev1(son[y][0]);
}
if(op[0]=='R'&&op[3]=='O')
{
scanf("%d%d",&y,&z),z%=y-x+1;
if(z)
{
int u=x,t;
x=kth(y-z+1),y=kth(y+2);
splay(x,0),splay(y,x),t=son[y][0];
son[y][0]=0,up(y),up(x);
x=kth(u),y=kth(u+1);
splay(x,0),splay(y,x),son[y][0]=t,f[t]=y;
up(y),up(x);
}
}
if(op[0]=='I')
{
scanf("%d",&y);
x=kth(x+1);
splay(x,0);
f[++tot]=x,val[tot]=y;
son[tot][1]=son[x][1],f[son[x][1]]=tot,son[x][1]=tot;
up(tot),up(x);
}
if(op[0]=='D')
{
y=x;
x=kth(x),y=kth(y+2);
splay(x,0),splay(y,x),son[y][0]=0;
up(y),up(x);
}
if(op[0]=='M')
{
scanf("%d",&y);
x=kth(x),y=kth(y+2);
splay(x,0),splay(y,x),printf("%d\n",mn[son[y][0]]);
}
}
}更多推荐
【week2day4笔记】平衡树
发布评论