[## 一、什么是SBT
SBT , 即Size Balanced Tree，是一种平衡二叉排序树，根据其节点中Size域大小进行平衡，由陈启峰于在冬令营提出
二、为什么写SBT：
书写简单：在常用的平衡树（ Spaly , Treap , AVL , Red-Black Tree ……）中，SBT的码量较小，只是在原有 BST 的基础上加入 Maintain 函数以及对Size域的一些调整.
理解简单：SBT 的基本思想相对于别的平衡树（ Splay , AVL ,RBT……）来说更加容易被初学者所接受
效率较高：其核心算法 Maintain 的复杂度平摊为O(1)(不会证)，（证明过程可见论文），且其趋近于一棵完美的二叉排序树。
三、平衡性质
SBT总满足：
1.Size[Right[t]] >= Size[Left[Left[t]]],Size[Right[Left[t]]]
2.Size[Left[t]] >= Size[Left[Right[t]]],Size[Right[Right[t]]]
翻译过来即：
一个节点的左右儿子的子树大小总不小于其兄弟的儿子（侄子）的子树大小
而这种平衡性质便是以 Maintain 来维持
四、基本操作
0、声明：
int n, root, tot;int Right[100100], Left[100100], Size[100100], Val[100100];
1、旋转
实现 Maintain 的基本操作即 左旋 与 右旋
左旋即将操作点（L）变为其先前右儿子(P)的左儿子，先前右儿子(P)变为操作点(L)的父亲，同时保持BST性质。（如图，先前P为L的右儿子，现在L为P的左儿子）
void Left_rotate(int &p)//{int k = Right[p];Right[p] = Left[k];//将p的右儿子变为其原本右儿子的左儿子Left[k] = p;//将p原本的右儿子的左儿子变为pSize[k] = Size[p];//k取代p的Size值Size[p] = Size[Right[p]] + Size[Left[p]] + 1;//计算p的大小值p = k;}
右旋即将操作点(P)变为其先前左儿子(L)的右儿子，先前左儿子(L)变为操作点(P)的父亲,同时保持BST性质。（如图，先前L为P的左儿子，现在P为L的右儿子）
void Right_rotate(int &p)//右旋与左旋相反{int k = Left[p];Left[p] = Right[k];Right[k] = p;Size[k] = Size[p];Size[p] = Size[Right[p]] + Size[Left[p]] + 1;p = k;}
2、Maintain
在什么情况下会使用 Maintain 呢？就是在性质1或2不满足，平衡树不平衡。所以，当一棵 SBT 变化的时候会使用 Maintain。
在所有的基本操作中，改变 BST 的也就两个,Insert 和 Delete。而 Delete 是不改变树的形态的。
虽然它(Delete)会破坏SBT的结构，但因为使用 Insert 操作，它还是一棵高度为O(log2 K)的 SBT 。这里的 K 是所有插入节点的个数，而不是当前节点的个数
而插入一个节点后中，我们需要对插入过程中经过的点进行 Maintain 操作，否则以这些点为根的子树有可能不平衡。
Maintain(p）指的是调整以 p 为根的 SBT 。
我们可以发现，性质1，2是基本对称的，所以我们可以先讨论性质1，再类比性质2
性质1.a: 如图，Size[Right[t]] < Size[Left[Left[t]]],
(1）为了配平，我们可以先将L进行右旋操作，变为下图;
(2)如图，有可能Size[C] or Size[D] 大于 Size[B] ,所以需要再次 Maintain(right[p])(p在上一次操作中指向了L);
(3)调整完后，我们会发现以L为根节点的子树仍有可能不平，所以需要继续执行Maintain(p);
性质1.b: 如图，Size[Right[t]] < Size[Right[Left[t]]],
(1)先调整以L为根节点的子树，对L执行左旋操作，变为下图
(2)再对P执行右旋操作，变为下图。
(3)我们可以发现，虽然这棵树炒鸡不平衡，但子树 A，E，F，R只是挪了挪位置，其平衡性质并没有改变，所以我们只需要再Maintain(L),Maintain(P),Maintain(B)即可。
性质2.a:Size[Left[t]] < Size[Right[Right[t]]]:
与性质1.a刚好相反，可以自行画图理解。
性质2.b:Size[Left[t]] < Size[Left[Right[t]]]:
与性质1.b刚好相反，可以自行画图理解。
其实是我不想画图了
综上，我们可以大致的写出如下程序：
void Maintian(int &p){if (Size[Left[Left[p]]] > Size[Right[p]]){Right_rotate(p);Maintian(Right[p]);Maintian(p);return；}if (Size[Right[Left[p]]] > Size[Right[p]]){Left_rotate(Left[p]);Right_rotate(p);Maintian(Left[p]);Maintian(Right[p]);Maintian(p);return；}if (Size[Left[Left[p]]] > Size[Right[p]]){Left_rotate(p);Maintian(Left[p]);Maintian(p);return；}if (Size[Right[Left[p]]] > Size[Right[p]]){Right_rotate(Right[p]);Left_rotate(p);Maintian(Left[p]);Maintian(Right[p]);Maintian(p);return；}return;}
不过我们还可以有另一种写法，即用一个bool参数flag来表示其究竟是违反了性质1还是性质2，并且将一些重合的操作写在外面
void Maintian(int &p, bool flag){if (!flag){if (Size[Left[Left[p]]] > Size[Right[p]])Right_rotate(p);else if (Size[Right[Left[p]]] > Size[Right[p]]){Left_rotate(Left[p]);Right_rotate(p);}elsereturn;}else{if (Size[Right[Right[p]]] > Size[Left[p]])Left_rotate(p);else if (Size[Left[Right[p]]] > Size[Left[p]]){Right_rotate(Right[p]);Left_rotate(p);}elsereturn;}Maintian(Left[p], false);//以Left[p]为根的子树中，左子树定比右子树的儿子子树的大小要大Maintian(Right[p], true);//以Right[p]为根的子树中，右子树定比左子树的儿子子树的大小要大Maintian(p, true);Maintian(p, false);}
至于 Maintain 的效率云云，可见陈启峰大佬的论文：中文译文版 英文版
3、Insert
与 BST 差不多，只是多加了 Maintain 与 对Size的处理，故直接放代码：
void Insert(int &p, int &v){if (!p){p = ++tot;Val[++p] = v;Size[p] = 1;//Sizereturn;}Size[p]++;//Sizeif (v < Val[p])Insert(Left[p], v);elseInsert(Right[p], v);Maintian(p, v >= Val[p]);//Maintain}
4、Delete
与 BST 差不多，只需再注意对 Size 的处理，直接放代码：
int Delete(int &p, int x){Size[p]--;int tmp;if (x == Val[p] || (x < Val[p] && !Left[p]) || (x > Val[p] && !Right[p])){tmp = Val[p];if (!Left[p] || !Right[p])p = Left[p] + Right[p];elseVal[p] = erase(Left[p], Val[p] + 1);return tmp;}if (x < Val[p])tmp = erase(Left[p], x);elsetmp = erase(Right[p], x);return tmp;}
5、Rank：
查找一个值在树中的大小排名，细节在代码中
int Rank(int &p, int &v){if (p == 0)return 1;if (v <= Val[p])return Rank(Left[p], v);elsereturn Size[Left[p]] + 1 + Rank(Right[p], v);}
6、Select：
查找一个排名在树中的具体值，细节在代码中：
int Select(int &p, int k){if (Size[Left[p]] + 1 == k)return Val[p];if (k <= Size[Left[p]])return Select(Left[p], k);elsereturn Select(Right[p], k - 1 - Size[Left[p]]);}
7、Find:
查找一个值是否存在
bool Find(int &p, int &v){if (p == 0)return 0;if (v < Val[p])return Find(Left[p], v);else if (v == Val[p])return 1;elsereturn Find(Right[p], v);}
8、找前驱/后继：
细节在代码中：
int GetLast(int &p, int &v)//前驱{if (p == 0)return v;int x;if (v <= Val[p])return GetLast(Left[p], v);else{x = GetLast(Right[p], v);if (x == v)x = Val[p];return x;}}int GetNext(int &p, int &v)//后继{if (p == 0)return v;int x;if (v >= Val[p])return GetNext(Right[p], v);else{x = GetNext(Left[p], v);if (x == v)x = Val[p];return x;}}
9、完整代码：
#include <bits/stdc++.h>using namespace std;int n, root, tot;int Right[100100], Left[100100], Size[100100], Val[100100];void Right_rotate(int &p){int k = Left[p];Left[p] = Right[k];Right[k] = p;Size[k] = Size[p];Size[p] = Size[Right[p]] + Size[Left[p]] + 1;p = k;}void Left_rotate(int &p){int k = Right[p];Right[p] = Left[k];Left[k] = p;Size[k] = Size[p];Size[p] = Size[Right[p]] + Size[Left[p]] + 1;p = k;}void Maintian(int &p, bool flag){if (!flag){if (Size[Left[Left[p]]] > Size[Right[p]])Right_rotate(p);else if (Size[Right[Left[p]]] > Size[Right[p]]){Left_rotate(Left[p]);Right_rotate(p);}elsereturn;}else{if (Size[Right[Right[p]]] > Size[Left[p]])Left_rotate(p);else if (Size[Left[Right[p]]] > Size[Left[p]]){Right_rotate(Right[p]);Left_rotate(p);}elsereturn;}Maintian(Left[p], false);Maintian(Right[p], true);Maintian(p, true);Maintian(p, false);}void Insert(int &p, int &v){if (!p){p = ++tot;Val[++p] = v;Size[p] = 1;return;}Size[p]++;if (v < Val[p])Insert(Left[p], v);elseInsert(Right[p], v);Maintian(p, v >= Val[p]);}int Delete(int &p, int x){Size[p]--;int tmp;if (x == Val[p] || (x < Val[p] && !Left[p]) || (x > Val[p] && !Right[p])){tmp = Val[p];if (!Left[p] || !Right[p])p = Left[p] + Right[p];elseVal[p] = erase(Left[p], Val[p] + 1);return tmp;}if (x < Val[p])tmp = erase(Left[p], x);elsetmp = erase(Right[p], x);return tmp;}int Rank(int &p, int &v){if (p == 0)return 1;if (v <= Val[p])return Rank(Left[p], v);elsereturn Size[Left[p]] + 1 + Rank(Right[p], v);}int Select(int &p, int k){if (Size[Left[p]] + 1 == k)return Val[p];if (k <= Size[Left[p]])return Select(Left[p], k);elsereturn Select(Right[p], k - 1 - Size[Left[p]]);}int GetLast(int &p, int &v){if (p == 0)return v;int x;if (v <= Val[p])return GetLast(Left[p], v);else{x = GetLast(Right[p], v);if (x == v)x = Val[p];return x;}}int GetNext(int &p, int &v){if (p == 0)return v;int x;if (v >= Val[p])return GetNext(Right[p], v);else{x = GetNext(Left[p], v);if (x == v)x = Val[p];return x;}}void LDR(int &p){if (p == 0)return;LDR(Left[p]);printf("%d ", Val[p]);LDR(Right[p]);return;}bool Find(int &p, int &v){if (p == 0)return 0;if (v < Val[p])return Find(Left[p], v);else if (v == Val[p])return 1;elsereturn Find(Right[p], v);}int Max(int &p){if (Right[p] != 0)return Max(Right[p]);elsereturn Val[p];}int Min(int &p){if (Left[p] != 0)return Min(Left[p]);elsereturn Val[p];}int main(){scanf("%d", &n);int k, v;for (int i = 1; i <= n; i++){scanf("%d%d", &k, &v);if (k == 1)Insert(root, v);else if (k == 2)Delete(root, v);else if (k == 3)printf("%d\n", Rank(root, v));else if (k == 4)printf("%d\n", Select(root, v));else if (k == 5)printf("%d\n", GetLast(root, v));else if (k == 6)printf("%d\n", GetNext(root, v));else if (k == 7)LDR(root);}return 0;}
四、推荐习题：
1 【模板】普通平衡树
2、郁闷的出纳员
五、关于 SBT 的几个疑惑暂时只有一个
1、为啥没多少人用SBT？？？
六、参考文献：
1、感谢陈启峰大佬的论文（虽然我并没有找到原版）
2、感谢 I_AM_HelloWord，olinr 的博客
