SBT | Dr.Lib

。。也没什么好说的了，《Size Balanced Tree》（CQF WC 2006）说的很清楚了……

今晚（昨晚？手敲的代码……不知道如何……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define L(x) T[(x)].ls
#define Ln(x) T[T[(x)].ls]
#define R(x) T[(x)].rs
#define Rn(x) T[T[(x)].ls]
#define W(x) T[(x)].w
#define S(x) T[(x)].size
using namespace std;

const int MAXN=100000;
const int INF=2147483647;
int root=0;

struct Node{
	int ls,rs,size,w;
	Node():ls(0),rs(0),size(0),w(0){}
};
Node T[MAXN];
int sz,n;

void RR(int &s){
	int x = s;
	int k=L(s);
	L(s)=R(k);
	R(k)=s;
	S(k)=S(s);
	S(s)=S(L(s))+S(R(s))+1;
	s = k;
}
void LR(int &s){
	int x = s;
	int k=R(s);
	R(s)=L(k);
	L(k)=s;
	S(k)=S(s);
	S(s)=S(L(s))+S(R(s))+1;
	s = k;
}
void Maintain(int &s,bool op){
	if (s == 0)return;
	if(!op){
		if( S(R(s)) < S(L(L(s))) )RR(s);
		else if( S(R(s)) < S(R(L(s))) ){
			LR(L(s));RR(s);
		}
		else  return;
	}else{
		if( S(L(s)) < S(R(R(s))) )LR(s);
		else if( S(L(s)) < S(L(R(s))) ){
			RR(R(s));LR(s);
		}
		else  return;
	}
	Maintain(L(s),false);
	Maintain(R(s),true);
	Maintain(s,false);
	Maintain(s,true);
}
void Insert(int &s,int val){
	if(s==0){
		s=++sz;S(s)++;W(s)=val;return;
	}
	S(s)++;
	if(W(s)>val)Insert(L(s),val);
	else Insert(R(s),val);
	Maintain(s,(val>=W(s)));
}
int Delete(int &s,int v){
	S(s)--;
	if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){
		int ans=W(s);
		if(!(L(s)*R(s))){
			s=L(s)+R(s);
		}else{
			W(s)=Delete(L(s),W(s)+1);
		}
		return ans;
	}else{
		if(W(s)>v) return Delete(L(s),v); 
		else       return Delete(R(s),v);
	}
}
int Search(int &s,int v){
	if(!s)return INF;
	if(v==W(s))return s;
	else if(W(s)>v) return Search(L(s),v);
	else            return Search(R(s),v);
}
int Select(int &s,int k){
	if(k>S(root)) return INF;
	int Lt=S(L(s));
	if(k==Lt) return W(s);
	else if(Lt>k) return Select(L(s),k);
	else          return Select(R(s),k-Lt-1);
}
int Rank(int &s,int x){
	if(!s)return INF;
	int Lt=S(L(s));
	if(x==W(s))return Lt;
	else if(W(s)>x)return Rank(L(s),x);
	else           return Rank(R(s),x)+Lt+1;
}
int main(){
	int c;
	int x;
	while(cin>>c>>x){
		switch(c){
			case 0:Insert(root,x);break;
			case 1:Delete(root,x);break;
			case 2:cout<<Search(root,x)<<endl;break;
			case 3:cout<<Select(root,x)<<endl;break;
			case 4:cout<<Rank(root,x)<<endl;break;
			default:cout<<endl;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#define L(x) T[(x)].ls

#define Ln(x) T[T[(x)].ls]

#define R(x) T[(x)].rs

#define Rn(x) T[T[(x)].ls]

#define W(x) T[(x)].w

#define S(x) T[(x)].size

using namespace std;

const int MAXN=100000;

const int INF=2147483647;

int root=0;

struct Node{

int ls,rs,size,w;

Node():ls(0),rs(0),size(0),w(0){}

};

Node T[MAXN];

int sz,n;

void RR(int &s){

int x = s;

int k=L(s);

L(s)=R(k);

R(k)=s;

S(k)=S(s);

S(s)=S(L(s))+S(R(s))+1;

s = k;

}

void LR(int &s){

int x = s;

int k=R(s);

R(s)=L(k);

L(k)=s;

S(k)=S(s);

S(s)=S(L(s))+S(R(s))+1;

s = k;

}

void Maintain(int &s,bool op){

if (s == 0)return;

if(!op){

if( S(R(s)) < S(L(L(s))) )RR(s);

else if( S(R(s)) < S(R(L(s))) ){

LR(L(s));RR(s);

}

else return;

}else{

if( S(L(s)) < S(R(R(s))) )LR(s);

else if( S(L(s)) < S(L(R(s))) ){

RR(R(s));LR(s);

}

else return;

}

Maintain(L(s),false);

Maintain(R(s),true);

Maintain(s,false);

Maintain(s,true);

}

void Insert(int &s,int val){

if(s==0){

s=++sz;S(s)++;W(s)=val;return;

}

S(s)++;

if(W(s)>val)Insert(L(s),val);

else Insert(R(s),val);

Maintain(s,(val>=W(s)));

}

int Delete(int &s,int v){

S(s)--;

if( (v==W(s)) || (v<W(s)&&L(s)==0)||(v>W(s)&&R(s)==0) ){

int ans=W(s);

if(!(L(s)*R(s))){

s=L(s)+R(s);

}else{

W(s)=Delete(L(s),W(s)+1);

}

return ans;

}else{

if(W(s)>v) return Delete(L(s),v);

else return Delete(R(s),v);

}

int Search(int &s,int v){

if(!s)return INF;

if(v==W(s))return s;

else if(W(s)>v) return Search(L(s),v);

else return Search(R(s),v);

}

int Select(int &s,int k){

if(k>S(root)) return INF;

int Lt=S(L(s));

if(k==Lt) return W(s);

else if(Lt>k) return Select(L(s),k);

else return Select(R(s),k-Lt-1);

}

int Rank(int &s,int x){

if(!s)return INF;

int Lt=S(L(s));

if(x==W(s))return Lt;

else if(W(s)>x)return Rank(L(s),x);

else return Rank(R(s),x)+Lt+1;

}

int main(){

int c;

int x;

while(cin>>c>>x){

switch(c){

case 0:Insert(root,x);break;

case 1:Delete(root,x);break;

case 2:cout<<Search(root,x)<<endl;break;

case 3:cout<<Select(root,x)<<endl;break;

case 4:cout<<Rank(root,x)<<endl;break;

default:cout<<endl;

}

return 0;

}

。。按惯例笔记贴都是摘抄、转载的……TAT看了半天貌似还是不会写的样子……滚回去复习主席树了

Via NOCOW http://www.nocow.cn/index.php/Size_Balanced_Tree

Size Balanced Tree(SBT)是一种平衡二叉查找树。它的论文由中国广东中山纪念中学的陈启峰于2006年底完成，并在Winter Camp 2007中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的OIer们戏称为“傻X树”、“Super BT”等。但它的性能并不SB，编写起来也并不BT。恰恰相反，SBT易于实现，且据陈启峰论文中所言，“这是目前为止速度最快的高级二叉搜索树”。它能在O(logn)的时间内完成所有BST的相关操作。而且由于SBT赖以保持平衡的是Size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank。

性质

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

性质(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]
性质(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]

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

如图（圈代表结点，三角代表SBT，下同）：

s[R] ≥ s[A]，s[B]
s[L] ≥ s[C]，s[D]

旋转

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

k ← right[t]
right[t] ← left[k]
left[k] ← t
s[k] ← s[t]
s[t] ← s[left[t]] + s[right[t]] + 1
t ← k

k ← right[t]

right[t] ← left[k]

left[k] ← t

s[k] ← s[t]

s[t] ← s[left[t]] + s[right[t]] + 1

t ← k

k ← left[t]
left[t] ← right[k]
right[k] ← t
s[k] ← s[t]
s[t] ← s[left[t]] + s[right[t]] + 1
t ← k

k ← left[t]

left[t] ← right[k]

right[k] ← t

s[k] ← s[t]

s[t] ← s[left[t]] + s[right[t]] + 1

t ← k

保持性质(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，执行完Insert(left[t],v)后发生S[A]>S[R]，我们可以执行以下的指令来修复SBT：
1. 首先执行Right-Ratote(t)，这个操作让图3变成图4；
2. 在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
3. 结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
第二种情况：s[right[left[t]]>s[right[t]]在执行完Insert(left[t],v)后发生s[B]>s[R]，如图5，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复：
1. 在执行完Left-Ratote(L)后，图5就会变成下面图6那样了。
2. 然后执行Right-Ratote(T)，最后的结果就会由图6转变成为下面的图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对称。

通过前面的分析，很容易写出一个普通的Maintain。

 If s[left[left[t]]>s[right[t]] then    //case1
      Right-Rotate(t)
      Maintain(right[t])
      Maintain(t)
      Exit
 If s[left[right[t]]>s[right[t]] then   //case2
      Left-Rotate(left[t])
      Right-Rotate(t)
      Maintain(left[t])
      Maintain(right[t])
      Maintain(t)
      Exit
 If s[right[right[t]]>s[left[t]] then   //case1'
      Left-Rotate(t)
      Maintain(left[t])
      Maintain(t)
      Exit
 If s[right[left[t]]>s[left[t]] then    //case2'
      Right-Rotate(right[t])
      Left-Rotate(t)
      Maintain(left[t])
      Maintain(right[t])
      Maintain(t)

If s[left[left[t]]>s[right[t]] then //case1

Right-Rotate(t)

Maintain(right[t])

Maintain(t)

Exit

If s[left[right[t]]>s[right[t]] then //case2

Left-Rotate(left[t])

Right-Rotate(t)

Maintain(left[t])

Maintain(right[t])

Maintain(t)

Exit

If s[right[right[t]]>s[left[t]] then //case1'

Left-Rotate(t)

Maintain(left[t])

Maintain(t)

Exit

If s[right[left[t]]>s[left[t]] then //case2'

Right-Rotate(right[t])

Left-Rotate(t)

Maintain(left[t])

Maintain(right[t])

Maintain(t)

前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量：flag，来避免毫无意义的判断。如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。

 If flag=false then
       If s[left[left[t]]>s[right[t]] then      //case1
           Right-Rotate(t)
       Else
           If s[left[right[t]]>s[right[t]] then   //case2
                Left-Rotate(left[t])
                Right-Rotate(t)
      Else                                   //needn’t repair
           Exit
 Else
       If s[right[right[t]]>s[left[t]] then      //case1'
           Left-Rotate(t)
      Else
           If s[right[left[t]]>s[left[t]] then     //case2'
                Right-Rotate(right[t])
                Left-Rotate(t)
      Else                                    //needn’t repair
           Exit
 Maintain(left[t],false)                     //repair the left subtree
 Maintain(right[t],true)                     //repair the right subtree
 Maintain(t,false)                           //repair the whole tree
 Maintain(t,true)                            //repair the whole tree

If flag=false then

If s[left[left[t]]>s[right[t]] then //case1

Right-Rotate(t)

Else

If s[left[right[t]]>s[right[t]] then //case2

Left-Rotate(left[t])

Right-Rotate(t)

Else //needn’t repair

Exit

Else

If s[right[right[t]]>s[left[t]] then //case1'

Left-Rotate(t)

Else

If s[right[left[t]]>s[left[t]] then //case2'

Right-Rotate(right[t])

Left-Rotate(t)

Else //needn’t repair

Exit

Maintain(left[t],false) //repair the left subtree

Maintain(right[t],true) //repair the right subtree

Maintain(t,false) //repair the whole tree

Maintain(t,true) //repair the whole tree

为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？

……且听下回分解

Tag Archives: SBT

[Dr.Lib]Note:Data Structures – Size Balanced Tree – II

[Dr.Lib]Note:Data Structures – Size Balanced Tree – I

性质

旋转

保持性质(Maintain)

朋友们

TAG CLOUD