數據結構
Size Balanced Tree（簡稱SBT）是一自平衡二叉查找樹，是在計算機科學中用到的一種數據結構。它是由中國廣東中山紀念中學的陳啟峰發明的。陳啟峰於2006年底完成論文《Size Balanced Tree》，並在2007年的全國青少年信息學奧林匹克競賽冬令營中發表。由於SBT的拼寫很容易找到中文諧音，它常被中國的信息學競賽選手和ACM/ICPC選手們戲稱為“傻B樹”、“Super BT”等。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易於實現。據陳啟峰在論文中稱，SBT是“目前為止速度最快的高級二叉搜尋樹”。SBT能在O(log n)的時間內完成所有二叉搜尋樹（BST）的相關操作，而與普通二叉搜尋樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由於SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很方便地實現動態順序統計中的select和rank操作。
用C++實現的SBT代碼，包括插入、刪除、找最大和最小值：
void goleft(int &t) //左旋
{
int y=r[t];
r[t]=l[y];
l[y]=t;
s[t]=s[l[t]]+s[r[t]]+1;
s[y]=s[l[y]]+s[r[y]]+1;
t=y;
}
void goright(int &t) //右旋
{
int y=l[t];
l[t]=r[y];
r[y]=t;
s[t]=s[l[t]]+s[r[t]]+1;
s[y]=s[l[y]]+s[r[y]]+1;
t=y;
}
void maintain(int &t,bool flag) //保持性質
{
if (!t) return;
if (flag)
{
if (s[r[t]]
else
if (s[r[t]]
{
goleft(l[t]);
goright(t);
}
else return;
}
else
{
if (s[l[t]]
else
if (s[l[t]]
{
goright(r[t]);
goleft(t);
}
else return;
}
maintain(l[t],1);
maintain(r[t],0);
maintain(t,1);
maintain(t,0);
}
void insert(int &t,int x) //插入
{
if (!t)
{
t=++k;
a[t]=x; s[t]=1;
}
else
{
s[t]++;
if (x
