learn from awesome NOCOW ;D
Size Balanced Tree(SBT)是一种通过大小(Size)域来保持平衡的二叉搜索树,它也因此得名。它总是满足:
对于SBT的每一个结点 t:
- 性质(a) s[right[t]] ≥ s[left[left[t]]],s[right[left[t]]]
- 性质(b) s[left[t]] ≥ s[left[right[t]]],s[right[right[t]]]
即每棵子树的大小不小于其兄弟的子树大小。
如图(圈代表结点,三角代表SBT,下同):
- s[R] ≥ s[A],s[B]
- s[L] ≥ s[C],s[D]
旋转
SBT的旋转(Rotations)与其他许多高级BST相同。它是下面提到的Maintain操作的基础。
保持性质(Maintain)
当我们插入或删除一个结点后,SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时,我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程;Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的,所以我们仅仅详细的讨论性质a。
-
第一种情况:s[left[left[t]]>s[right[t]]
图3(同图1) -
第二种情况:s[right[left[t]]>s[right[t]]
图5 -
第三种情况:s[right[right[t]]>s[left[t]]
与情况1对称。 -
第四种情况:s[left[right[t]]>s[left[t]]
与情况2对称。
通常我们可以保证性质a和性质b的满足,因此我们只需要检查情况1和情况2或者情况3和情况4,这样可以提高速度。所以在那种情况下,我们需要增加一个布尔(boolean)型变量:flag,来避免毫无意义的判断。如果flag是false,那么检查情况1和情况2;否则检查情况3和情况4。
为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢?
可以在陈启峰论文第六部分的分析中找到答案。
其他可以从论文中获得的信息:每次SBT后树的总深度递减的证明;Maintain的平摊运行时间是O(1)的证明(也就是说你不必担心Maintain这个递归过程是否会永不停止)等。
基本操作
查找
SBT的查找操作与普通BST完全相同。下面的过程将返回指向目标节点的指针。
Search(x,k)
1 if x=NULL or k=key[x] //找到了目标节点或目标节点不存在则返回x
2 then return x
3 if k<key[x]
4 then return Search(left[x],k)
5 else return Search(right[x],k)
取大/取小
由于SBT本身已经维护了size,因此这两项可用Select操作完成。
后继
SBT的后继操作与普通BST完全相同。
前趋
SBT的前趋操作与普通BST完全相同。它与上面的后继操作对称。
插入
SBT的插入操作很简单。它仅仅比普通BST的多出了一个Maintain操作和对s的简单维护。下面这个过程将一个节点v插入SBT中。
Insert (t,v)
1 If t=0 then
2 t ← v
3 Else
4 s[t] ← s[t]+1
5 If v<key[t] then
6 Insert(left[t],v)
7 Else
8 Insert(right[t],v)
9 Maintain(t,v≥key[t])
删除
与普通维护size域的BST删除相同。
关于无需Maintain的说明by sqybi:
在删除之前,可以保证整棵树是一棵SBT。当删除之后,虽然不能保证这棵树还是SBT,但是这时整棵树的最大深度并没有改变,所以时间复杂度也不会增加。这时,Maintain就显得是多余的了。
动态顺序统计操作
由于SBT本来就是靠着size域来维持平衡的,当我们进行动态顺序统计操作时,我们就无需去“额外”维护一个size域来进行数据结构的扩张。这样,以下操作就与其他高级BST扩张后的动态顺序统计操作完全一样了。
检索具有给定排序的元素
下面这个过程将返回一个指向以x为根的子树中包含第i小关键字的节点的指针。
Select(x,i)
1 r ← size[left[x]] + 1
2 if(i=r)
3 then return x
4 else if i<r
5 then return Select(left[x],i)
6 else return Select(right[x],i-r)
求元素的秩
SBT的rank操作与普通BST完全相同。
性能分析
SBT的高度是O(logn),Maintain是O(1),所有主要操作都是O(logn)。
以下是【NOI2004 郁闷的出纳员】我的程序,自认为写得还不错~就当做模板啦
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int M=100000+10;
struct SBT{
int l,r,s,key;
void init(){
l=r=key=0;
s=1;
}
}t[M];
int rt,cnt,tot,n,minn,delta;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
return x*f;
}
void update(int p)
{
t[p].s=t[t[p].l].s+t[t[p].r].s+1;
}
void Zig(int &p)
{
int k=t[p].r;
t[p].r=t[k].l;
t[k].l=p;
t[k].s=t[p].s;
update(p);
p=k;
}
void Zag(int &p)
{
int k=t[p].l;
t[p].l=t[k].r;
t[k].r=p;
t[k].s=t[p].s;
update(p);
p=k;
}
void maintain(int &p,bool flag)
{
if(flag)
{
if(t[t[t[p].r].r].s>t[t[p].l].s)
Zig(p);
else if(t[t[t[p].r].l].s>t[t[p].l].s)
{
Zag(t[p].r);
Zig(p);
}
else
return;
}
else
{
if(t[t[t[p].l].l].s>t[t[p].r].s)
Zag(p);
else if(t[t[t[p].l].r].s>t[t[p].r].s)
{
Zig(t[p].l);
Zag(p);
}
else
return;
}
maintain(t[p].l,false);
maintain(t[p].r,true);
maintain(p,false);
maintain(p,true);
}
void Insert(int &p,int x)
{
if(!p)
{
p=(++tot);
t[p].init();
t[p].key=x;
}
else
{
t[p].s++;
if(x<t[p].key)
Insert(t[p].l,x);
else
Insert(t[p].r,x);
maintain(p,x>=t[p].key);
}
}
void Del(int &p,int x)
{
if(!p) return;
if(x>t[p].key)
{
p=t[p].r;
Del(p,x);
}
else
{
Del(t[p].l,x);
update(p);
}
}
int maxKth(int &p,int k)
{
int tmp=t[t[p].r].s+1;
if(tmp==k)
return t[p].key;
else if(tmp<k)
return maxKth(t[p].l,k-tmp);
return maxKth(t[p].r,k);
}
int main()
{
tot=0;delta=0;rt=0;
char ch[5];
int x;
n=read();minn=read();
while(n--)
{
scanf("%s%d",ch,&x);
if(ch[0]=='I')
{
if(x<minn) continue;
Insert(rt,x-delta);
}
else if(ch[0]=='A') delta+=x;
else if(ch[0]=='S')
{
delta-=x;
Del(rt,minn-delta);
}
else if(ch[0]=='F')
{
if(x>t[rt].s) puts("-1");
else printf("%d\n",maxKth(rt,x)+delta);
}
}
printf("%d\n",tot-t[rt].s);
return 0;
}
另外几种基本操作:
inline int getMax(){
int i;
for (i=root;tree[i].right;i=tree[i].right);
return tree[i].key;
}
inline int getMin(){
int i;
for (i=root;tree[i].left;i=tree[i].left);
return tree[i].key;
}
int rank(int &x,int sp){
if (sp<tree[x].key){
return rank(tree[x].left,sp);
}else if (sp>tree[x].key){
return rank(tree[x].right,sp)+tree[tree[x].left].size+1;
}
return tree[tree[x].left].size+1;
}
int select(int &x,int rak){
int rk=tree[tree[x].left].size+1;
if (rak<rk){
return select(tree[x].left,rak);
}else if (rak>rk){
return select(tree[x].right,rak-rk);
}
return tree[x].key;
}