mtree.h

B-树实现索引和快速查找

#include"Queue.h"
#include"SeqList.h"
const int m=7;
#include<iostream.h>
#define MAXKEY 32767
template <class Type> class Mnode {   //结点定义
	//friend class Btree<Type>;
public:
	Mnode():n(0),parent(NULL){
	for(int i=0;i<m+1;i++)
		ptr[i]=NULL;
	}//,m(msize)
	int n;                          //结点中关键码个数
    Mnode<Type> *parent;      //双亲指针
    Type key[m+1]; 
//	int index[m+1];关键码数组 0?m-1
    Mnode<Type>* ptr[m+1];  //子树指针数组 0?m
//private:
	//Mnode(int msize=3):m(msize){}
};
template <class Type> struct Triple {
	/*Triple(const Triple<Type>& t){
		r=t.r;
		i=t.i;
		tag=t.tag;
	}
	Triple(){}*/
    Mnode<Type> * r;         //结点地址指针
    int i;  int tag;                  //结点中关键码序号i
};           //tag=0,搜索成功；tag=1,搜索不成功
template <class Type> class Btree {	
//继承 m 路搜索树的所有属性和操作
public:
     int m;
     Btree():root(NULL){} 
     Btree(Type Ref):RefValue(Ref){root=new Mnode<Type>;}
     Triple<Type>& Search ( const Type & );
     int Insert ( Type& x );
     int Delete ( const Type& x );
	 void FindRange(Type min,Type max){
		 Display(root,min,max);
	 }
     int Find(const Type& x);
     friend istream& operator>>(istream& in,Btree<Type>& Tree);
     friend ostream& operator<<(ostream& out,Btree<Type>& Tree);
private:
     Type RefValue;	
	 Mnode<Type>* root;
     Queue< Mnode<Type>* > qu;  
	 SeqList<Type> seqlist;
	 void insertkey(Mnode<Type>* p,int j,Type K,Mnode<Type>* ap);
     void move(Mnode<Type>* p,Mnode<Type>* q,int s,int m);
     void merge(Mnode<Type> *p,Mnode<Type> *q,Mnode<Type> *p1,int j);
     void compress(Mnode<Type> *p,int j);
     void LeftAdjust(Mnode<Type> *p,Mnode<Type> *q,int d,int j);
     void RightAdjust(Mnode<Type> *p,Mnode<Type> *q,int d,int j);
     void Traverse(Mnode<Type> *p,ostream& out);
	 int Height(const Mnode<Type>* p){int i=0;
	 while(p!=root){p=p->parent;i++;}return i;}
	 void Display(Mnode<Type>* x,Type min,Type max);
};
template <class Type> void Btree<Type>::Display(Mnode<Type>* m,Type min,Type max){
	if(m&&m->n){
		Display(m->ptr[0],min,max);
		for(int i=0;i<m->n;i++){
		if(m->key[i+1]>=min&&m->key[i+1]<=max)cout<<m->key[i+1]<<" "; 
		Display(m->ptr[i+1],min,max);}
	}
}
				
template <class Type> Triple<Type>& Btree<Type> :: Search ( const Type & x ) {
    Triple<Type> result;int i;                    //记录搜索结果三元组
    //GetNode ( root );              读入根结点
    Mnode <Type> *p = root, *q = NULL;
    while ( p != NULL ) {       //从根开始检测
          i = 0;  p->key[(p->n)+1] = MAXKEY;
         while ( p->key[i+1] < x ) i++;   //结点内搜索
	if ( p->key[i+1] == x ) {            //搜索成功
 	   result.r = p;  
	   result.i =  i+1; 
	   result.tag = 0;
	   return result;
         } 
	q = p;  
	p = p->ptr[i];     //向下一层结点搜索
          //GetNode (p);                  //读入该结点
     }
     result.r = q;  result.i = i;  result.tag = 1;
     return result;             //搜索失败,返回插入位置
}
template<class Type> istream& operator>>(istream& in,Btree<Type>& Tree){
    Type item;
	cout<<"输入阶: ";
	in>>Tree.m;
    cout<<"构造 Btree树:\n";
    cout<<"逐个输入键值,并以 "<<Tree.RefValue<<" 结束: ";
    in>>item;
    while(item !=Tree.RefValue){
        Tree.Insert (item);
        cout<<"逐个输入键值,并以 "<<Tree.RefValue<<" 结束: ";
        in>>item;				
    }
    return in;
}
template<class Type> ostream& operator<<(ostream& out,Btree<Type>& Tree){
	out<<endl;
    out<<"层次遍历Btree.\n";
	if(Tree.root)
    Tree.Traverse(Tree.root,out);
    out<<endl;
    return out;					
}
template<class Type> void Btree<Type>::Traverse(Mnode<Type> *p,ostream& out){
//AVL树前序遍历并输出数据
	 qu.MakeEmpty();qu.EnQueue(p);
	 Mnode<Type>* q=qu.DeQueue();
	 Mnode<Type>* t;
     while(q){out<<"[";
		 for(int i=0;i<q->n;i++){
			 out<<"("<<q->key[i+1]<<","<<seqlist.Find(q->key[i+1])<<")";
			 if(i+1!=q->n)cout<<";";
			 qu.EnQueue(q->ptr[i]);
		 }out<<"]";
		 t=qu.GetFront();
		 if(t){
			 t=qu.GetFront();
			 if(Height(t)!=Height(q))
				 out<<endl;
		 }/**/
		 qu.EnQueue(q->ptr[i]);
		 q=qu.DeQueue();
	 }
}
template <class Type> void Btree<Type>::insertkey(Mnode<Type>* p,int j,Type K,Mnode<Type>* ap)
{
	p->n++;
	for(int i=p->n;i>j+1;i--){
		p->key[i]=p->key[i-1];
		p->ptr[i]=p->ptr[i-1];
	}
	p->key[j+1]=K;
	p->ptr[j+1]=ap;
}
template <class Type> void Btree<Type>::move(Mnode<Type>* p,Mnode<Type>* q,int s,int m){
 	p->n=s-1;
	q->n=m-s;
	for(int i=1;i<m-s+1;i++)
		q->key[i]=p->key[s+i];
	for(i=0;i<m-s+1;i++)
	{q->ptr[i]=p->ptr[s+i];
	if(q->ptr[i])(q->ptr[i])->parent=q;}
}
template <class Type> int Btree<Type> ::Find(const Type& x){
   Triple<Type> loc = Search (x); 
   if(!loc.tag)return seqlist.Find(x);
   else return -1;
}
template <class Type> int Btree<Type> :: Insert (  Type & x ) {
    seqlist.Insert(x);//int index=seqlist.Find(item);
    Triple<Type> loc = Search (x);   //找x的位置
    if ( !loc.tag ) return 0;                 //找到,不再插入
    Mnode<Type> *p = loc.r,  *q;    //未找到,插入
    Mnode<Type> *ap = NULL,  *t;
    Type K = x;                              
    int j = loc.i;
    while (1) {
		 if ( p->n < m-1) {                   //当前结点未满
	    insertkey ( p, j, K, ap );      //(K,ap)插入 j后
	    //PutNode (p);  
		return 1;     //写出         
		 }                                             //结点已满,分裂
         int s = (m+1)/2;                     //求 ?m/2? 
         insertkey ( p, j, K, ap );         //(K,ap)插入 j后
         q = new Mnode<Type>;      //建立新结点
         move ( p, q, s, m );                //从 p向q 搬送
	     K = p->key[s];   
		 ap = q;        //分界关键码上移
         if ( p->parent != NULL ) {   //双亲结点不是根 
 	    t = p->parent;  //GetNode (t);        //读入双亲
	    j = 0;  t->key[(t->n)+1] = MAXKEY;
	    while ( t->key[j+1] < K ) j++;//找插入点
	    q->parent = p->parent;			
 	    //PutNode (p);  PutNode (q);			
	    p = t;
         }
	else {	                                    //双亲是根
             root = new Mnode<Type>;     //创建新根
	         root->n = 1;  root->parent = NULL;	
	         root->key[1] = K;  
             root->ptr[0] = p;
             root->ptr[1] = ap;
 	    q->parent = p->parent = root;
 	    //PutNode (p);  PutNode (q);  PutNode (root);
	    return 1;
	}
    }
}
template <class Type> void Btree<Type> ::compress(Mnode<Type> *p,int j){
	for(int i=j;i<p->n;i++)
	{p->key[i]=p->key[i+1];
	p->ptr[i]=p->ptr[i+1];}
	p->n--;
}
template<class Type>void Btree<Type>::merge(Mnode<Type> *p,Mnode<Type> *q,Mnode<Type> *p1,int j)
{
	p->key[(p->n)+1]=q->key[j];
	p->ptr[(p->n)+1]=p1->ptr[0];
	if(p->ptr[(p->n)+1])
	(p->ptr[(p->n)+1])->parent=p;
	for(int i=1;i<=p1->n;i++){
		p->key[(p->n)+i+1]=p1->key[i];
		p->ptr[(p->n)+i+1]=p1->ptr[i];
		if(p->ptr[(p->n)+i+1])
			(p->ptr[(p->n)+i+1])->parent=p;
	}
	compress(q,j);
	p->n=p->n+p1->n+1;
	delete p1;
}
template <class Type> void Btree<Type>::LeftAdjust(Mnode<Type> *p,Mnode<Type> *q,int d,int j){
	Mnode<Type> *p1=q->ptr[1];
	if(p1->n>d-1){
		(p->n)++;
		p->key[p->n]=q->key[1];
		q->key[1]=p1->key[1];
		p->ptr[p->n]=p1->ptr[0];
		if(p->ptr[p->n])(p->ptr[p->n])->parent=p;
		p1->ptr[0]=p1->ptr[1];
		compress(p1,1);
	}
	else merge(p,q,p1,1);
}
template <class Type> void Btree<Type>::RightAdjust(Mnode<Type> *p,Mnode<Type> *q,int d,int j){
	Mnode<Type> *p1=q->ptr[j-1];
	if(p1->n>d-1){
		(p->n)++;
		for(int i=p->n;i>1;i--){
			p->key[i]=p->key[i-1];
			p->ptr[i]=p->ptr[i-1];
		}
		p->key[1]=q->key[j];
		q->key[j]=p1->key[p1->n];
		p->ptr[0]=p1->ptr[p1->n];
		if(p->ptr[0])(p->ptr[0])->parent=p;
		(p1->n)--;
	}
	else merge(p1,q,p,j);
}
template <class Type> int Btree<Type> :: Delete ( const Type & x ) {
    Triple<Type> loc = Search (x);    //搜索x
    if ( loc.tag ) return 0;
	seqlist.Remove(x);//未找到,不删除
    Mnode<Type> *p = loc.r, *q, *s;   //找到,删除
    int j = loc.i;
    if ( p->ptr[j] != NULL ) {                //非叶结点
       s = p->ptr[j];   
	   //GetNode (s);   
	   q = p;
       while ( s != NULL ) { q = s;  s = s->ptr[0]; }
       p->key[j] = q->key[1];    //从叶结点替补
       compress ( q, 1 );             //在叶结点删除
       p = q;                               //转化为叶结点的删除
    }
    else compress ( p, j );         //叶结点,直接删除
    int d = (m+1)/2;                 //求 ?m/2?
    while (1) {                          //调整或合并
        if ( p->n < d -1&&p!=root ) {                //小于最小限制
            j = 0;  q = p->parent;       //找到双亲
	  // GetNode (q);
	   while ( j <= q->n && q->ptr[j] != p )  j++;
	   if ( !j ) LeftAdjust ( p, q, d, j );    //调整
            else RightAdjust ( p, q, d, j );
 	   p = q;                                          //向上调整  
	   if ( p == root ) break;
        }
        else break;
    }
    if ( !root->n ) {		     //调整后根的n减到0
       p = root->ptr[0];  
	   delete root;
	   root=new Mnode<Type>;
	   root = p;   //删根
       if(root)root->parent = NULL; 
	       //新根
    }return 1;

}