子樹大小平衡樹（Size Balanced Tree，SBT）Insert操作模板及雜談，balancedsbt
基礎知識（包括但不限於：二叉查找樹是啥，SBT又是啥反正又不能吃，平衡樹怎麼旋轉，等等）在這裡就不（lan）予（de）贅（duo）述（xie）了。
由於學生黨比較忙，所以博文寫的比較簡略，有時間會慢慢補完
先貼代碼：
![]()
1 int seed;
2 int _rand()
3 {
4 return seed=seed*1103515245+12345;
5 }
6
7 template <class T>
8 struct SbtNode
9 {
10 T val;
11 int lSize;
12 int rSize;
13 int lch;
14 int rch;
15
16 void assignVir()
17 {
18 lSize=rSize=lch=rch=0;
19 }
20 void assign(const T& _val)
21 {
22 val=_val;
23 lSize=rSize=lch=rch=0;
24 }
25 };
26
27 template <class T>
28 struct LesserSbt
29 {
30 SbtNode<T> *node; //Dynamic array
31 int pos;
32 int root;
33
34 LesserSbt(int size):pos(0)
35 {
36 node=new SbtNode<T> [size+60];
37 node[0].assignVir();
38 root=0;
39 //node[0] is a virtual node and the real root is node[1]
40 }
41
42 ~LesserSbt()
43 {
44 delete[] node;
45 }
46
47 int insert_aux(const T& _val,int _cur)
48 {
49 if(!_cur)
50 {
51 node[++pos].assign(_val);
52 return pos;
53 }
54 else if( _val < node[_cur].val )
55 {
56 ++node[_cur].lSize;
57 node[_cur].lch=insert_aux(_val,node[_cur].lch);
58
59 int _lch=node[_cur].lch;
60 if(node[_lch].lSize > node[_cur].rSize)
61 {
62 return rRotate(_cur);
63 }
64 else if(node[_lch].rSize >node[_cur].rSize)
65 {
66 node[_cur].lch=lRotate(_lch);
67 return rRotate(_cur);
68 }
69 return _cur;
70 }
71 else
72 {
73 ++node[_cur].rSize;
74 node[_cur].rch=insert_aux(_val,node[_cur].rch);
75
76 int _rch=node[_cur].rch;
77 if(node[_rch].rSize > node[_cur].lSize)
78 {
79 return lRotate(_cur);
80 }
81 else if(node[_rch].lSize > node[_cur].lSize)
82 {
83 node[_cur].rch=rRotate(_rch);
84 return lRotate(_cur);
85 }
86 return _cur;
87 }
88 }
89
90 void insert(const T& _val)
91 {
92 root=insert_aux(_val,root);
93 }
94
95 int lRotate(int _cur)
96 {
97 int _next=node[_cur].rch;
98
99 node[_cur].rch=node[_next].lch;
100 node[_cur].rSize=node[_next].lSize;
101
102 node[_next].lch=_cur;
103 node[_next].lSize += (node[_cur].lSize + 1);
104
105 return _next;
106 }
107
108 int rRotate(int _cur)
109 {
110 int _next=node[_cur].lch;
111
112 node[_cur].lch=node[_next].rch;
113 node[_cur].lSize=node[_next].rSize;
114
115 node[_next].rch=_cur;
116 node[_next].rSize += (node[_cur].rSize + 1);
117
118 return _next;
119 }
120
121 void clear()
122 {
123 pos=root=0;
124 }
125
126 int max(int a,int b) {return a>b?a:b;}
127
128 int height(int _cur)
129 {
130 return _cur?max(height(node[_cur].lch),height(node[_cur].rch))+1:0;
131 }
132
133 void traverse(int _cur);
134 };
135
136 #include <iostream>
137 #include <ctime>
138 #include <set>
139
140 template <class T>
141 void LesserSbt<T>::traverse(int _cur)
142 {
143 if(node[_cur].lch) traverse(node[_cur].lch);
144 std::cout<<node[_cur].val<<"\n";
145 if(node[_cur].rch) traverse(node[_cur].rch);
146 }
147
148 const int N=1000000;
149
150 int x[N];
151 int main()
152 {
153 seed=time(0);
154
155 std::set<int> _std;
156 LesserSbt<int> _sbt(N);
157
158 int k=10;
159 clock_t s,t;
160 while(k--)
161 {
162 for(int i=0;i<N;i++) x[i]=_rand();
163
164 s=clock();
165 for(int i=0;i<N;i++) _std.insert(x[i]);
166 t=clock();
167 std::cout<<"Using std::set : "<<t-s<<"\n";
168 _std.clear();
169
170 s=clock();
171 for(int i=0;i<N;i++) _sbt.insert(x[i]);
172 t=clock();
173 std::cout<<"Using Lesser SBT : "<<t-s<<" ; Max Height : "<<_sbt.height(_sbt.root)<<"\n";
174 _sbt.clear();
175 }
176
177 return 0;
178 }
探女小姐姐很懶所以只寫了Insert操作(*^__^*)當然以後有時間會把其他操作也補上
其實只寫Insert操作也不是沒有理由的，SBT的查找和刪除操作和普通BST（BST=Binary Search Tree）是完全一致的。
查找全局第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、Maintain函數可以被省略（？）
熟悉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）
6、不要重新發明輪子
時間復雜度不是衡量編程效率的全部，無論是OI/ACM做題還是項目開發，編程復雜度也是一個很重要的衡量因素
STL已經給我們封裝了若干很優秀的基於平衡樹的數據結構
如果不需要std：：set不能實現的操作（例如詢問第k大），直接用STL就行了
很多人說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++的經典
