平衡二叉查找树
既Size Balanced Tree。
左旋 右旋 维护 ： 这个比较容易理解，《Size Balanced Tree》对维护操作的复杂度分析是均摊O(1)，优美
插入：普通BST插入，进行树形状的调整
删除：用BST的删除方法，要找到删除节点的最小关键字或最大关键字，来进行替换。
代码
1 #include <algorithm>
2 #include <cstdio>
3 using namespace std;
4
5 const int maxn = 100005;
6 int NEW = 0, n, m;
7 int size[maxn], left[maxn], right[maxn], key[maxn];
8 int val[maxn];
9
10 void Left_Rotate(int &x) {
11 int k = right[x];
12 right[x] = left[k];
13 left[k] = x;
14 size[k] = size[x];
15 size[x] = size[ left[x] ] + size[ right[x] ] + 1;
16 x = k;
17 }
18
19 void Right_Rotate(int &x) {
20 int k = left[x];
21 left[x] = right[k];
22 right[k] = x;
23 size[k] = size[x];
24 size[x] = size[ left[x] ] + size[ right[x] ] + 1;
25 x = k;
26 }
27
28 void Maintain(int &x, bool Right) {
29 if(!x) return ;
30 if(!Right) {
31 if(size[ left[ left[x] ] ] > size[ right[x] ])
32 Right_Rotate(x);
33 else if(size[ right[ left[x] ] ] > size[ right[x] ])
34 Left_Rotate( left[x] ) , Right_Rotate(x);
35 else
36 return ;
37 } else {
38 if(size[ right[ right[x] ] ] > size[ left[x] ])
39 Left_Rotate(x);
40 else if(size[ left[ right[x] ] ] > size[ left[x] ])
41 Right_Rotate( right[x] ) , Left_Rotate(x);
42 else
43 return ;
44 }
45 Maintain(left[x] , false);
46 Maintain(right[x] , true);
47 Maintain(x , false);
48 Maintain(x , true);
49 }
50
51 void insert(int &x, int delta) {
52 if(!x) {
53 x = ++ NEW;
54 size[x] = 1;
55 key[x] = delta;
56 } else {
57 size[x] ++;
58 if(key[x] > delta)
59 insert(left[x] , delta);
60 else
61 insert(right[x] , delta);
62 Maintain(x , delta >= key[x]);
63 }
64 }
65
66 int Delete(int &x, int delta)
67 {
68 if(!x) return 0;
69 size[x] --;
70 if(delta == key[x] || (delta < key[x] && !left[x]) || (delta > key[x] && !right[x]) )
71 {
72 if(left[x] && right[x]) {
73 int p = Delete(left[x] , delta + 1);
74 key[x] = key[p];
75 return p;
76 } else {
77 int p = x;
78 x = left[x] + right[x];
79 return p;
80 }
81 } else {
82 if(delta < key[x])
83 Delete(left[x] , delta);
84 else
85 Delete(right[x] , delta);
86 }
87 }
88
89
90 int select_max(int &x, int k)
91 {
92 if(!x) return -1;
93 int r = size[ right[x] ] + 1;
94 if(r < k)
95 select_max(left[x] , k - r);
96 else if(r > k)
97 select_max(right[x] , k);
98 else
99 return key[x];
100 }
101
102 int select_min(int &x, int k) {
103 if(!x) return -1;
104 int l = size[ left[x] ] + 1;
105 if(l < k)
106 select_min(right[x] , k - l);
107 else if(l > k)
108 select_min(left[x] , k);
109 else
110 return key[x];
111 }
112
113 int ans[maxn];
114 struct NODE { int u, v, k, id; } A[maxn];
115
116 bool operator < (const NODE x, const NODE y)
117 {
118 if(x.u == y.u)
119 return x.v < y.v;
120 return x.u < y.u;
121 }
122
123 int main()
124 {
125 NEW = 0;
126 scanf("%d %d", &n, &m);
127 int root = 0;
128
129 for(int i=1; i <= n; i++)
130 scanf("%d", &val[i]);
131
132 for(int i=0; i < m; i++) {
133 scanf("%d %d %d", &A[i].u, &A[i].v, &A[i].k);
134 if(A[i].u > A[i].v)
135 swap(A[i].u , A[i].v);
136 A[i].id = i;
137 }
138
139 sort(A, A + m);
140
141 int st = A[0].u, et = A[0].v;
142 for(int j=st; j <= et; j++)
143 insert(root , val[j]);
144 ans[ A[0].id ] = select_min(root , A[0].k);
145
146 for(int i=1; i < m; i++) {
147
148 if(A[i].v <= A[i - 1].v) {
149 for(int j=A[i - 1].u; j < A[i].u; j++)
150 Delete(root , val[j]);
151 for(int j=A[i].v + 1; j <= A[i - 1].v; j++)
152 Delete(root , val[j]);
153 st = 1; et = 0;
154 } else if(A[i].u <= A[i - 1].v && A[i].v >= A[i - 1].v) {
155 for(int j=A[i - 1].u; j < A[i].u; j++)
156 Delete(root , val[j]);
157 st = A[i - 1].v + 1; et = A[i].v;
158 } else {
159 for(int j=A[i - 1].u; j <= A[i - 1].v; j++)
160 Delete(root , val[j]);
161 st = A[i].u; et = A[i].v;
162 }
163
164 for(int j=st; j <= et; j++)
165 insert(root , val[j]);
166 ans[ A[i].id ] = select_min(root , A[i].k);
167
168 }
169
170 for(int i=0; i < m; i++)
171 printf("%d\n", ans[i]);
172 return 0;
173 }
- 最新评论