van Emda Boas

van Emda Boas维护了一个整数集合[0,Max)(无重复),其中Max必须等于2的正整数次幂。它支持以下操作：
（1）插入一个数字;
（2）删除一个数字；
（3）询问某一个数字在不在这个集合中；
（4）询问集合的最大最小值；
（5）询问一个数字的前驱或者后继。
每个操作的复杂度最大为O(loglog(n))

  1 #include <cmath>
  2 #include <algorithm>
  3 
  4 /***
  5   维护的集合范围为[0,MAXU-1]
  6   MAXU必须为2的正整数次幂
  7   MAXU<=2^30
  8 ***/
  9 
 10 
 11 template<int MAXU>
 12 class VanEmdeBoasTree
 13 {
 14 private:
 15 
 16     int m_inValidValue;
 17 
 18     struct TreeNode
 19     {
 20         int Min,Max;
 21 
 22         /**
 23           u为2的某次幂
 24           设u=2^k
 25           若k为偶数 UpBit=k/2
 26           若k为奇数 UpBit=(k+1)/2
 27           DownBit=k-UpBit
 28         **/
 29         int u;
 30         int UpBit;
 31         int DownBit;
 32 
 33         TreeNode* summary;
 34         TreeNode** cluster;
 35 
 36         /**
 37           x的高UpBit位
 38         **/
 39         int high(int x)
 40         {
 41             return x>>DownBit;
 42         }
 43 
 44         /**
 45           x的低DownBit位
 46         **/
 47         int low(int x)
 48         {
 49             return x&((1<<DownBit)-1);
 50         }
 51 
 52         int index(int hx,int lx)
 53         {
 54             return (hx<<DownBit)|lx;
 55         }
 56     };
 57     TreeNode* m_root;
 58     int m_MAXRANGE;
 59 
 60 
 61     /**
 62        已知u=2^k  返回k
 63     **/
 64     int GetSumBit(const int u)
 65     {
 66         return int(log2(u)+0.5);
 67     }
 68 
 69     void build(TreeNode* &root,const int u)
 70     {
 71         root->Min=m_inValidValue;
 72         root->Max=m_inValidValue;
 73         root->u=u;
 74 
 75         if(2==u) return;
 76 
 77         const int k=GetSumBit(u);
 78         root->UpBit=(k+1)>>1;
 79         root->DownBit=k>>1;
 80 
 81         root->summary=new TreeNode;
 82         build(root->summary,1<<root->UpBit);
 83 
 84         root->cluster=new TreeNode*[1<<root->UpBit];
 85         for(int i=0;i<(1<<root->UpBit);i++)
 86         {
 87             root->cluster[i]=new TreeNode;
 88             build(root->cluster[i],1<<root->DownBit);
 89         }
 90     }
 91 
 92     int GetMinValue(TreeNode *rt) { return rt->Min; }
 93     int GetMaxValue(TreeNode *rt) { return rt->Max; }
 94 
 95     int getSuccessor(TreeNode* curNode,int x)
 96     {
 97         if(2==curNode->u)
 98         {
 99             if(x==0&&curNode->Max==1) return 1;
100             else return m_inValidValue;
101         }
102         else if(curNode->Min!=m_inValidValue&&x<curNode->Min)
103         {
104             return curNode->Min;
105         }
106         else
107         {
108             const int highX=curNode->high(x);
109             const int lowX=curNode->low(x);
110 
111             int MaxLow=GetMaxValue(curNode->cluster[highX]);
112             if(MaxLow!=m_inValidValue&&lowX<MaxLow)
113             {
114                 return curNode->index(highX,
115                                       getSuccessor(curNode->cluster[highX],lowX));
116             }
117             else
118             {
119                 int successCluster=getSuccessor(curNode->summary,highX);
120                 if(successCluster==m_inValidValue) return m_inValidValue;
121                 else
122                 {
123                     return curNode->index(successCluster,
124                                           GetMinValue(curNode->cluster[successCluster]));
125                 }
126             }
127         }
128     }
129 
130     int getPredecessor(TreeNode* curNode,int x)
131     {
132         if(2==curNode->u)
133         {
134             if(1==x&&0==curNode->Min) return 0;
135             else return m_inValidValue;
136         }
137         else if(curNode->Max!=m_inValidValue&&x>curNode->Max)
138         {
139             return curNode->Max;
140         }
141         else
142         {
143             const int highX=curNode->high(x);
144             const int lowX=curNode->low(x);
145 
146             int MinLow=GetMinValue(curNode->cluster[highX]);
147             if(MinLow!=m_inValidValue&&lowX>MinLow)
148             {
149                 return curNode->index(highX,
150                                       getPredecessor(curNode->cluster[highX],lowX));
151             }
152             else
153             {
154                 int predCluster=getPredecessor(curNode->summary,highX);
155                 if(predCluster==m_inValidValue)
156                 {
157                     if(curNode->Min!=m_inValidValue&&x>curNode->Min)
158                     {
159                         return curNode->Min;
160                     }
161                     else return m_inValidValue;
162                 }
163                 else
164                 {
165                     return curNode->index(predCluster,
166                                           GetMaxValue(curNode->cluster[predCluster]));
167                 }
168             }
169         }
170     }
171 
172     void insertEmptyNode(TreeNode* curNode,int x)
173     {
174         curNode->Min=curNode->Max=x;
175     }
176 
177     void insert(TreeNode* curNode,int x)
178     {
179         if(curNode->Min==m_inValidValue)
180         {
181             insertEmptyNode(curNode,x);
182             return;
183         }
184         if(x==curNode->Min||x==curNode->Max) return;
185         if(x<curNode->Min)
186         {
187             std::swap(x,curNode->Min);
188         }
189         if(curNode->u>2)
190         {
191             const int highX=curNode->high(x);
192             const int lowX=curNode->low(x);
193             if(GetMinValue(curNode->cluster[highX])==m_inValidValue)
194             {
195                 insert(curNode->summary,highX);
196                 insertEmptyNode(curNode->cluster[highX],lowX);
197             }
198             else
199             {
200                 insert(curNode->cluster[highX],lowX);
201             }
202         }
203         if(x>curNode->Max) curNode->Max=x;
204     }
205 
206     void remove(TreeNode* curNode,int x)
207     {
208         if(curNode->Min==curNode->Max)
209         {
210             curNode->Min=curNode->Max=m_inValidValue;
211             return;
212         }
213         if(curNode->u==2)
214         {
215             if(x==0) curNode->Min=1;
216             else curNode->Min=0;
217             curNode->Max=curNode->Min;
218             return;
219         }
220         if(x==curNode->Min)
221         {
222             int firstCluster=GetMinValue(curNode->summary);
223             x=curNode->index(firstCluster,
224                              GetMinValue(curNode->cluster[firstCluster]));
225             curNode->Min=x;
226         }
227 
228         const int highX=curNode->high(x);
229         const int lowX=curNode->low(x);
230         remove(curNode->cluster[highX],lowX);
231         if(GetMinValue(curNode->cluster[highX])==m_inValidValue)
232         {
233             remove(curNode->summary,highX);
234             if(x==curNode->Max)
235             {
236                 int summaryMax=GetMaxValue(curNode->summary);
237                 if(summaryMax==m_inValidValue) curNode->Max=curNode->Min;
238                 else
239                 {
240                     curNode->Max=curNode->index(summaryMax,
241                                                 GetMaxValue(curNode->cluster[summaryMax]));
242                 }
243             }
244         }
245         else
246         {
247             if(x==curNode->Max)
248             {
249                 curNode->Max=curNode->index(highX,
250                                             GetMaxValue(curNode->cluster[highX]));
251             }
252         }
253     }
254 
255 public:
256 
257     /**
258       构造函数需要提供类型的无效值
259     **/
260     VanEmdeBoasTree(const int inValidValue=-1)
261     {
262         m_MAXRANGE=MAXU;
263         m_inValidValue=inValidValue;
264         m_root=new TreeNode;
265         build(m_root,MAXU);
266     }
267 
268     /**
269       key存在 返回1 否则返回0
270     **/
271     int isExist(int key)
272     {
273         if(key<0||key>=MAXU) return 0;
274 
275         TreeNode* curNode=m_root;
276         while(1)
277         {
278             if(key==curNode->Min||key==curNode->Max) return 1;
279             else if(2==curNode->u) return 0;
280             else
281             {
282                 TreeNode *nextNode=curNode->cluster[curNode->high(key)];
283                 key=curNode->low(key);
284                 curNode=nextNode;
285             }
286         }
287     }
288 
289     /**
290       查找key的后继 即大于key最小的值
291       若没有 返回m_inValidValue
292     **/
293     int getSuccessor(int key)
294     {
295         if(key<0) return GetMinValue(m_root);
296         if(key>=m_MAXRANGE) return m_inValidValue;
297         return getSuccessor(m_root,key);
298     }
299 
300     /**
301       查找key的前驱 即小于key最大的值
302       若没有 返回m_inValidValue
303     **/
304     int getPredecessor(int key)
305     {
306         if(key<0) return m_inValidValue;
307         if(key>=m_MAXRANGE) return GetMaxValue(m_root);
308         return getPredecessor(m_root,key);
309     }
310 
311     void insert(int key)
312     {
313         if(key<0||key>=m_MAXRANGE) return;
314         insert(m_root,key);
315     }
316 
317     void remove(int key)
318     {
319         if(key<0||key>=m_MAXRANGE) return;
320         remove(m_root,key);
321     }
322 
323     int GetMaxValue()
324     {
325         return GetMaxValue(m_root);
326     }
327 
328     int GetMinValue()
329     {
330         return GetMinValue(m_root);
331     }
332 };
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jianglangcaijin/p/6004241.html