#include<iostream>#include<math.h>#define NIL 9999#define MAX 100using namespace std;struct Van_Emde_Boas {//veb树节点 int u;int min; int max;Van_Emde_Boas *summary=NULL;Van_Emde_Boas *cluster[MAX];};//创建vbn树 void vEB_TREE_CREATE(Van_Emde_Boas *V,int u){V->u=u;int min=NIL; int max=NIL;for(int j=0;j<MAX;j++){V->cluster[j]=NULL;}if(u!=2) {int su=(int)sqrt((double)u);V->summary=new Van_Emde_Boas;vEB_TREE_CREATE(V->summary,su);for(int i=0;i<su;i++) {V->cluster[i]=new Van_Emde_Boas;vEB_TREE_CREATE(V->cluster[i],su);}}} //交换函数void swap(int *a,int *b) {int temp=*a;*a=*b;*b=temp;} //high函数 int high(int x,int u) {return (int)floor(x/sqrt((double)u));}//low 函数int low(int x,int u){return x%(int)sqrt((double)u);} //index函数 int index(int x,int y,int u){return x*(int)sqrt((double)u)+y;}//返回vbn树中的最小值 int vEB_TREE_MINIMUM(Van_Emde_Boas *V) {return V->min;}//返回vbn树中的最大值 int vEB_TREE_MAXIMUM(Van_Emde_Boas *V) {return V->max;}//判断一个值是否在集合中bool vEB_TREE_MEMBER(Van_Emde_Boas *V,int x,int u) {if(x==V->min || x==V->max) {return true;} else {if(V->u==2){return false;} else {return vEB_TREE_MEMBER(V->cluster[high(x,u)],low(x,u),u);}}}//查找后继int vEB_TREE_SUCCESSOR(Van_Emde_Boas *V,int x,int u) {if(V->u==2) {if(x==0 && V->max==1) {return 1;} else {return NIL;}} else {if(V->min!=NIL && x<V->min) {return V->min;} else {int max_low=vEB_TREE_MAXIMUM(V->cluster[high(x,u)]);if(max_low!=NIL && low(x,u)<max_low) {int offset=vEB_TREE_SUCCESSOR(V->cluster[high(x,u)],low(x,u),u);return index(high(x,u),offset,u);} else {int succ_cluster=vEB_TREE_SUCCESSOR(V->summary,high(x,u),u);if(succ_cluster==NIL) {return NIL;} else {int offset=vEB_TREE_MINIMUM(V->cluster[succ_cluster]);return index(succ_cluster,offset,u);}}}}}//查找前驱 int vEB_TREE_PREDECESSOR(Van_Emde_Boas *V,int x,int u) {if(V->u==2) {if(x==1 && V->min==0) {return 0;} else {return NIL;}} else {if(V->max!=NIL && x>V->max) {return V->max;} else {int min_low=vEB_TREE_MINIMUM(V->cluster[high(x,u)]);if(min_low!=NIL && low(x,u)>min_low) {int offset=vEB_TREE_PREDECESSOR(V->cluster[high(x,u)],low(x,u),u);return index(high(x,u),offset,u);} else {int pred_cluster=vEB_TREE_PREDECESSOR(V->summary,high(x,u),u);if(pred_cluster==NIL) {if(V->min!=NIL &&x>V->max) {return V->min;} else {return NIL;}} else {int offset=vEB_TREE_MINIMUM(V->cluster[pred_cluster]);return index(pred_cluster,offset,u);}}}}}//插入一个空树void vEB_EMPTY_TREE_INSERT(Van_Emde_Boas *V,int x) {V->min=x;V->max=x;} //插入一个 元素void vEB_TREE_INSERT(Van_Emde_Boas *V,int x,int u) {if(V->min==NIL) {vEB_EMPTY_TREE_INSERT(V,x);} else {//第一种情况 if(x<V->min) {swap(&x,&V->min);}//第二种情况if(V->u>2) {if(vEB_TREE_MINIMUM(V->cluster[high(x,u)])==NIL) {vEB_TREE_INSERT(V->summary,high(x,u),u);vEB_EMPTY_TREE_INSERT(V->cluster[high(x,u)],low(x,u));} else {vEB_TREE_INSERT(V->cluster[high(x,u)],low(x,u),u);}} //第三种情况if(x>V->max) {V->max=x;}}} //删除一个元素void vEB_TREE_DELETE(Van_Emde_Boas *V,int x,int u) {if(V->min==V->max) {V->min=NIL;V->max=NIL;} else {if(V->u==2) {if(x==0) {V->min=1;} else {V->min=0;V->max=V->min;}} else {if(x==V->min) {int first_cluster=vEB_TREE_MINIMUM(V->summary);x=index(first_cluster,vEB_TREE_MINIMUM(V->cluster[first_cluster]),u);V->min=x;vEB_TREE_DELETE(V->cluster[high(x,u)],low(x,u),u);if(vEB_TREE_MINIMUM(V->cluster[high(x,u)])==NIL) {vEB_TREE_DELETE(V->summary,high(x,u),u);if(x==V->max) {int summary_max=vEB_TREE_MAXIMUM(V->summary);if(summary_max==NIL) {V->max=V->min;} else {V->max=index(summary_max,vEB_TREE_MAXIMUM(V->cluster[summary_max]),u);}}} else {if(x==V->max) {V->max=index(high(x,u),vEB_TREE_MAXIMUM(V->cluster[high(x,u)]),u);}}}}}}//测试函数 void vEB_TREE_INSERT(Van_Emde_Boas *V,int u){int x;int a[]={2,3,4,5,7,14,15};vEB_TREE_CREATE(V,u);for(int i=0;i<7;i++){vEB_TREE_INSERT(V,a[i],u);}cout<<"请输入你要查询的数据:";cin>>x; if(vEB_TREE_MEMBER(V,x,u)){cout<<"该数据存在VEB树中"<<endl; } else {cout<<"该数据不存在VEB树中"<<endl; }cout<<"请输入你要删除的数据:";cin>>x; vEB_TREE_DELETE(V,x,u);cout<<"请输入你要查询的数据:";cin>>x; if(vEB_TREE_MEMBER(V,x,u)){cout<<"该数据存在VEB树中"<<endl; } else {cout<<"该数据不存在VEB树中"<<endl; }} int main() {int u;cin>>u;Van_Emde_Boas *V=new Van_Emde_Boas;vEB_TREE_INSERT(V,u);return 0;}
