b-.cpp

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

			T->ptr[1]=T->ptr[2];
			T->ptr[2]=NULL;
		}
		else
		{	//若要删除的关键字在双亲节点的第三个指针上//
			T=T->parent;
			T->ptr[1]->key[2]=T->key[2];
			T->ptr[1]->Keynum++;
			T->Keynum--;
			free(T->ptr[2]);
			T->ptr[2]=NULL;
		}
		return  OK;
	}

	//******关键字的删除时需要节点变化的情况*******//
	Status  Deletenode(Result *r,Btree  &bt)
	{
		BTNode  *p,*T=r->pt; 
		if(T->parent->Keynum==2)
		{	//其双亲有三个孩子，但是要删除的关键字没有相邻兄弟的关键字多于一个；
			return DeleteThreeChild(T);
		}
		else
		{	//此时节点和兄弟及双亲都只有一个关键字//
			//首先把最低层节点变化如下//
			if(T==T->parent->ptr[0])
			{
				T=T->parent;
				p=T->ptr[1];
				T->key[2]=p->key[1];
				T->Keynum++;
				free(T->ptr[0]);
				free(T->ptr[1]);
				T->ptr[0]=NULL;
				T->ptr[1]=NULL;
				T->ptr[2]=NULL;
			}
			else 
			{
				T=T->parent;
				p=T->ptr[0];
				T->key[2]=T->key[1];
				T->key[1]=p->key[1];
				T->Keynum++;
				free(T->ptr[0]);
				free(T->ptr[1]);
				T->ptr[0]=NULL;
				T->ptr[1]=NULL;
				T->ptr[2]=NULL;
			}
		}

		while(T->parent && T->parent->Keynum==1)
		{	//节点的双亲和兄弟节点都只有一个关键字//
			//***********进入以下循环*************//
			if(T==T->parent->ptr[0])
			{	//要求兄弟节点的关键字数目为1//
				if(T->parent->ptr[1]->Keynum==1)
				{
					T=T->parent;
					p=T->ptr[1];
					T->key[2]=p->key[1];
					T->Keynum++;
					T->ptr[1]=p->ptr[0];
					T->ptr[1]->parent=T;
					T->ptr[2]=p->ptr[1];
					T->ptr[2]->parent=T;
				}
				else
					break;
			}
			else 
			{
				if(T->parent->ptr[0]->Keynum==1)
				{
					T=T->parent;
					p=T->ptr[0];
					T->key[2]=T->key[1];
					T->key[1]=p->key[1];
					T->Keynum++;
					T->ptr[2]=T->ptr[1];
					T->ptr[0]=p->ptr[0];
					T->ptr[0]->parent=T;
					T->ptr[1]=p->ptr[1];
					T->ptr[1]->parent=T;
				}
				else
					break;
			}
		}

		if(!T->parent)//双亲节点不存在
		{
			return  OK;
		}
		else if(T->parent && T->parent->Keynum!=1)//双亲节点的关键字多于一个//
		{
			if(T==T->parent->ptr[0])//要变化的节点为双亲的第一个孩子//
			{
				if(T->parent->ptr[1]->Keynum==1)//相邻的兄弟节点的关键字为一个//
				{
					T=T->parent;	
					T->ptr[1]->ptr[2]=T->ptr[1]->ptr[1];
					T->ptr[1]->ptr[1]=T->ptr[1]->ptr[0];
					T->ptr[1]->ptr[0]=T->ptr[0];
					T->ptr[1]->ptr[0]->parent=T->ptr[1];
					T->ptr[0]=T->ptr[1];
					T->ptr[1]=T->ptr[2];
					T->ptr[2]=NULL;
					T->ptr[0]->key[2]=T->ptr[0]->key[1];	
					T->ptr[0]->key[1]=T->key[1];
					T->key[1]=T->key[2];
					T->ptr[0]->Keynum++;
					T->Keynum--;
				}
				else
				{	//相邻的兄弟节点的关键字多于一个//
					p=Buildnode(T->parent->key[1]);
					T->parent->ptr[0]=p;
					p->parent=T->parent;
					p->ptr[0]=T;
					T->parent=p;
					p->ptr[1]=p->parent->ptr[1]->ptr[0];
					p->ptr[1]->parent=p;
					p=p->parent;
					p->key[1]=p->ptr[1]->key[1];
					p=p->ptr[1];
					p->key[1]=p->key[2];
					p->key[2]=0;
					p->Keynum--;
					p->ptr[0]=p->ptr[1];
					p->ptr[1]=p->ptr[2];
					p->ptr[2]=NULL;

				}
			}
			else if(T==T->parent->ptr[1])//要变化的节点为双亲的第二孩子//
			{
				if(T->parent->ptr[0]->Keynum==1 && T->parent->ptr[2]->Keynum==1)
				{
					T=T->parent;
					T->ptr[0]->ptr[2]=T->ptr[1];
					T->ptr[0]->ptr[2]->parent=T->ptr[0];
					T->ptr[0]->key[2]=T->key[1];
					T->key[1]=T->key[2];
					T->Keynum--;
					T->ptr[0]->Keynum++;
					T->ptr[1]=T->ptr[2];
					T->ptr[2]=NULL;
				}
				else if(T->parent->ptr[0]->Keynum!=1)
				{
					p=Buildnode(T->parent->key[1]);
					T->parent->ptr[1]=p;
					p->parent=T->parent;
					p->ptr[1]=T;
					T->parent=p;
					p->ptr[0]=p->parent->ptr[0]->ptr[2];
					p->ptr[0]->parent=p;
					p=p->parent;
					p->key[1]=p->ptr[0]->key[2];
					p=p->ptr[0];
					p->key[2]=0;
					p->Keynum--;
					p->ptr[2]=NULL;
				}
				else
				{
					p=Buildnode(T->parent->key[2]);
					T->parent->ptr[1]=p;
					p->parent=T->parent;
					p->ptr[0]=T;
					T->parent=p;
					p->ptr[1]=p->parent->ptr[2]->ptr[0];
					p->ptr[1]->parent=p;
					p=p->parent;
					p->key[2]=p->ptr[2]->key[1];
					p=p->ptr[2];
					p->key[1]=p->key[2];
					p->key[2]=0;
					p->Keynum--;
					p->ptr[0]=p->ptr[1];
					p->ptr[1]=p->ptr[2];
					p->ptr[2]=NULL;
				}
			}
			else //要变化的节点为双亲的第三个孩子//
			{
				if(T->parent->ptr[1]->Keynum==1)
				{
					T=T->parent;
					T->ptr[1]->ptr[2]=T->ptr[2];
					T->ptr[1]->ptr[2]->parent=T->ptr[1];
					T->ptr[1]->key[2]=T->key[2];
					T->key[2]=0;
					T->Keynum--;
					T->ptr[1]->Keynum++;
					T->ptr[2]=NULL;
				}
				else
				{
					p=Buildnode(T->parent->key[2]);
					T->parent->ptr[2]=p;
					p->parent=T->parent;
					p->ptr[1]=T;
					T->parent=p;
					p->ptr[0]=p->parent->ptr[1]->ptr[2];
					p->ptr[1]->parent=p;
					p=p->parent;
					p->key[2]=p->ptr[1]->key[2];
					p=p->ptr[1];
					p->key[2]=0;
					p->Keynum--;
					p->ptr[2]=NULL;
				}
			}
		}
		else
		{//双亲节点的其他孩子关键字多于一个，但是双亲的关键字只有一个//
			if(T==T->parent->ptr[0])
			{
				p=Buildnode(T->parent->ptr[1]->key[1]);
				p->parent=T->parent->parent;
				
				if(p->parent)
				{
					for(int i=0;i<=M;i++)
						if(p->parent->ptr[i]==T->parent)
						{
							p->parent->ptr[i]=p;
							break;
						}
				}
				else
					bt=p;
				p->ptr[0]=T->parent;
				p->ptr[0]->parent=p;
				p->ptr[1]=T->parent->ptr[1];
				p->ptr[1]->parent=p;
				p->ptr[1]->key[1]=p->ptr[1]->key[2];
				p->ptr[1]->key[2]=0;
				p->ptr[1]->Keynum--;
				p->ptr[0]->ptr[1]=p->ptr[1]->ptr[0];
				p->ptr[0]->ptr[1]->parent=p->ptr[0];
				p->ptr[1]->ptr[0]=p->ptr[1]->ptr[1];	
				p->ptr[1]->ptr[1]=p->ptr[1]->ptr[2];
				p->ptr[1]->ptr[2]=NULL;
			}
			else if(T==T->parent->ptr[1] && T->parent->ptr[0]->Keynum!=1)
			{
				p=Buildnode(T->parent->ptr[0]->key[2]);
				p->parent=T->parent->parent;
				
				if(p->parent)
				{for(int i=0;i<=M;i++)
						if(p->parent->ptr[i]==T->parent)
						{
							p->parent->ptr[i]=p;
						}
				}
				else
					bt=p;

				p->ptr[1]=T->parent;
				p->ptr[1]->parent=p;
				p->ptr[0]=T->parent->ptr[0];
				p->ptr[0]->parent=p;	
				p->ptr[0]->key[2]=0;
				p->ptr[0]->Keynum--;
				p->ptr[1]->ptr[0]=p->ptr[0]->ptr[2];
				p->ptr[1]->ptr[0]->parent=p->ptr[1];
				p->ptr[0]->ptr[2]=NULL;
			}
		}

		return  OK;
	}

	//***删除叶子节点上的一个关键字***//
	Status   Deletekey(Result *r1,Btree &T)
	{
		Result *r2;
		if(r1->pt->Keynum>1)//如果节点上有不止一个关键字；
		{
			r1->pt->Keynum--;
			if(r1->order==1)
			{	
				r1->pt->key[1]=r1->pt->key[2];
				r1->pt->key[2]=0;
			}				
			else
				r1->pt->key[2]=0;
			return   OK;
		}
		else
		{
			if(r1->pt->parent)
			{
				r2=BrotherFind(r1);
				if(r2->tag)//其某一个相邻兄弟节点上有不止一个关键字//
					return	DeleteBrother(r1,r2);
				else//其所有相邻兄弟节点上都只有一个关键字//
					return  Deletenode(r1,T);
			}
			else
			{
				free(T);
				T=NULL;
				return OK;
			}
		}
	}

	//***在一棵B-树中删除一个关键字***//
	void DeleteBTNode(Btree &T,KeyType  Key)
	{
		BTNode  *p;
		Result  *r;
		
		r=SearchKey(T,Key);
		if(r->tag)//该关键字找到了；
		{
			if(JudgeLeaf(r->pt))//节点是叶子节点//
			{
				if(Deletekey(r,T))
					cout<<"关键字"<<Key<<"的删除完成!"<<endl;
			}
			else//关键字所在节点为非叶子节点//
			{
				p=r->pt;
				r=leftFind(r);
				p->key[r->order]=r->pt->key[1];
				r->pt->key[1]=Key;
				r->order=1;
				if(Deletekey(r,T))
					cout<<"关键字"<<Key<<"的删除完成!"<<endl;
			}
		}
		else
		{
			cout<<"树中没有这个关键字!"<<endl;
		}

	}

	//***输出B-树的所有节点****//
	void  Output(Btree T)
	{
		int i,j=0,k,t=0,m=0;
		BTNode *p;
		LinkQueue Q[2];
		InitQueue(Q[0]);
		InitQueue(Q[1]);
		InQueue(Q[0],T);//两个队列，每次将一层全部放进一个队列中
		T->location=30;
		while(Q[j].base!=Q[j].top)
		{
			k=(j+3)%2;
			p=*Q[j].top;
			for(i=0;i<=M;i++)
			{
				if(Q[k].base-Q[k].top==Q[k].queuesize )
					IncreQueue(Q[k]);
				if(p->ptr[i])
					InQueue(Q[k],p->ptr[i]);//进队//
			}
			for(i=0;i<=M;i++)
				if(p->parent  && p==p->parent->ptr[i])
				{
					if(i==1 && !p->parent->ptr[2])
						p->location=p->parent->location+(20-m);
					else
						p->location=p->parent->location+(20-m)*(i-1);
				}

			for(;t<p->location;t++)//输出之前的空格//
				cout<<" ";
			cout<<'|';//每个节点之间进行区分的标记//
			t++;
			i=1;
			while(i<=p->Keynum)
			{
				cout<<p->key[i];
				i++;
				t++;
				if(i<=p->Keynum)
					{
						cout<<"  ";//输出一个节点的所有关键字//
						t++;
					}
			}
			cout<<'|';
			t++;
			OutQueue(Q[j]);
			if(Q[j].base==Q[j].top)
			{
				j=(j+3)%2;
				cout<<endl<<endl;
				t=0;
				m+=5;
			}
		}
		DestroyQueue(Q[0]);
		DestroyQueue(Q[1]);
	}

	//***将树写入到文件中***//
	Status  WriteTree(Btree T)
	{
		int i;
		BTNode* p;
		LinkQueue Q;
		InitQueue(Q);
		fstream    Outfile("info of bree.dat",ios::out|ios::binary);
		if(Outfile.fail())
		{
			cout<<"文件打开失败!"<<endl;
			return  ERROR;
		}
		InQueue(Q,T);
		while(Q.base!=Q.top)
		{
			p=*Q.top;
			for(i=0;i<=M;i++)//将每一个节点的孩子全部进入队列之后，在将节点写入到文件中//
			{
				if(Q.base-Q.top==Q.queuesize )
					IncreQueue(Q);
				if(p->ptr[i])
					InQueue(Q,p->ptr[i]);
			}
			Outfile.write((char*)p,sizeof(BTNode));
			OutQueue(Q);
		}
		Outfile.close();
		return  OK;
	}
	
    //***从文件中读出信息恢复成一棵B-树***//
	Btree  ReadTree()
	{
		int i,j=0,k;
		BTNode *p,*q=NULL,*T=NULL;
		LinkQueue Q[2];
		InitQueue(Q[0]);
		InitQueue(Q[1]);//两个队列，没个队列依次存储一层的所有节点//
		fstream    Infile("info of bree.dat",ios::in|ios::binary);
		if(Infile.fail())
		{
			cout<<"文件打开失败!"<<endl;
			return  NULL;
		}
		
		T=(BTNode *)malloc(sizeof(BTNode));
		Infile.read((char*)T,sizeof(BTNode));
		InQueue(Q[0],T);
		T->parent=NULL;//将树的第一个节点制成一棵树//
		
		while(Q[j].base!=Q[j].top)
		{
			k=(j+3)%2;
		
			while(Q[j].top!=Q[j].base)
			{
				p=*Q[j].top;
				for(i=0;i<=M;i++)
				{
					if(p->ptr[i])//将每一个节点的孩子全部进队之后，再出队//
					{
						q=(BTNode *)malloc(sizeof(BTNode));
						Infile.read((char*)q,sizeof(BTNode));
						if(Q[k].base-Q[k].top==Q[k].queuesize)
							IncreQueue(Q[k]);
						InQueue(Q[k],q);
						p->ptr[i]=q;
						q->parent=p;
					}
					else
						break;
				}
				OutQueue(Q[j]);
			}
			if(Q[j].base==Q[j].top)
				j=(j+3)%2;
		}

		DestroyQueue(Q[0]);
		DestroyQueue(Q[1]);
		Infile.close();
		return  T;
	}

	//************主********************函*******************数***********//
	void main()
	{
		Btree  T;
		KeyType  Key;
		Result *r;
		int i;
		
		/*if(InitBtree(T))
			cout<<"Initialing succeeded!"<<endl;
		Output(T);	
		if(WriteTree(T))
			cout<<"B-树已经写到了文件中"<<endl;*/
	  
		T=ReadTree();
		Output(T);
		cout<<"请选择要执行的操作:";
		cout<<"1:插入     2:删除     3:退出;(其他选择亦退出)";
		cin>>i;
		while(i==1 || i==2)
		{
			if(i==1)
			{	//插入关键字//
				cout<<endl<<"给出你想要插入的关键字:";
				cin>>Key;
				r=SearchKey(T,Key);
				if(r->tag)
					cout<<"此关键字在树中已经存在,请按提示重新操作!"<<endl;
				else
				{
					T=InsertBTNode(T,Key);
					cout<<"关键字"<<Key<<"的插入完成"<<endl;
					Output(T);
				}
			}
			else
			{	//删除关键字//
				cout<<endl<<"给出你想要删除的关键字:";
				cin>>Key;
				r=SearchKey(T,Key);
				if(!r->tag)
					cout<<"此关键字在树中不存在,请按提示重新操作!"<<endl;
				else
				{
					DeleteBTNode(T,Key);
					if(T)
						Output(T);
				}
			}

			cout<<"请选择要执行的操作:";//循环操作//
			cout<<"1:插入     2:删除     3:退出;(其他选择亦退出)";
			cin>>i;
		}
		if(WriteTree(T))
			cout<<"树已经写到文件中!"<<endl;
		DestroyBtree(T);
		cout<<"B-树已经被删除!"<<endl;
	}