替罪羊树

admin

基本思路，不平衡的就把他打扁，然后重建。什么叫做不平衡呢？我们定义左儿子的节点数和右儿子的节点数差距较大就为不平衡，完美的平衡是左右儿子数量相等，左右儿子各占根总数的50%。但这个很难，一般定义左右儿子中某个数量超过根节点的alpha=75%为不平衡，需要重构。若alpha太大，>80%，重构次数太多，费时，太小<70%，树就不太平衡，影响以后查找和删除的效果。
如何重构呢？暴力点，先把这个子树拍平，中序遍历到一个数组，然后从中间开始二分类似线段树完美建树。
所以在一般的BST基础上，除了ls rs val cnt等之外还需要加上sz记录我这棵树下所有节点的数目。

1. struct node
   
2. {
   
3.         int val,cnt;
   
4.         int ls,rs,sz;  ///lsrs左右儿子  sz本子树下所有节点个数
   
5. } a[N];

复制代码

重建过程

1. void RB(int &rt)   ///重建rt
   
2. {
   
3.         if(rt==0) return;
   
4.         float t=a[rt].sz*p; ///左右儿子不能大于rt的0.75
   
5.         bool b1=a[a[rt].ls].sz>t;
   
6.         bool b2=a[a[rt].rs].sz>t;
   
7. 
   
8.         if( b1|| b2)
   
9.                 {
   
10.                         ita=0;
    
11.                         Inorder(rt);
    
12.                         rt=build(1,ita);
    
13.                 }
    
14. }

复制代码

拍扁的过程，其实就是递归中序遍历，不过是输出到临时数组

1. void Inorder(int rt)   //倒到数组
   
2. {
   
3.         if(rt>0)
   
4.                 {
   
5.                         Inorder(a[rt].ls);
   
6.                         ta[++ita]=rt;
   
7.                         Inorder(a[rt].rs);
   
8.                 }
   
9. }

复制代码

重新完美建树的过程，完全类似线段树

1. int build(int l, int r)   //l-r重新建树
   
2. {
   
3.         if(l>r) return 0;
   
4.         int m=(l+r)/2;
   
5.         a[ta[m]].ls=build(l,m-1);
   
6.         a[ta[m]].rs=build(m+1,r);
   
7.         pushup(ta[m]);
   
8.         return ta[m];
   
9. }

复制代码

admin

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int N = 1001005;
   
4. const float p=0.75;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int ls,rs,sz;  ///lsrs左右儿子  sz本子树下所有节点个数
   
9. } a[N];
   
10. int ta[N],ita;///转移数组
    
11. 
    
12. int n, tot, rt;
    
13. void ArrayPr()
    
14. {
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
16.         cout<<endl;
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
18.         cout<<endl;
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
20.         cout<<endl;
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].ls;
    
22.         cout<<endl;
    
23.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rs;
    
24.         cout<<endl;
    
25.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
26.         cout<<endl;
    
27. 
    
28. }
    
29. 
    
30. void BSTPr(int rt) ///中序输出以rt为根的BST
    
31. {
    
32.         if (a[rt].ls>0)  BSTPr(a[rt].ls);
    
33.         cout<<a[rt].val<<' '; /// 也可以加上cnt
    
34.         if (a[rt].rs>0)  BSTPr(a[rt].rs);
    
35. }
    
36. 
    
37. void pushup(int rt)
    
38. {
    
39.         int l=a[rt].ls, r=a[rt].rs;
    
40.         a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
    
41. }
    
42. 
    
43. int build(int l, int r)//l-r重新建树
    
44. {
    
45.         if(l>r) return 0;
    
46.         int m=(l+r)/2;
    
47.         a[ta[m]].ls=build(l,m-1);
    
48.         a[ta[m]].rs=build(m+1,r);
    
49.         pushup(ta[m]);
    
50.         return ta[m];
    
51. }
    
52. 
    
53. void Inorder(int rt)//倒到数组
    
54. {
    
55.         if(rt>0)
    
56.         {
    
57.                 Inorder(a[rt].ls);
    
58.                 ta[++ita]=rt;
    
59.                 Inorder(a[rt].rs);
    
60.         }
    
61. }
    
62. 
    
63. void RB(int &rt)  ///重建rt
    
64. {
    
65.         if(rt==0) return;
    
66.         float t=a[rt].sz*p; ///左右儿子不能大于rt的0,75
    
67.         bool b1=a[a[rt].ls].sz>t;
    
68.         bool b2=a[a[rt].rs].sz>t;
    
69. 
    
70.         if( b1|| b2)
    
71.         {
    
72.                 ita=0;
    
73.                 Inorder(rt);
    
74.                 rt=build(1,ita);
    
75.         }
    
76. }
    
77. 
    
78. void Ins(int &rt, int x)
    
79. {
    
80.         if(rt==0)
    
81.         {
    
82.                 rt=++tot;
    
83.                 a[rt].val=x;
    
84.                 a[rt].sz=a[rt].cnt = 1;
    
85.         }
    
86.         else
    
87.         {
    
88.                 RB(rt); /// 比原版多一句调整
    
89.                 if(a[rt].val==x) a[rt].cnt ++,a[rt].sz++;
    
90.                 else
    
91.                 {
    
92.                         if(a[rt].val<x) Ins(a[rt].rs, x);
    
93.                         else if(a[rt].val>x) Ins(a[rt].ls, x);
    
94.                         pushup(rt); /// 比原版多一句调整  线段树相似
    
95.                 }
    
96.         }
    
97. }
    
98. 
    
99. int DelMin(int &rt)  ///原版不变
    
100. {
     
101.         int t;
     
102.         if(a[rt].ls==0)///没有左儿子 那就是它
     
103.         {
     
104.                 t=rt;
     
105.                 rt=a[rt].rs;
     
106.                 return t;
     
107.         }
     
108.         else
     
109.         {
     
110.                 t=DelMin(a[rt].ls); ///递归
     
111.                 pushup(rt);///多了这个调整
     
112.                 return t;
     
113.         }
     
114. 
     
115. }
     
116. 
     
117. void Del(int &rt,int x)
     
118. {
     
119.         if (rt==0) return ;
     
120.         else if(a[rt].val>x)
     
121.         {
     
122.                 Del(a[rt].ls,x);
     
123.                 pushup(rt);
     
124.         }
     
125.         else if(a[rt].val<x)
     
126.         {
     
127.                 Del(a[rt].rs,x);
     
128.                 pushup(rt);
     
129.         }
     
130.         else if(a[rt].val==x)
     
131.         {
     
132.                 if(a[rt].cnt>1)a[rt].cnt--,a[rt].sz--;
     
133.                 else if(a[rt].ls==0)rt=a[rt].rs;
     
134.                 else if(a[rt].rs==0)rt=a[rt].ls;
     
135.                 else
     
136.                 {
     
137.                         int t=DelMin(a[rt].rs);
     
138.                         a[rt].val=a[t].val;
     
139.                         a[rt].cnt=a[t].cnt;
     
140.                         pushup(rt);
     
141.                 }
     
142.         }
     
143. }
     
144. 
     
145. int Rank(int rt, int x) ///在RT子树中比x小的数 +1
     
146. {
     
147.         if(a[rt].val==x) return a[a[rt].ls].sz+1; /// 找到了
     
148.         if(a[rt].val<x) return a[a[rt].ls].sz +a[rt].cnt+ Rank(a[rt].rs,x);///左子树下面的都算
     
149.         if(a[rt].val>x) return Rank(a[rt].ls,x);
     
150. }
     
151. 
     
152. int Getkth(int rt, int x) ///在RT子树中找第k小
     
153. {
     
154.         int l=a[a[rt].ls].sz;  /// RT的左儿子下的个数
     
155.         if(l+1<=x && x<=l+a[rt].cnt) return a[rt].val;
     
156.         if(l+1>x) return Getkth(a[rt].ls, x); ///左儿子里去找
     
157.         if(l+a[rt].cnt<x) return Getkth(a[rt].rs, x-(l+a[rt].cnt));
     
158. }
     
159. 
     
160. int Pre(int rt, int x)
     
161. {
     
162.         int p = rt, ans;
     
163.         while(p>0)
     
164.         {
     
165.                 if(x<=a[p].val) p=a[p].ls;
     
166.                 else
     
167.                 {
     
168.                         ans=p;
     
169.                         p=a[p].rs;
     
170.                 }
     
171.         }
     
172.         return ans;
     
173. }
     
174. int Suc(int rt, int x)
     
175. {
     
176.         int p = rt, ans;
     
177.         while(p>0)
     
178.         {
     
179.                 if(a[p].val<=x) p=a[p].rs;
     
180.                 else
     
181.                 {
     
182.                         ans = p;
     
183.                         p=a[p].ls;
     
184.                 }
     
185.         }
     
186.         return ans;
     
187. }
     
188. 
     
189. int main()
     
190. {
     
191.         cin>>n;
     
192.         while(n--)
     
193.         {
     
194.                 int opt, x;
     
195.                 cin>>opt>>x;
     
196.                 if(opt == 1) Ins(rt, x);
     
197.                 if(opt == 2) Del(rt, x);
     
198.                 if(opt == 3) cout<<Rank(rt, x)<<endl;
     
199.                 if(opt == 4) cout<<Getkth(rt, x)<<endl;
     
200.                 if(opt == 5) cout<<a[Pre(rt, x)].val<<endl;
     
201.                 if(opt == 6) cout<<a[Suc(rt, x)].val<<endl;
     
202.                 ///ArrayPr();
     
203.                 ///BSTPr(rt);
     
204.         }
     
205.         return 0;
     
206. }

复制代码