12
5
2015
0

BST学习笔记~

 

learn from awesome NOCOW ;D

Size Balanced Tree(SBT)是一种通过大小(Size)域来保持平衡的二叉搜索树,它也因此得名。它总是满足:
对于SBT的每一个结点 t:

  1. 性质(a) s[right[t]] ≥ s[left[left[t]]],s[right[left[t]]]
  2. 性质(b) s[left[t]] ≥ s[left[right[t]]],s[right[right[t]]]

即每棵子树的大小不小于其兄弟的子树大小。
 

Sbt1.PNG
图1

如图(圈代表结点,三角代表SBT,下同):

  1. s[R] ≥ s[A],s[B]
  2. s[L] ≥ s[C],s[D]

 

  1.  

旋转

SBT的旋转(Rotations)与其他许多高级BST相同。它是下面提到的Maintain操作的基础。

保持性质(Maintain)

当我们插入或删除一个结点后,SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时,我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程;Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的,所以我们仅仅详细的讨论性质a。

  1. 第一种情况:s[left[left[t]]>s[right[t]]
    Sbt1.PNG
    图3(同图1)
    如图3,执行完Insert(left[t],v)后发生S[A]>S[R],我们可以执行以下的指令来修复SBT:
    1. 首先执行Right-Ratote(t),这个操作让图3变成图4;
      Sbt4.PNG
      图4
    2. 在这之后,有时候这棵树还仍然不是一棵SBT,因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
    3. 结点L的右子树有可能被连续调整,因为有可能由于性质的破坏需要再一次运行Maintain(L)。
       
  2. 第二种情况:s[right[left[t]]>s[right[t]]
    Sbt5.PNG
    图5
    在执行完Insert(left[t],v)后发生s[B]>s[R],如图5,这种调整要比情况1复杂一些。我们可以执行下面的操作来修复:
    1. 在执行完Left-Ratote(L)后,图5就会变成下面图6那样了。
      Sbt6.PNG
      图6
    2. 然后执行Right-Ratote(T),最后的结果就会由图6转变成为下面的图7。
      Sbt7.PNG
      图7
    3. 在第1步和第2步过后,整棵树就变得非常不可预料了。万幸的是,在图7中,子树A、E、F和R仍就是SBT,所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
    4. 在第3步之后,子树都已经是SBT了,但是在结点B上还可能不满足性质a或性质b,因此我们需要再一次调用Maintain(B)。
       
  3. 第三种情况:s[right[right[t]]>s[left[t]]
    与情况1对称。
  4. 第四种情况: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;
}
Category: 伸展树 | Tags: | Read Count: 168

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com