BST学习笔记~

12
5
2015

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]]]

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

图1

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

Category: 伸展树 | Tags: | Read Count: 452

Ryan_<

能追无尽景,始是不凡人_