btree.h

实现m阶B_树 （2）将线性表中的键值插入到B_树中（即建立索引）； （3）当删除和插入数据到线性表时

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include"stack.h"
#include"queue.h"

const int MAXKEY = 32767;//B_树的搜索函数所用的监视哨
const int Msize = 3;//默认的B_树的阶
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type> class Btree;

template<class Type>
class Mnode {//B_树结点类定义
	friend class Btree<Type>;
private:
	int n;//当前结点中关键码的个数
	Mnode<Type>* parent;//双亲结点指针
	Type data[Msize+1];//B_树结点中的关键码与其在数组中的记录号的数组，data[m]为监视哨兼工作单元，data[0].key未用
	Mnode<Type>* ptr[Msize+1];//子树结点指针数组，ptr[m]未用
	Mnode(){ n=0;parent = NULL; }//构造函数
};
/////////////////////////////////////////////////////////////////////////////////////////////////////
//BTree的数据类型
struct Data
{
	int key;//关键码
	int record;//关键码为key的数据在数组中的记录号
	Data(int k=-1,int r=-1):key(k),record(r){}
	Data& operator = (Data& x)
	{ key = x.key; record = x.record; return *this; }
};
/////////////////////////////////////////////////////////////////////////////////////////////////////
//类Btree的成员Array的元素类型
struct Element
{
	int key;//关键码
	char edata;//数组元素中应该存放的数据，此处设为字符类型
};
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
struct Triple//B_树的Search()函数的搜索结果
{
	Mnode<Type>* r;//Btree结点地址
	int i;//结点中的关键码序号
	int tag;//搜索成功标志
};
/////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
struct stkNode//按关键码从小到大遍历B_树时所用到的栈中结点结构
{
	const Mnode<Type> * Node;//B_树的结点指针
	int k;//k表示当前进栈结点向其子女结点遍历，其子女是它的ptr[]数组中的第k个指针
	stkNode(const Mnode<Type>* N,int K):Node(N),k(K){}//构造函数
};
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type> 
class Btree {		  
public:
	Btree(int M=Msize):root(NULL),m(M){  } //构造函数
    int Insert(Type& x);//插入函数
	int Remove(Type& x);//在树中删除关键码x.key，并返回其记录号
	int GetRecord(Type& k);//查找关键码为k.key的结点，返回该结点在被索引数组中的数组记录号
	void GetKeyRange(Type& a,Type& b);//按由小到大的顺序输出B_树中的关键码在a.key到b.key内的结点的关键码
	Triple<Type>& Search(const Type& x);// 在B_树中查找关键码为x.key的结点，返回指向它的指针和该关键码是结点的data[]数组的第几个关键码，附带一个搜索成功标志tag
	void move(Mnode<Type> * p,Mnode<Type>* q,int s);//此函数将p的data[s+1...m]和ptr[s...m]移到q的data[1...s-1]和ptr[0...s-1]，p->n改为s-1，q->改为m-s
	void print();//打印B_树
    friend istream& operator >>(istream& in,Btree<Type>& Tree);//输入B_树的相关数据		
private:
	Element* Array;//B_树对象基于的数组
	int m;//B_树的阶
	int arraysize;//数组的元素个数
    Mnode<Type> *root;//B_树的根

	void LeftAdjust(Mnode<Type>* p,Mnode<Type>* q,int d,int j);//在B_树中作删除操作时恢复B_树平衡的左平衡函数
	void RightAdjust(Mnode<Type>* p,Mnode<Type>* q,int d,int j);//在B_树中作删除操作时恢复B_树平衡的右平衡函数
	void insertkey(Mnode<Type>* p,int j,Type& k,Mnode<Type>* ap);//K,ap插入到结点p的位置j，同时p->n加一
	void compress(Mnode<Type>* p,int j);//在结点p中由第j个位置开始后面的data[]和ptr[]向前移一个位置
	void merge(Mnode<Type>* p,Mnode<Type>* q,Mnode<Type>* p1,int j);//作删除操作时遇到被删结点及其左右兄弟结点的关键码个数均少于指定个数时，叶子结点p和p1合并的函数，保留p
};
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type>
Triple<Type>& Btree<Type>::Search(const Type& x)
{
	Triple<Type> *result = new Triple<Type>;//存放返回结果的工作单元，因为要按引用返回，所以用
	                                        //指针new声明和分配内存空间，以防返回函数内部的局部变量
	Mnode<Type> *p = root,*q = NULL;//p是扫描指针，q是p的父结点指针
	int i = 0;
	while(p != NULL)//当p不为空，继续搜索
	{
		i = 0;
		p->data[(p->n)+1].key = MAXKEY;//用data[]的最后一个元素作为监视哨
		while(p->data[i+1].key<x.key) i++;//在结点内顺序寻找关键码x.key
		if(p->data[i+1].key == x.key)//搜索成功，本结点内由x.key
		{
			result->r = p;//关键码在p所指向的结点中
			result->i = i+1;//x.key是结点p的数组data[]的第i+1个元素
			result->tag = 0;//返回搜索成功标志,tag==0表示本结点内由x.key
			return *result;
		}
		q = p;//本结点没有x.key，q记下当前节点
		p = p->ptr[i];//p下降到相应的子树结点
	}
	//搜索失败
	result->r = q;//这时可以插入关键码x.key的结点是q
	result->i = i+1;//可以插入的位置是q的第i+1个位置
	result->tag = 1;//返回搜索失败标志
	return *result;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type>
int Btree<Type>::Insert(Type& x)
{
	if(root == NULL)//当B_树为空树时作特殊处理,为根结点分配内存空间和赋值
	{
		root = new Mnode<Type>;
		root->n = 1;
		root->data[1] = x;
		root->parent = NULL;
		root->ptr[0] = root->ptr[1] = NULL;
		return 1;
	}

	Triple<Type> loc = Search(x);//在树中搜索x的插入位置
	if(!loc.tag)
		return 0;//x已在树中，不插入
	Mnode<Type> *p = loc.r,*q,*ap = NULL,*t;//p指向x将要插入的结点地址，ap时插入x的位置的右邻指针
	Type K = x;//(K,ap)形成插入二元对
	int j = loc.i;

	while(1)
	{
		if(p->n<m-1)//结点的关键码个数未超出，可容纳新的关键码
		{
			insertkey(p,j,K,ap);//(K,ap)插入到位置j，p->n加一
			return 1;
		}
		int s = (m+1)/2;//准备分裂结点，s时m/2取上限的位置
		insertkey(p,j,K,ap);//先插入，结点中的p->n达到m
		q = new Mnode<Type>;//建立新的结点q
		move(p,q,s);//移动p的相应关键码到q中

		K = p->data[s];
		ap = q;         //(K,ap)形成向上插入二元组
		
		if(p->parent != NULL)//从下向上进行调整:原来的p部位根
		{
			t = p->parent;//取p的父结点
			j = 0;
			t->data[(t->n)+1].key = MAXKEY;//在父结点t内顺序搜索，设监视哨
			while(t->data[j+1].key<K.key) j++;//搜索，找到大于K.key的关键码停
			q->parent = p->parent;//新结点q的双亲指针赋值
			p = t;//p上升到父结点，向上调整
			j++;
		}
		else//原来的p是根，要产生新的根
		{
			root = new Mnode<Type>;
			root->n = 1;
			root->parent = NULL;
			root->data[1] = K;
			root->ptr[0] = p;
			root->ptr[1] = ap;
			q->parent = p->parent = root;
			return 1;
		}
	}//while(1)
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
void Btree<Type>::insertkey(Mnode<Type>* p,int j,Type& K,Mnode<Type>* ap)
{
	if(p->n >= j)//如果插入位置是在p所指结点的中间位置，则要将将data[]和ptr[]数组中的相应元素后移一个位置，挪出空位插入
	{
		for(int i=p->n;i>=j;i--)
		{
			p->data[i+1] = p->data[i];
			p->ptr[i+1] = p->ptr[i];
		}
	}
	p->ptr[j] = ap;//插入
	p->data[j] = K;
	p->n++;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type> 
void Btree<Type>::move(Mnode<Type>* p,Mnode<Type>* q,int s)
{//此函数将p的data[s+1...m]和ptr[s...m]移到q的data[1...s-1]和ptr[0...s-1]，p->n改为s-1，q->改为m-s
	int i,j;
	for(i = 0,j=s+1;j<=m;i++,j++)
	{
		q->ptr[i] = p->ptr[j-1];
		q->data[i+1] = p->data[j];//复制数据到结点q中
	}
	q->ptr[i] = p->ptr[j-1];
	p->n = s-1;//结点p的关键码个数为s-1
	q->n = m-s;//结点q的关键码个数为m-s
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type> 
int Btree<Type>::Remove(Type& x)
{
	Triple<Type> loc = Search(x);//在树中搜索关键码为x.key的结点
	if(loc.tag) return -1;//没找到，返回
	
	int record = loc.r->data[loc.i].record;//用record记下关键码为x.key的数组在被索引数组中的记录号

	Mnode<Type> * p = loc.r,*q,*s;//p是关键码x.key所在的结点
	int j = loc.i;//j是关键码在结点中的位置
	if(p->ptr[j] != NULL)//若p非叶子结点
	{
		s = p->ptr[j];//s取得结点p上的第j个指针
		q = p;
		while(s != NULL) 
		{
			q =s; 
			s = s->ptr[0];//找大于x.key但最接近与x.key的最小关键码
		}
		p->data[j] = q->data[1];//用最小关键码填补
		compress(q,1);//在结点q中关键码与指针前移填补data[j]，p->n减一
		p = q;//下一步处理结点q中的删除
	}
	else compress(p,j);//p是叶子结点，关键码与指针前移填补data[j]p->n减一
	int d = (m+1)/2;
	while(1)
	{
		if(p->n<d-1)//需要调整
		{
			j = 0;
			q = p->parent;
			while(j<=q->n && q->ptr[j]!=p) j++;//在q中找指向p的指针
			if(!j) LeftAdjust(p,q,d,j);//p是q的最左子女，与其右兄弟与双亲结点作调整
			else RightAdjust(p,q,d,j);//p不是q的最左子女，与其左兄弟与双亲结点作调整