bptree.h

our homework big project

	if(Isroot(m_nodeposition)==1)								//根结点情况
	{
		if(Isleaf(m_nodeposition)==1)							//叶节点
		{
			if(m_nodeposition->no>1)							//多个数据
			{
				for(;i<m_nodeposition->no-1;i++)
				{
					m_nodeposition->key[i]=m_nodeposition->key[i+1];
					m_nodeposition->p_leaf_next[i]=m_nodeposition->p_leaf_next[i+1];
				}
				m_nodeposition->key[i]=NULL;
				m_nodeposition->p_leaf_next[i]=NULL;
				m_nodeposition->no--;
				m_total--;
			}
			else												//只有一个数据，直接删除
			{
				m_total=0;
				m_nodeposition->no=0;
				m_nodeposition->key[0]=NULL;
				m_nodeposition->p_leaf_next[0]=NULL;
			}
		}
		else													//非叶节点
		{
			if(m_nodeposition->no>2)							//多个数据
			{
				for(;i<m_nodeposition->no-1;i++)
				{
					m_nodeposition->key[i]=m_nodeposition->key[i+1];
					m_nodeposition->p_node_next[i]=m_nodeposition->p_node_next[i+1];
				}
				m_nodeposition->key[i]=NULL;
				m_nodeposition->p_node_next[i]=NULL;
				m_nodeposition->no--;
			}
			else												//只剩两个数据时
			{
				m_noderoot=m_noderoot->p_node_next[0];
				delete m_noderoot->p_fathernode;
				m_noderoot->p_fathernode=NULL;
			}
		}
	}
	else														//非根结点
	{
		if(Isleaf(m_nodeposition)==1)							//叶节点
		{
			for(;i<m_nodeposition->no-1;i++)
			{
				m_nodeposition->key[i]=m_nodeposition->key[i+1];
				m_nodeposition->p_leaf_next[i]=m_nodeposition->p_leaf_next[i+1];
			}
			m_nodeposition->key[i]=NULL;
			m_nodeposition->p_leaf_next[i]=NULL;
			m_total--;
		}
		else													//非叶节点
		{
			for(;i<m_nodeposition->no-1;i++)
			{
				m_nodeposition->key[i]=m_nodeposition->key[i+1];
				m_nodeposition->p_node_next[i]=m_nodeposition->p_node_next[i+1];
			}
			m_nodeposition->key[i]=NULL;
			m_nodeposition->p_node_next[i]=NULL;
		}
		m_nodeposition->no--;
		node* tp=m_nodeposition->p_fathernode;
		for(;Isroot(tp)==0;)
		{
			for(int j=0;j<tp->no;j++)
			{
				if(compare(k,tp->key[j])==0)
					tp->key[j]=t;
			}
			tp=tp->p_fathernode;
		}
		for(int j=0;j<tp->no;j++)
		{
			if(compare(k,tp->key[j])==0)
				tp->key[j]=t;
		}
	
		if(m_nodeposition->no<N/2)									//需要调整的
		{
			Merge();
		}
	}

}			

//－－－－－－－－－－－－－－－合并节点－－－－－－－－－－－－－－－－

template<class T>
void Node<T>::Merge()
{	
	node* brother=m_nodeposition->brother;
	int i;

	
	if(brother->no<=N/2+1)											//两节点可以合并的说
	{
		if(m_nodeposition->p_next!=NULL)							//不是最右边的节点
		{
			node* t=m_nodeposition;

			//合并

			for(i=m_nodeposition->no;i<m_nodeposition->no+brother->no;i++)
			{
				m_nodeposition->key[i]=brother->key[i-m_nodeposition->no];
				if(Isleaf(m_nodeposition)==1)						//叶节点的赋值
					m_nodeposition->p_leaf_next[i]=brother->p_leaf_next[i-m_nodeposition->no];
				else												//非叶节点的赋值
				{
					m_nodeposition->p_node_next[i]=brother->p_node_next[i-m_nodeposition->no];
					brother->p_node_next[i-m_nodeposition->no]->p_fathernode=m_nodeposition;
				}
			}

			//处理合并后节点的其他数值

			m_nodeposition->no+=brother->no;

			if(brother->p_next!=NULL)
			{
				if(brother->p_next->p_next!=NULL)m_nodeposition->brother=brother->brother;
				else
				{
					m_nodeposition->brother=brother->brother;
					brother->brother->brother=m_nodeposition;
				}
			}
			else
				m_nodeposition->brother=m_nodeposition->p_fathernode->p_node_next[m_nodeposition->p_fathernode->no-3];

			m_nodeposition->p_next=brother->p_next;

			//重置上级节点中的数值

			node* tp=m_nodeposition->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(m_nodeposition->key[m_nodeposition->no-brother->no-1],tp->key[j])==0)
							tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(m_nodeposition->key[m_nodeposition->no-brother->no-1],tp->key[j])==0)
						tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
			}	
			
			m_nodeposition=brother->p_fathernode;
			del(brother->key[brother->no-1],t->key[t->no-1]);		//删除被删节点在父节点中的值
			delete brother;
			brother=NULL;
		}
		else														//最右边的节点
		{
			T ko=m_nodeposition->key[m_nodeposition->no-1];
			node* t=m_nodeposition;

			//合并

			for(i=brother->no;i<brother->no+m_nodeposition->no;i++)
			{
				brother->key[i]=m_nodeposition->key[i-brother->no];
				if(Isleaf(m_nodeposition)==1)
					brother->p_leaf_next[i]=m_nodeposition->p_leaf_next[i-brother->no];
				else
				{
					brother->p_node_next[i]=m_nodeposition->p_node_next[i-brother->no];
					m_nodeposition->p_node_next[i-brother->no]->p_fathernode=brother;
				}
			}
			
			//合并后其他数据处理

			brother->no+=m_nodeposition->no;
			brother->p_next=NULL;
			brother->brother=brother->p_fathernode->p_node_next[brother->p_fathernode->no-3];

			//替换上级节点中的数据

			node* tp=brother->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(brother->key[brother->no-m_nodeposition->no-1],tp->key[j])==0)
							tp->key[j]=brother->key[brother->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(brother->key[brother->no-m_nodeposition->no-1],tp->key[j])==0)
						tp->key[j]=brother->key[brother->no-1];
			}

			m_nodeposition=m_nodeposition->p_fathernode;
			del(ko,brother->key[brother->no-1]);							//删除被删节点在父节点中的值
			delete t;
			t=NULL;
		}
	}
	else																	//两节点不可以合并的说
	{
		if(m_nodeposition->p_next!=NULL)									//不是最右边的节点
		{
			//调整两个节点的数据个数

			int w=m_nodeposition->no;
			m_nodeposition->key[w]=brother->key[0];
			if(Isleaf(m_nodeposition)==1)
				m_nodeposition->p_leaf_next[w]=brother->p_leaf_next[0];
			else
			{
				m_nodeposition->p_node_next[w]=brother->p_node_next[0];
				m_nodeposition->p_node_next[w]->p_fathernode=m_nodeposition;
			}

			m_nodeposition->no++;
			brother->no--;	

			//数据前移

			for( i=0;i<brother->no;i++)
			{
				brother->key[i]=brother->key[i+1];
				if(Isleaf(m_nodeposition)==1)
					brother->p_leaf_next[i]=brother->p_leaf_next[i+1];
				else
					brother->p_node_next[i]=brother->p_node_next[i+1];
			}

			//数据转移后空位付零

			if(Isleaf(m_nodeposition)==1)
				brother->p_leaf_next[i]=NULL;
			else
				brother->p_node_next[i]=NULL;
			brother->key[i]=NULL;
			
			//替换上级节点的值

			node* tp=m_nodeposition->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(m_nodeposition->key[m_nodeposition->no-2],tp->key[j])==0)
							tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(m_nodeposition->key[m_nodeposition->no-2],tp->key[j])==0)
						tp->key[j]=m_nodeposition->key[m_nodeposition->no-1];
			}	
			
		}
		else																		//最右边的节点
		{
			//调整数据个数
			
			for(i=m_nodeposition->no;i>0;i--)										//数据后移
			{
				m_nodeposition->key[i]=m_nodeposition->key[i-1];
				if(Isleaf(m_nodeposition)==1)
					m_nodeposition->p_leaf_next[i]=m_nodeposition->p_leaf_next[i-1];
				else
					m_nodeposition->p_node_next[i]=m_nodeposition->p_node_next[i-1];
			}
			if(Isleaf(m_nodeposition)==1)
				m_nodeposition->p_leaf_next[0]=brother->p_leaf_next[brother->no-1];
			else
			{
				m_nodeposition->p_node_next[0]=brother->p_node_next[brother->no-1];
				m_nodeposition->p_node_next[0]->p_fathernode=m_nodeposition;
			}
			m_nodeposition->key[0]=brother->key[brother->no-1];

			brother->no--;
			m_nodeposition->no++;

			//数据转移后空位付零

			if(Isleaf(m_nodeposition)==1)
				brother->p_leaf_next[brother->no]=NULL;
			else
				brother->p_node_next[brother->no]=NULL;
			brother->key[brother->no]=NULL;
			
			//重置上级结点的值

			node* tp=brother->p_fathernode;
			for(;Isroot(tp)==0;)
			{
				if(Isleaf(tp)==0)
				{
					for(int j=0;j<tp->no;j++)
					{
						if(compare(m_nodeposition->key[0],tp->key[j])==0)
							tp->key[j]=brother->key[brother->no-1];
					}
				}
				tp=tp->p_fathernode;
			}
			for(int j=0;j<tp->no;j++)
			{
				if(compare(m_nodeposition->key[0],tp->key[j])==0)
					tp->key[j]=brother->key[brother->no-1];
			}
		}
	}
}


//－－－－－－－－－－－－－－－－－－－－－－显示用－－－－－－－－－－－－－－－－

/*
template<class T>
void Node<T>::Show()
{
	node* p=m_noderoot;
	if(p!=NULL)
	{
		
		for(;Isleaf(p)==0;)
			p=p->p_node_next[0];
		int j=0;
		m_nodehead=p->p_fathernode;
		for(;;)
		{
			j=0;
			if(p!=NULL)
			{
				while(p->p_next!=NULL)
				{
					for(int i=0;i<p->no;i++)
					{
						cout<<p->key[i];
						cout<<"    ";
						j++;
					}
					p=p->p_next;
					cout<<"\n"<<"\n";
				}
				for(int i=0;i<p->no;i++)
				{
					cout<<p->key[i];
					cout<<"    ";
					j++;
				}
				cout<<"\n"<<"\n";
				cout<<j<<"\n";
				p=m_nodehead;
				cout<<"-------------------------------------"<<"\n";
			}
			if(p!=NULL)
			{
				if(p->p_fathernode!=NULL)
					m_nodehead=p->p_fathernode;
				else
					break;
			}
			if(p==NULL)break;
		}
	
	
		for(int i=0;i<p->no;i++)
		{
			cout<<p->key[i];
			cout<<"    ";
			j++;
		}
		cout<<"\n"<<"\n";
		
	}
	else
		cout<<"no data is exist";
}*/


template<class T>
void Node<T>::Index(string & indexName)				//建立索引文件
{
	
	ofstream finout(indexName.c_str(),ios::out|ios::binary);
	
	int total=0;
	size_t place=sizeof(int);
	for(m_nodehead=m_noderoot;m_nodehead->flag==0;m_nodehead=m_nodehead->p_node_next[0])
		;
	tnode indxnode;
	node* next=m_nodehead;
	finout.seekp(sizeof(int));
	for(;next!=NULL;)
	{
		indxnode.no=next->no;
		for(int i=0;i<N;i++)
		{
			indxnode.p_leaf_next[i]=next->p_leaf_next[i];
			indxnode.key[i]=next->key[i];
		}
		finout.write((char *)&indxnode,sizeof(indxnode))<<flush;
		next=next->p_next;
		total++;
	}
	finout.seekp(0);
	finout.write((char *)&total,sizeof(int))<<flush;

	finout.close();

}

	

template<class T>
void Node<T>::Buildtree(string & indexName)			//从索引文件中导出建立b＋树
{
	ifstream fin;
	fin.open(indexName.c_str(),ios::in|ios::binary);
	int total;
	int i;
	tnode indxnode;
	size_t place=0;
	fin.read((char *)&total,sizeof(int));
	if(total!=0)
	{
					
		for(i=0;i<total;i++)
		{
			fin.read((char *)&indxnode,sizeof(tnode));
			for(int j=0;j<indxnode.no;j++)
				Insert_node(indxnode.key[j],indxnode.p_leaf_next[j]);
		}
	}
}
		

#endif