1 //SBTree
  2 #include <iostream>
  3 using namespace std;
  4 
  5 //结点类
  6 template <typename Type>
  7 class SBTnode{
  8 public:
  9     Type data;
 10     int size;
 11     SBTnode<Type> *lchild, *rchild, *father;
 12     SBTnode(Type init_data, int init_size=0, SBTnode<Type> *init_father=NULL);
 13     ~SBTnode();
 14     
 15     SBTnode<Type>* search(Type value);
 16     SBTnode<Type>* predecessor();
 17     SBTnode<Type>* successor();
 18     void remove_node(SBTnode<Type> *delete_node);
 19     bool remove(Type value);
 20     void inorder();
 21     int Rank(SBTnode<Type> *node);
 22     int select(int k);
 23 };
 24 
 25 //this is a trick to make the comparison easier
 26 //we can use NIL->size for comparison (but NULL cannot)
 27 SBTnode<int> ZERO(0);
 28 SBTnode<int> *NIL=&ZERO;
 29 
 30 //结点类的构造
 31 //之前已经有过声明,所以ZERO可以调用此构造函数
 32 template <typename Type>
 33 SBTnode<Type>::SBTnode(Type init_data, int init_size, SBTnode<Type> *init_father){
 34     data=http://www.mamicode.com/init_data;
 35     size=init_size;
 36     father=init_father;
 37     //注意所有child默认初始化为NIL(size=0)
 38     lchild=NIL;
 39     rchild=NIL;
 40 }
 41 
 42 //结点类的析构
 43 template <typename Type>
 44 SBTnode<Type>::~SBTnode(){
 45     if(lchild!=NIL){
 46         delete lchild;
 47     }
 48     if(rchild!=NIL){
 49         delete rchild;
 50     }
 51 }
 52 
 53 //结点类的中序遍历
 54 template <typename Type>
 55 void SBTnode<Type>::inorder(){
 56     if(lchild!=NIL){
 57         lchild->inorder();
 58     }
 59     cout<<data<<" ";
 60     if(rchild!=NIL){
 61         rchild->inorder();
 62     }
 63 }
 64 
 65 
 66 //SBT类
 67 template <typename Type>
 68 class SBT{
 69 private:
 70     SBTnode<Type> *root;
 71 public:
 72     SBT(){
 73         root=NULL;
 74     }
 75     ~SBT(){
 76         if(root!=NULL) delete root;
 77     }
 78     
 79     void insert(Type value);
 80     bool find(Type value);
 81     bool remove(Type value);
 82     void inorder(){
 83         if(root!=NULL) root->inorder();
 84         cout<<endl;
 85     }
 86     int Rank(Type value);
 87     void Display();
 88     int get_size(SBTnode<Type> *node){
 89         return node->size;
 90     }
 91     int select(int k);
 92 };
 93 
 94 //左旋函数
 95 template <typename Type>
 96 SBTnode<Type>* left_rotate(SBTnode<Type>* node) {
 97     SBTnode<Type>* temp = node->rchild;
 98     node->rchild = temp->lchild;
 99     temp->lchild->father = node;
100     temp->lchild = node;
101     temp->father = node->father;
102     node->father = temp;
103     temp->size = node->size;
104     node->size = node->lchild->size + node->rchild->size + 1;
105     return temp;
106 }
107 
108 //右旋函数
109 template <typename Type>
110 SBTnode<Type>* right_rotate(SBTnode<Type>* node) {
111     SBTnode<Type>* temp = node->lchild;
112     node->lchild = temp->rchild;
113     temp->rchild->father = node;
114     temp->rchild = node;
115     temp->father = node->father;
116     node->father = temp;
117     temp->size = node->size;
118     node->size = node->lchild->size + node->rchild->size + 1;
119     return temp;
120 }
121 
122 //maintain函数
123 template <typename Type>
124 SBTnode<Type>* maintain(SBTnode<Type> *node, bool flag){
125     if(flag==false){
126         if(node->lchild->lchild->size > node->rchild->size){
127             node=right_rotate(node);
128         }
129         else if(node->lchild->rchild->size > node->rchild->size){
130             node->lchild=left_rotate(node->lchild);
131             node=right_rotate(node);
132         }
133         else{
134             return node;
135         }
136     }
137     else{
138         if(node->rchild->rchild->size > node->lchild->size){
139             node=left_rotate(node);
140         }
141         else if(node->rchild->lchild->size > node->lchild->size){
142             node->rchild=right_rotate(node->rchild);
143             node=left_rotate(node);
144         }
145         else{
146             return node;
147         }
148     }
149     //根据cqf的证明,(node->lchild,true)和(node->rchild,false)可以省略
150     node->lchild=maintain(node->lchild, false);
151     node->rchild=maintain(node->rchild, true);
152     node=maintain(node,true);
153     node=maintain(node,false);
154     return node;
155 }
156 
157 //Insert函数
158 template <typename Type>
159 SBTnode<Type>* Insert(SBTnode<Type> *node, Type value){
160     //先更新size,这会影响之后的自平衡条件
161     node->size++;
162     if(value>node->data){
163         if(node->rchild==NIL){
164             node->rchild=new SBTnode<Type>(value,1,node);
165         }
166         else{
167             node->rchild=Insert(node->rchild,value);
168         }
169     }
170     else{
171         if(node->lchild==NIL){
172             node->lchild=new SBTnode<Type>(value,1,node);
173         }
174         else{
175             node->lchild=Insert(node->lchild,value);
176         }
177     }
178     //插完后maintain,并返回调整后的根结点
179     return maintain(node,value>node->data);
180 }
181 
182 
183 template <typename Type>
184 SBTnode<Type>* SBTnode<Type>::search(Type value){
185     if(data=http://www.mamicode.com/=value){
186         return this;
187     }
188     else if(value>data){
189         if(rchild==NIL){
190             return NIL;
191         }
192         else{
193             return rchild->search(value);
194         }
195     }
196     else{
197         if(lchild==NIL){
198             return NIL;
199         }
200         else{
201             return lchild->search(value);
202         }
203     }
204 }
205 
206 
207 template <typename Type>
208 SBTnode<Type> *SBTnode<Type>::predecessor(){
209     SBTnode<Type> *temp=lchild;
210     while(temp!=NIL&&temp->rchild!=NIL){
211         temp=temp->rchild;
212     }
213     return temp;
214 }
215 
216 
217 template <typename Type>
218 SBTnode<Type> *SBTnode<Type>::successor(){
219     SBTnode<Type> *temp=rchild;
220     while(temp!=NIL&&temp->lchild!=NIL){
221         temp=temp->lchild;
222     }
223     return temp;
224 }
225 
226 //remove_node func for nodes with one or no child 
227 template <typename Type>
228 void SBTnode<Type>::remove_node(SBTnode<Type>* delete_node){
229     SBTnode<Type>* temp=NIL;
230     if(delete_node->lchild!=NIL){
231         temp=delete_node->lchild;
232         temp->father=delete_node->father;
233         //set lchild to be NIL so that its lchild won‘t be deleted later
234         delete_node->lchild=NIL;
235     }
236     if(delete_node->rchild!=NIL){
237         temp=delete_node->rchild;
238         temp->father=delete_node->father;
239         //same as above
240         delete_node->rchild=NIL;
241     }
242     if(delete_node->father->lchild==delete_node){
243         delete_node->father->lchild=temp;
244     }
245     else{
246         delete_node->father->rchild=temp;
247     }
248     temp=delete_node;
249     //更新所有包含此结点的结点的size
250     //注意循环条件为temp!=NULL,因为根结点的默认father=NULL,not NIL
251     while(temp!=NULL){
252         temp->size--;
253         temp=temp->father;
254     }
255     delete delete_node;
256 }
257 
258 //remove func for any node
259 template <typename Type>
260 bool SBTnode<Type>::remove(Type value){
261     SBTnode<Type> *delete_node, *current_node;
262     current_node=search(value);
263     if(current_node==NIL){
264         return false;
265     }
266     if(current_node->lchild!=NIL){
267         delete_node=current_node->predecessor();
268     }
269     else if(current_node->rchild!=NIL){
270         delete_node=current_node->successor();
271     }
272     else{
273         delete_node=current_node;
274     }
275     current_node->data=http://www.mamicode.com/delete_node->data;
276     remove_node(delete_node);
277     return true;
278 }
279 
280 template <typename Type>
281 void SBT<Type>::insert(Type value){
282     if(root==NULL){
283         root=new SBTnode<Type>(value,1);
284     }
285     else if(root->search(value)==NIL){
286         root=Insert(root,value);
287     }
288 }
289 
290 template <typename Type>
291 bool SBT<Type>::find(Type value){
292     if(root->search(value)==NIL){
293         return false;
294     }
295     else{
296         return true;
297     }
298 }
299 
300 
301 template <typename Type>
302 bool SBT<Type>::remove(Type value){
303     return root->remove(value);
304 }
305 
306 //求结点node在以当前结点为根结点的子树的rank
307 //从小到大排
308 template <typename Type>
309 int SBTnode<Type>::Rank(SBTnode<Type> *node){
310     if(node->data =http://www.mamicode.com/= data){
311         return lchild->size+1;
312     }
313     else if(node->data > data){
314         return lchild->size+1 + rchild->Rank(node);
315     }
316     else{
317         return lchild->Rank(node);
318     }
319 }
320 
321 //for testing
322 template <typename Type>
323 void display(SBTnode<Type>* cur, int level){
324     if(cur!=NIL){
325         display(cur->rchild, level+1);
326         cout<<endl;
327         for(int i=0;i<level;i++){
328             cout<<"      ";
329         }
330         cout<<cur->data;
331         display(cur->lchild, level+1);
332     }
333 }
334 
335 //for testing
336 template <typename Type>
337 void SBT<Type>::Display(){
338     display(root,0);
339 }
340 
341 //求值为value的结点在整棵树中的从小到大排名
342 template <typename Type>
343 int SBT<Type>::Rank(Type value){
344     SBTnode<Type> *temp;
345     temp=root->search(value);
346     if(temp==NIL){
347         return 0;
348     }
349     else{
350         return root->Rank(temp);
351     }
352 }
353 
354 //求当前子树中第k小的结点的data
355 template <typename Type>
356 int SBTnode<Type>::select(int k){
357     int rank=lchild->size+1;
358     if(rank==k){
359         return data;
360     }
361     else if(k<rank){
362         //结点在左子树中的排名和当前子树中的排名是一样的
363         return lchild->select(k);
364     }
365     else{
366         //右子树中会从1开始重新排
367         //所以结点在右子树中的rank+根结点的rank=结点在整棵子树中的rank
368         return rchild->select(k-rank);
369     }
370 }
371 
372 //求整棵树中第k小的结点的data
373 template <typename Type>
374 int SBT<Type>::select(int k){
375     return root->select(k);
376 }