基础知识（包括但不限于：二叉查找树是啥，SBT又是啥反正又不能吃，平衡树怎么旋转，等等）在这里就不（lan）予（de）赘（duo）述（xie）了。
先贴代码（数组模拟）：
int seed;
int _rand()
{
+;
}
template <class T>
struct SbtNode
{
T val;
int lSize;
int rSize;
int lch;
int rch;
void assignVir()
{
lSize=rSize=lch=rch=;
}
void assign(const T& _val)
{
val=_val;
lSize=rSize=lch=rch=;
}
};
template <class T>
struct LesserSbt
{
SbtNode<T> *node; //Dynamic array
int pos;
int root;
LesserSbt()
{
node=];
node[].assignVir();
root=;
//node[0] is a virtual node and the real root is node[1]
}
~LesserSbt()
{
delete[] node;
}
int insert_aux(const T& _val,int _cur)
{
if(!_cur)
{
node[++pos].assign(_val);
return pos;
}
else if( _val < node[_cur].val )
{
++node[_cur].lSize;
node[_cur].lch=insert_aux(_val,node[_cur].lch);
int _lch=node[_cur].lch;
if(node[_lch].lSize > node[_cur].rSize)
{
return rRotate(_cur);
}
else if(node[_lch].rSize >node[_cur].rSize)
{
node[_cur].lch=lRotate(_lch);
return rRotate(_cur);
}
return _cur;
}
else
{
++node[_cur].rSize;
node[_cur].rch=insert_aux(_val,node[_cur].rch);
int _rch=node[_cur].rch;
if(node[_rch].rSize > node[_cur].lSize)
{
return lRotate(_cur);
}
else if(node[_rch].lSize > node[_cur].lSize)
{
node[_cur].rch=rRotate(_rch);
return lRotate(_cur);
}
return _cur;
}
}
void insert(const T& _val)
{
root=insert_aux(_val,root);
}
int lRotate(int _cur)
{
int _next=node[_cur].rch;
node[_cur].rch=node[_next].lch;
node[_cur].rSize=node[_next].lSize;
node[_next].lch=_cur;
node[_next].lSize += (node[_cur].lSize + );
return _next;
}
int rRotate(int _cur)
{
int _next=node[_cur].lch;
node[_cur].lch=node[_next].rch;
node[_cur].lSize=node[_next].rSize;
node[_next].rch=_cur;
node[_next].rSize += (node[_cur].rSize + );
return _next;
}
void clear()
{
pos=root=;
}
int max(int a,int b) {return a>b?a:b;}
int height(int _cur)
{
:;
}
void traverse(int _cur);
};
#include <iostream>
#include <ctime>
#include <set>
template <class T>
void LesserSbt<T>::traverse(int _cur)
{
if(node[_cur].lch) traverse(node[_cur].lch);
std::cout<<node[_cur].val<<"\n";
if(node[_cur].rch) traverse(node[_cur].rch);
}
;
int x[N];
int main()
{
seed=time();
std::set<int> _std;
LesserSbt<int> _sbt(N);
;
clock_t s,t;
while(k--)
{
;i<N;i++) x[i]=_rand();
s=clock();
;i<N;i++) _std.insert(x[i]);
t=clock();
std::cout<<"Using std::set : "<<t-s<<"\n";
_std.clear();
s=clock();
;i<N;i++) _sbt.insert(x[i]);
t=clock();
std::cout<<"Using Lesser SBT : "<<t-s<<" ; Max Height : "<<_sbt.height(_sbt.root)<<"\n";
_sbt.clear();
}
;
}
只写了Insert操作
其实只写Insert操作也不是没有理由的，SBT的查找和删除操作和普通BST（BST=Binary Search Tree）是完全一致的。
再贴上一个动态分配内存版本的（包含了删除和类似于upper_bound的操作）：
template <class T>
struct SbtNode
{
typedef SbtNode<T> Node;
Node* lch;
Node* rch;
T val;
int lSize;
int rSize;
SbtNode(const T& _val):
lch(),rch(),val(_val),lSize(),rSize() {}
void assign(const T& _val)
{
lch=rch=;
val=_val;
lSize=rSize=;
}
};
template <class T,class Comp>
struct SizeBlcTree
{
,Left=,Right= };
typedef SbtNode<T> Node;
typedef SizeBlcTree<T,Comp> Sbt;
Node* root;
Comp cmp;
SizeBlcTree():root() {}
~SizeBlcTree() { clear(); }
void clear_aux(Node* _cur)
{
if(_cur->lch) clear_aux(_cur->lch);
if(_cur->rch) clear_aux(_cur->rch);
delete _cur;
}
void clear()
{
if(root) clear_aux(root);
root=;
}
Node* lRotate(Node* _cur)
{
Node* next=_cur->rch;
_cur->rch=next->lch;
next->lch=_cur;
_cur->rSize=next->lSize;
next->lSize+=(_cur->lSize+);
return next;
}
Node* rRotate(Node* _cur)
{
Node* next=_cur->lch;
_cur->lch=next->rch;
next->rch=_cur;
_cur->lSize=next->rSize;
next->rSize+=(_cur->rSize+);
return next;
}
Node* insert_aux(const T& _val,Node* _cur)
{
if(!_cur) return new Node(_val);
if(cmp(_val,_cur->val))
{
++_cur->lSize;
_cur->lch=insert_aux(_val,_cur->lch);
if(_cur->lch->lSize > _cur->rSize) return rRotate(_cur);
else if(_cur->lch->rSize > _cur->rSize)
{
_cur->lch=lRotate(_cur->lch);
return rRotate(_cur);
}
else return _cur;
}
else
{
++_cur->rSize;
_cur->rch=insert_aux(_val,_cur->rch);
if(_cur->rch->rSize > _cur->lSize) return lRotate(_cur);
else if(_cur->rch->lSize > _cur->lSize)
{
_cur->rch=rRotate(_cur->rch);
return lRotate(_cur);
}
else return _cur;
}
}
Sbt& operator << (const T& _val)
{
root=insert_aux(_val,root);
return *this;
}
Node* erase_aux(const T& _val,Node* _cur,bool& _found)
{
if(!_cur)
{
_found=false;
;
}
if(cmp(_val,_cur->val))
{
_cur->lch=erase_aux(_val,_cur->lch,_found);
if(_found) --_cur->lSize;
return _cur;
}
if(cmp(_cur->val,_val))
{
_cur->rch=erase_aux(_val,_cur->rch,_found);
if(_found) --_cur->rSize;
return _cur;
}
_found=true;
;
;
;
Node* res;
Node* &prev=res;
switch(status)
{
:
delete _cur;
;
:
res=_cur->lch;
delete _cur;
return res;
:
res=_cur->rch;
delete _cur;
return res;
:
prev=_cur;
if(prev->rch->lch)
{
--prev->rSize;
prev=prev->rch;
while(prev->lch->lch)
{
--prev->lSize;
prev=prev->lch;
}
_cur->val=prev->lch->val;
prev->lch=erase_aux(prev->lch->val,prev->lch,_found);
--prev->lSize;
}
else
{
_cur->val=_cur->rch->val;
_cur->rch=erase_aux(_cur->rch->val,_cur->rch,_found);
--_cur->rSize;
}
return _cur;
}
}
Sbt& operator >> (const T& _val)
{
bool found=false;
root=erase_aux(_val,root,found);
return *this;
}
int notMoreCount(const T& _val)
{
Node* cur=root;
;
while(cur)
{
if(cmp(_val,cur->val)) cur=cur->lch;
else
{
res+=(cur->lSize+);
cur=cur->rch;
}
}
return res;
}
};
#include <cstdio>
#include <functional>
int main()
{
]={,,,,,,,,,,,,,,,,,,,};
SizeBlcTree<int,std::less<int> > test;
;i<;i++) test<<x[i];
printf(),test.notMoreCount());
test>>>>>>>>>>;
printf(),test.notMoreCount());
;
}
A "fuller" version of SBT using dynamic memory allocation/deallocation
查找全局第k大，只需利用好每个节点的Size域
不用考虑删除以后SBT失衡的问题，随便Insert几次就又平衡了:-D
另外值的注意的是，代码中的“左旋”和“右旋”分别指“向逆时针方向旋转”和“向顺时针方向旋转”
这两者的另一种理解是“将左边的节点旋转”和“将右边的节点旋转”，两种理解的含义截然相反
谁对谁错并不重要（反正我也不知道O__O"…），怎么理解符合个人习惯就怎么着吧
先简单说几个小技巧吧
1、手打随机函数_rand()
记住这个伪随机数生成公式：an+1 = (1103515245 * an + 12345） mod X
X通常不用刻意设定，让int自然溢出就好
用的时候令seed=time（0）
<cstdlib>头文件里的rand函数貌似是拿汇编写的，两者的效率我没比较过，不过手写rand的一大好处就是：取值范围与平台无关
因为函数很短，所以最好设为inline
2、虚节点
数组模拟的话很好说，用node[0]表示空节点
指针的话也可以设一个virNode指针变量，然后用它代替NULL（即本该等于NULL的指针，让它等于这个virNode）
好处是避免了针对“左/右孩子存不存在”的分类讨论，更重要的是，减少了被打回一个SIGSEGV的可能性。
注意不要让virNode干扰正常的数值统计操作
3、左右子树的size分开记录
一个小小的用空间换时间的技巧
比起只设立一个size域，lSize和rSize两个数据分开可以简化一些操作
而且可以避免诸如“孩子的孩子是否存在”这样的分类讨论
4、函数的“分层”
比如说，代码段里的insert（const T& _val）和insert_aux（const T& _val,int cur）
（顺带一提，aux=auxiliary（adj.辅助的） ）
假如你是用户，我给你这么一段代码，你肯定会偏好简单直白的insert而不是多一个奇怪参数的insert_aux
少掉的一个参数可以看成SBT“底层”的东西，它不需要被用户关心，而且从OOP的角度说，也不应该被用户关心
如果把struct改成class的话，insert就是public的外部借口，而insert_aux则是private的底层操作
函数“分层”的另一个重要用途，就是对于一段操作，如果其中的一个子段需要递归，而其他部分不应递归，那么这一个子段就应该拿出来作为一个独立的函数
举个直观的栗子，你会在main函数里写DFS么？（你写非递归的那就当我没说(￣▽￣")）
5、erase是二叉查找树最恶心的操作没有之一
erase的细节太多了，个人认为删除函数是所有成员函数里最难写的
代码中设立了一个_found引用变量，如果找到该值则为true，否则为false
当且仅当_found=true时更新沿途的size大小
找到目标节点以后大致要分4种情况：
（1）是叶子节点：直接删除，然后向上层返回一个空指针。
（2）只有左孩子：删除该节点并向上层返回原先该节点的左孩子
（3）只有右孩子：删除该节点并向上层返回原先该节点的右孩子
（4）左右孩子都有：这个最麻烦，详见下文
如果目标节点的左右孩子都有，那么：
（1）首先找到该节点的后继（当然也可以是前驱，这个视个人口味（雾）而定）。
节点的后继就是该节点的右孩子的左孩子的左孩子的左孩子……
注意维护后继节点的父节点，以保证删除过程中整棵树不会断裂（因为我们并没有维护每个节点的父节点指针）
（2）交换目标节点和其后继的值
（3）删掉其后继。此时后继的状态只可能是上文框中的前三种情况。
6、Maintain函数可以被省略（？）
也许就是所谓的退化版SBT？
熟悉SBT的读者应该了解其Maintain操作。我在这里就不加介绍了。
其实说实在话，我真心不会Maintain%>_<% o(╯□╰)o
然后我采取了最笨的方法。（这也是为什么我把我的SBT称为LesserSbt，看起来好奇怪的样子(⊙v⊙)）
SBT的定义要求树中任意节点都满足以下不等式组：
node[cur].rSize >= node[lch].lSize ①
node[cur].rSize >= node[lch].rSize ②
node[cur].lSize >= node[rch].lSize ③
node[cur].lSize >= node[rch].rSize ④
我对这四个不等式的理解是：他们一定程度上可以看成平衡树高度的估价函数，size近似与height呈正相关
我们需要一个调整平衡树（也就是旋转）的“标准”，在SBT中，这个“标准”就是：在何种条件下，旋转可以使左、右子树的size之差（绝对值）减小
由估价思想可知，当左右子树size之差减小时，两子树的height之差也会趋向于减小
作图+不等式分析可以验证，当以上4个不等式中的某一个不成立时，相应的调整策略（单旋或双旋）总能使左右子树的size之差变小
我的笨办法就是，在Insert_aux递归退栈的过程中顺路检查一下这4个不等式是否还成立（每一步只需检查两个）
如果不成立，就将当前节点单旋或双旋（①③被破坏就单旋，②④被破坏就双旋，这点可以和AVL的单、双旋类比）
实验表明这样做的效率并不比写一个Maintain函数差，而且省下了Maintain函数的反复递归
最后作为结语，写一点更像是杂谈的东西吧（貌似扯远了⊙﹏⊙b）
和STL比效率，被虐了无数遍以后的悲惨总结
7、除非有必要，尽可能不要重新发明*（关于STL）
时间复杂度不是衡量编程效率的全部，无论是OI/ACM做题还是项目开发，编程复杂度也是一个很重要的衡量因素
废话这么多说白了就是三句：
如果允许-O2优化，善用STL削减编程复杂度
否则，除非时间卡的很严或者STL在少数编译器版本中表现很萎，STL用得恰当也无妨
当然STL无法实现的功能必须要手打(´･ω･｀)
STL已经给我们封装了若干很优秀的基于平衡树的数据结构
如果不需要std：：set不能实现的操作（例如询问第k大），直接用STL就行了
【有兴趣的OIer可以试试__gnu_pbds里的相关数据结构，据说支持查询区间第k大】
很多人说STL效率低，速度慢，但是真的是这样么？
也许不开-O2优化的话可以成立
但即便如此，STL慢也慢得有个样（某些很猥琐的gcc/g++版本除外）
更何况开了-O2优化的情形下，同样的ADT你根本写不过STL
本文给出的模板，在笔者的计算机上可以在450ms（-O2）左右完成100万次插入操作，而std：：set需要650ms（-O2）
但如果让我写一个动态开点的SBT，然后再和STL比效率，那就难说了
而笔者之前写过的一个Treap（动态开点），效率更是低到了STL的2/3（without -O2）甚至1/2（-O2）
OI/ACM的题目是很灵活的，STL无能为力的情况很常见
但是用STL高效AC的情况也许更加常见
所以，STL是不容轻视的，即使存在着种种缺陷，也不愧为C++的经典（Orz）