b-.cpp

三阶B-树的节点插入与删除 三阶B-树的节点插入与删除

	//************************************
    //学号    :    040630223
	//姓名    :    周福平
	//题目    :    B-树
	//指导老师:    高航
	//日期    :    2007.12.16
	//************************************

	#include  "iostream.h"	
	#include  "stdlib.h"
	#include  "fstream.h"
	#define   KeyType     int
	#define   M		2
	#define   OK	1
	#define   ERROR 0
	#define  QUEUE_INIT_SIZE    100
    #define  QUEUEINCREMENT     10
    typedef   int   Status;
	
	/******定义B-树节点结构体*******/
	typedef   struct  BTNode{
		int				Keynum;		 //节点包含的关键字的个数；
		struct  BTNode	*parent;	 //节点的双亲节点；
		KeyType			key[M+1];	 //关键字的值；
		struct  BTNode  *ptr[M+1];   //子树指针；
		int             location;
	}BTNode,*Btree;

	/********定义查找节点的结果的结构体*******/
	typedef    struct  Result{
		BTNode  *pt;//目标节点指针；
		int     order;  //关键字在目标节点中的序号(1-M);
		int     tag;//查找的结果(1为存在，0为不存在);
	}Result;

	/********队列操作的结构体*******/
	typedef   struct  LinkQueue{
		BTNode  **base;
		BTNode  **top;
		int  queuesize;
	}LinkQueue;
	
	//**********************************************************************//
	//*********************队列的基本操(用于树的输出)***********************//

	//队列的初始化:申请空间
	void InitQueue( LinkQueue &Q)
	{
		int item;
		item=QUEUE_INIT_SIZE*sizeof(BTNode*);
		Q.top=(BTNode**)malloc(item);
		if(!Q.top)//申请不成功,需要结束程序;
		{
			cout<<endl<<"空间申请失败!";
			exit(0);
		}
		Q.base=Q.top;
		Q.queuesize=QUEUE_INIT_SIZE;
	}
	
	//元素进队;
	void InQueue(LinkQueue &Q,BTNode *p)
	{
		*Q.base=p;
		Q.base++;
	}

	//元素出队；
	void OutQueue(LinkQueue &Q)
	{
		BTNode  **p=Q.top;	
		Q.base--;
		while(p!=Q.base)   //出队的时候所有的元素都向前移动一位；
		{
			*p=*(p+1);        //这样操作很简单，但是效率很低；
			p++;
		}
	}	
	
	//增加队列的长度;
	void IncreQueue(LinkQueue &Q)
	{
		int size;
		BTNode **p,**q,**r;
		Q.queuesize=Q.queuesize+QUEUEINCREMENT;
		size=Q.queuesize*sizeof(BTNode*);//申请新的空间;
		p=(BTNode**)malloc(size);//把队列的两个指针分别都指到新的空间上来;
		q=p;
		r=Q.top;
		while(r!=Q.base)
		{
			*p=*r;    //将原队列中的元素全部都复制到新的队列中间来;
			p++;
			r++;
		}
		Q.top=q;
		Q.base=(p+1);
	
		cout<<endl<<"队列的长度已经增加!";
	}

	//队列的删除;
	void  DestroyQueue(LinkQueue &Q)  
	{
		free(Q.top);
	}
	
	//*********************队列的基本操(用于树的输出)***********************//
	//**********************************************************************//

	//**在一棵B-树中判断某指针所指的节点是否为叶子节点**//
	Status   JudgeLeaf(BTNode *T)
	{
		int  i;
		if(T)
		{
			for(i=0;i<=M;i++)
				if(T->ptr[i])
					break;
			//该节点所有的孩子指针都为空；
			if(i==(M+1))
				return  OK;
			else
				return  ERROR;
		}
		return ERROR;
	}

	//***初始化一个节点，里面只有一个关键字***//
	Btree  Buildnode(KeyType Key)
	{
		int i;
		Btree T;
		T=(Btree)malloc(sizeof(BTNode));
		T->Keynum=1;
		T->key[1]=Key;
		T->key[2]=0;
		for(i=0;i<=M;i++)
			T->ptr[i]=NULL;
		T->parent=NULL;
		T->location=0;
		return  T;
	}

	//****将两棵B-树合成一棵****//
	Btree   Together(Btree p,Btree q)
	{
		BTNode   *T,*r;
		if(p->key[1]>q->key[2])
		{//新加入的关键字在一个节点的三个关键字中最大的情况；
			T=Buildnode(q->key[2]);
			T->ptr[0]=q;
			q->parent=T;
			T->ptr[1]=p;
			p->parent=T;
			q->key[2]=0;
			q->Keynum--;
			q->ptr[2]=NULL;
			
		}
		else if(p->key[1]<q->key[1])
		{//新加入的关键字在一个节点的三个关键字中最小的情况；
			T=Buildnode(q->key[1]);
			T->ptr[0]=p;
			p->parent=T;
			T->ptr[1]=q;
			q->parent=T;
			q->key[1]=q->key[2];
			q->key[2]=0;
			q->Keynum--;
			q->ptr[0]=q->ptr[1];
			if(q->ptr[0])
				q->ptr[0]->parent=q;
			q->ptr[1]=q->ptr[2];
			if(q->ptr[1])
				q->ptr[1]->parent=q;
			q->ptr[2]=NULL;
		}
		else//新加入的关键字在一个节点的三个关键字中居中的情况；
		{
			T=Buildnode(p->key[1]);
			T->ptr[0]=q;
			q->parent=T;
			T->ptr[1]=p;	
			p->parent=T;
			r=p->ptr[0];
			p->key[1]=q->key[2];	
			p->ptr[0]=p->ptr[1];
			if(p->ptr[0])
				p->ptr[0]->parent=p;
			p->ptr[1]=q->ptr[2];
			if(p->ptr[1])
				p->ptr[1]->parent=p;
			q->key[2]=0;
			q->Keynum--;
			q->ptr[1]=r;
			if(q->ptr[1])
				q->ptr[1]->parent=q;
			q->ptr[2]=NULL;
		
		}
		return   T;
	}

	//**在一棵B-树中找到应该插入某关键字的节点(用于插入关键字)**//
	Result*  SearchBnode(Btree  T,KeyType  Key)
	{
		Result *r;	
		r=(Result *)malloc(sizeof(Result));
		while(!JudgeLeaf(T))//找到合适的叶子节点；
		{
			if(T->Keynum==1)
			{
				if(Key<T->key[1])
					T=T->ptr[0];
				else
					T=T->ptr[1];
			}
			else  if(T->Keynum==2)
			{
				if(Key<T->key[1])
					T=T->ptr[0];
				else if(Key<T->key[2])
					T=T->ptr[1];
				else
					T=T->ptr[2];
			}
		}
		if(T)//找到应该插入的节点，记录插入信息//
		{
			r->pt=T;
			if(T->key[1]>Key)
				r->order=1;
			else if(T->Keynum==1 && T->key[1]<Key)
				r->order=2;
			else if(T->Keynum>1 && T->key[2]<Key)
				r->order=3;
			else
				r->order=2;
			r->tag=1;
			return  r;
		}
        else//树为空树//
		{
			r->tag=0;
			return r;
		}
	}
	
	//***寻找一个关键字，用于删除；***//
	Result *SearchKey(Btree T,KeyType  Key)
	{
		Result  *r;
		r=(Result *)malloc(sizeof(Result));
		while(T)//找到合适的叶子节点；
		{
			if(T->Keynum==1)//节点只有一个关键字，有三种情况//
			{
				if(Key<T->key[1])
					T=T->ptr[0];
				else if(Key==T->key[1])	
				{
					r->pt=T;                                                       //此函数已经改变，注意以前有无使用；
					r->order=1;
					r->tag=1;
					return   r;
				}
				else	
					T=T->ptr[1];
			
			}
			else  if(T->Keynum==2)//节点有两个关键字，有五种情况；
			{
				if(Key<T->key[1])
					T=T->ptr[0];
				else if(Key==T->key[1])
				{
					r->pt=T;
					r->order=1;
					r->tag=1;
					return   r;
				}
				else if(Key<T->key[2])
					T=T->ptr[1];
				else if(Key==T->key[2])
				{
					r->pt=T;
					r->order=2;
					r->tag=1;
					return   r;
				}
				else
					T=T->ptr[2];
			}
		}
        r->tag=0;//没有找到，返回0//
		return  r;
	}

	//***节点的关键字只有一个还可以直接插入一个***//
	void  InsertKey(BTNode *T,KeyType Key)
	{
		T->Keynum++;
		if(Key>T->key[1])
			T->key[2]=Key;
		else
		{
			T->key[2]=T->key[1];
			T->key[1]=Key;
		}
	}

	//***向B-树中插入一个关键字***//
	Btree  InsertBTNode(Btree T,KeyType Key)
	{	
		Btree p,q;
		Result *r;
		
		if(T)
		{
			r=SearchBnode(T,Key);//寻找关键字应该插入的叶子节点//
			if(r->pt->Keynum<M)//节点的关键字还没有装满，可以继续装//
			{
				InsertKey(r->pt,Key);//直接装进节点中//
				return  T;
			}
			else//节点已经装不下了，要将节点裂开//
			{	
				p=Buildnode(Key);//申请一个节点//
				while(r->pt && r->pt->Keynum==M)//在没有碰到可以直接装的节点之前，要一直裂开//
				{
					q=r->pt;
					r->pt=q->parent;
					p=Together(p,q);//裂开时进行两棵树的合并//
				}
				if(r->pt)//如果合并没有进行到树的顶端//
				{   //调节各路指针//
					if(p->key[1]<r->pt->key[1])
					{
						r->pt->ptr[2]=r->pt->ptr[1];
						if(r->pt->ptr[2])
							r->pt->ptr[2]->parent=r->pt;
						r->pt->ptr[1]=p->ptr[1];
						if(r->pt->ptr[1])
							r->pt->ptr[1]->parent=r->pt;
						r->pt->key[2]=r->pt->key[1];
						r->pt->key[1]=p->key[1];
						r->pt->ptr[0]=p->ptr[0];
						if(r->pt->ptr[0])
							r->pt->ptr[0]->parent=r->pt;
						r->pt->Keynum++;
						free(p);									
					}
					else
					{
						r->pt->ptr[2]=p->ptr[1];
						if(r->pt->ptr[2])
							r->pt->ptr[2]->parent=r->pt;
						r->pt->ptr[1]=p->ptr[0];
						if(r->pt->ptr[1])
							r->pt->ptr[1]->parent=r->pt;
						r->pt->key[2]=p->key[1];
						r->pt->Keynum++;
						free(p);
					}
					return  T;
				}
				else//合并已经到达顶端，树的顶点已经变化//
				{
					p->parent=NULL;
					return  p;
				}
			}
		}
		else
		{
			T=Buildnode(Key);
			return  T;
		}
	}

	//*****利用给出的信息初始化一棵B-树***********//
	Status   InitBtree(	Btree  &T)
	{
		int   i,n;
		KeyType  Key;
		Result *r;
		cout<<"初始化的树中的关键字的个数为：";
		cin>>n;
        cout<<"请给出一个关键字:";
		cin>>Key;
		T=Buildnode(Key);//先建立一棵只有一个节点的树//
		
		for(i=1;i<n;i++)
		{
			cout<<"请给出一个关键字:";
			cin>>Key;
			r=SearchKey(T,Key);//判断这个关键字树中是否已经存在//
			if(r->tag)
			{
				cout<<"此关键字在树中已经存在,请重新输入!";
				i--;
				continue;
			}
			T=InsertBTNode(T,Key);//其余的关键字往其中插入即可//
		}
		if(T)
			return  OK;
		else 
			return  ERROR;
	}

	//***************销毁一棵B-树***********************//
	void   DestroyBtree(Btree T)
	{
		Btree   p,q,r;

		if(T)    
		{	//在节点存在时，就执行此操作//
			p=T->ptr[0];
			q=T->ptr[1];
			r=T->ptr[2];
			free(T);
			DestroyBtree(p);
			DestroyBtree(q);
			DestroyBtree(r);
		}
		//**省略的else语句**作为结束条件//
	}

	//***寻找一个非叶子节点中的关键字的右边的最左边关键字***//
	Result  * leftFind(Result *r)
	{
		if(!JudgeLeaf(r->pt))
			r->pt=r->pt->ptr[r->order];
		while(!JudgeLeaf(r->pt))
			r->pt=r->pt->ptr[0];
		return  r;
	}

	
	//***判断一个节点上的相邻兄弟节点的关键字是否都为一个***//
	Result*   BrotherFind(Result *r1)
	{
		Result *r2;
		r2=(Result *)malloc(sizeof(Result));//申请返回信息的节点空间//
		if(r1->pt==r1->pt->parent->ptr[0])//若需要删除的关键字在双亲的第一个指针上//
		{	
			if(r1->pt->parent->ptr[1]->Keynum>1)//只需要看第二个指针就可以了//
			{
				r2->pt=r1->pt->parent->ptr[1];
				r2->order=1;//第二个指针上有多个关键字；
				r2->tag=1;
				return r2;
			}

		}
		else  if(r1->pt==r1->pt->parent->ptr[1])//若需要删除的关键字在双亲的第二个指针上//
		{
			if(r1->pt->parent->ptr[0]->Keynum>1)//需要同时看第一个和第三个指针//
			{
				r2->pt=r1->pt->parent->ptr[0];//都满足时，先看第一个指针//
				r2->order=2;
				r2->tag=1;
				return r2;
			}
			else if(r1->pt->parent->ptr[2])//看第三个指针//
				if(r1->pt->parent->ptr[2]->Keynum>1)
				{
					r2->pt=r1->pt->parent->ptr[2];
					r2->order=1;
					r2->tag=1;
					return r2;
				}

		}
		else if(r1->pt==r1->pt->parent->ptr[2])//若需要删除的关键字在双亲的第三个指针上//
		{
			if(r1->pt->parent->ptr[1]->Keynum>1)//只需要看第二个指针就可以了//
			{
				r2->pt=r1->pt->parent->ptr[1];
				r2->order=2;
				r2->tag=1;
				return r2;
			}
		}
		r2->tag=0;//没有找到的时候返回0//
		return  r2;
	}

	//*******在树中找到了满足的兄弟节点*******//
	Status     DeleteBrother(Result *r1,Result *r2)
	{
		BTNode *T1=r1->pt,*T2=r2->pt;
		if(T1==T1->parent->ptr[0])
			{	//若要删除的关键字在双亲的第一个指针上//
				T1->key[1]=T1->parent->key[1];
				T1->parent->key[1]=T2->key[1];
				T2->key[1]=T2->key[2];
				T2->key[2]=0;
				T2->Keynum--;
			}								
			else if(T1==T1->parent->ptr[1])
			{	//若要删除的关键字在第二个指针上//
				if(r2->order==1)
				{
					T1->key[1]=T1->parent->key[2];
					T1->parent->key[2]=T2->key[1];
					T2->key[1]=T2->key[2];
					T2->Keynum--;
				}
				else
				{
					T1->key[1]=T1->parent->key[1];
					T1->parent->key[1]=T2->key[2];
					T2->Keynum--;
				}
			}
			else
			{	//要删除的关键字在双亲的第三个指针上//
				T1->key[1]=T1->parent->key[2];
				T1->parent->key[2]=T2->key[2];
				T2->Keynum--;
			}
			return   OK;
	}

	//******其双亲有三个孩子，但是要删除的关******//
	//******键字没有相邻兄弟的关键字多于一个******//
	Status   DeleteThreeChild(BTNode *T)
	{
		if(T==T->parent->ptr[0])
		{	//若要删除的关键字在双亲节点的第一个指针上；
			T=T->parent;
			T->ptr[0]->key[1]=T->key[1];
			T->ptr[0]->key[2]=T->ptr[1]->key[1];
			T->key[1]=T->key[2];
			T->key[2]=0;
			T->Keynum--;				
			T->ptr[0]->Keynum++;
			free(T->ptr[1]);
			T->ptr[1]=T->ptr[2];
			T->ptr[2]=NULL;
		}
		else if(T==T->parent->ptr[1])
		{	//若要删除的关键字在双亲节点的第二个指针上//	
			T=T->parent;
			T->ptr[0]->key[2]=T->key[1];
			T->ptr[0]->Keynum++;
			T->key[1]=T->key[2];
			T->key[2]=0;
			T->Keynum--;
			free(T->ptr[1]);