子樹大小平衡樹（Size Balanced Tree，SBT）Insert操作模板及雜談

基礎知識（包括但不限於：二叉查找樹是啥，SBT又是啥反正又不能吃，平衡樹怎麼旋轉，等等）在這裡就不（lan）予（de）贅（duo）述（xie）了。由於學生黨比較忙，所以博文寫的比較簡略，有時間會慢慢補完先貼代碼： 1 int seed; 2 int _rand() 3 { 4 return se ...

基礎知識（包括但不限於：二叉查找樹是啥，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()

記住這個偽隨機數生成公式：a_n+1 = (1103515245 * a_n + 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++的經典