b-tree.cpp

btree算法

#include "b-tree.h"
#include "StdAfx.h"

template <typename T> int BinarySearch(T a[], int sz, T key)
{
	int low = 1;
	int high = sz;
	int mid = 0;
	T   midVal;
	while(low<=high)
	{
		mid = (low+high)/2;
		midVal = a[mid];
		if(midVal < key) //Less than
		{
			low++;
		}
		else if(midVal > key)  // Greater than
		{
			high--;
		}
		else
		{
			return mid; //如果找到了返回目标值所在位置
		}
	}

	//如果不存在， 返回最后查找到的最相近的值
	return mid;
}

template <class T> CBMTree<T>::CBMTree()
{
	;
}

template <class T> CBMTree<T>::~CBMTree()
{
	;
}

template <class T> bool CBMTree<T>::SearchBMTree(BMNode<T> *p_root,T key, BMNode<T> **p_keypos, int &keyidx)
{
	BMNode<T> *p = p_root;
	BMNode<T> *q = NULL;
	bool found = false;

	int idx = 0;
	while(!found && p)
	{
		idx = BinarySearch(p->key, p->keynum, key);
		if(key == p->key[idx])
		{
			found = true;
		}
		else if(key > p->key[idx])
		{
			q = p;
			p = q->ptr[idx];
		}
		else
		{
			idx--;
			q = p;
			p = q->ptr[idx];
		}
	}

	if(found) //查找成功， 返回k的位置信息
	{
		*p_keypos = p;
		keyidx = idx;

		return true;
	}
	else//查找不成功， 返回k的插入位置信息
	{
		*p_keypos = q;
		keyidx = idx;
		return false;
	}
}

template <class T> int CBMTree<T>::Insert(BMNode<T> *q, T key, int idx, BMNode<T> *ap)
{
	BMNode<T> *ptr1, *ptr2;
	T k1,k2;
	
	k1 = q->key[idx+1];
	ptr1 = q->ptr[idx+1];
	for(int i = idx+1; i <= q->keynum; i++)
	{
		k2   = k1;
		ptr2 = ptr1;
		k1   = q->key[i+1];
		ptr1 = q->ptr[i+1];
		q->key[i+1] = k2;
		q->ptr[i+1] = ptr2;
	}
	q->key[idx+1] = key;
	q->ptr[idx+1] = ap;
	ap?ap->parent = q:NULL;
	q->keynum++;

	return q->keynum;
}

template <class T> int CBMTree<T>::Split(BMNode<T> *q,BMNode<T> **ap)
{
	int s = m%2==0?m/2:m/2+1;

	*ap = new BMNode<T>;
	(*ap)->parent = q->parent;
	
	int i;
	//Store the last key to a new node
	for(i = s+1; i <= q->keynum; i++)
	{
		(*ap)->key[i-s] = q->key[i];
		q->key[i] = -1;	
	}
	for(i = s+1; i <= q->keynum+1; i++)
	{
		(*ap)->ptr[i-s-1] = q->ptr[i-1];
		q->ptr[i-1] = NULL;
		(*ap)->ptr[i-s-1]?(*ap)->ptr[i-s-1]->parent = *ap:NULL;
	}
    (*ap)->keynum = q->keynum - s;
	(*ap)->parent = q->parent;
	q->keynum = s-1;

	return 0;
}

template <class T> int CBMTree<T>::InsertBMTree(BMNode<T> **p_root, T key)
{
	BMNode<T> *root = *p_root;
	bool finished = false;
	T keytmp = key;

	BMNode<T> *p=NULL,*q = NULL;
	int keyidx;
    bool bexist = false;
	bexist = SearchBMTree(root, key, &q, keyidx);
	if(bexist)//Already exist
	{
		return 0;
	}

	BMNode<T> *ap = NULL;
	int s;
	while(q && !finished)
	{
		//Insert the node
		Insert(q, keytmp,keyidx, ap);

		if(q->keynum < m) //Ok, Insert finished.
		{
			finished = true;
		}
		else // Need to split q_root;
		{
			s = m%2==0?m/2:m/2+1;
			Split(q, &ap);

			keytmp = q->key[s];
			q->key[s] = -1;
			p = q;
			q = p->parent;
			if(q)
			{
				p = q;
				keyidx = BinarySearch(p->key, p->keynum, keytmp);
				if(key == p->key[keyidx])
				{
					bexist = true;
					finished = true;
				}
				else if(keytmp > p->key[keyidx])
				{
					;
				}
				else
				{
					keyidx--;
				}
			}
			else
			{
				q = new BMNode<T>();
				q->keynum=1;
				q->parent=NULL;
				q->key[1]=keytmp;
				q->ptr[0] = p;
				q->ptr[1] = ap;
				p->parent = q;
				ap->parent = q;
				*p_root = q;
				q = q->parent;
				finished = true;
			}
		}
	}

	if(!finished) //NULL Tree
	{
		*p_root = new BMNode<T>(); 
		(*p_root)->keynum=1;
		(*p_root)->parent=NULL;
		(*p_root)->key[1]=key;
		(*p_root)->ptr[0]=NULL;
	}

	return 0;
}

//B-树是二叉排序树的推广，中序遍历B-树同样可得到关键字的有序序列（具体遍历算法【参见练习】）。
//任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。
//若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K'取代K，然后从叶子中删去K'。从叶子
//*x开始删去某关键字K的三种情形为：
//      情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。
//  注意：min = m/2取上限+1
//    　 
//   　情形二：若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。
//  若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点
//  *parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移
//  出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等于Min；而*x中已移
//  入一个关键字，故删K后*x中仍有Min个关键字。涉及移动关键字的三个结点均满足B-树的性质(3)。 
//  请读者验证，上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。
//    　情形三：若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，则上述的移动
//  操作就不奏效，此时须*x和左或右兄弟合并。不妨设*x有右邻兄弟*y(对左邻兄弟的讨论与此类似)，在*x中
//  删去K及其右子树后，将双亲结点*parent中介于*x和*y之间的关键字K，作为中间关键字，与并x和*y中的关
//  键字一起"合并"为一个新的结点取代*x和*y。因为*x和*y原各有Min个关键字，从双亲中移人的K'抵消了从*x
//  中删除的K，故新结点中恰有2Min(即2「m/2」-2≤m-1)个关键字，没有破坏B-树的性质(3)。但由于K'从双亲
//  中移到新结点后，相当于从*parent中删去了K'，若parent->keynum原大于Min，则删除操作到此结束；否则，
//  同样要通过移动*parent的左右兄弟中的关键字或将*parent与其 左右兄弟合并的方法来维护B-树性质。
//  最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并
//  成一个新的根，从而使整棵树的高度减少一层。
template <class T> int CBMTree<T>::DeleteBMTree()
{
	return -1;
}


int main(int argc, char* argv[])
{
	CBMTree<int> bst;
	BMNode<int>  *root=NULL;
	BMNode<int>  *keypos;
	int keyidx;
	int key = 0;
	void outputBS(BMNode<int> *, int floor);
	int a[] = {45,24,3,12,37,53,90,50,61,70,100,30,26,85,7,7, 48, 102, 105, 106,\
		110, 120, 130, 140, 150, 160, 170, 180, 190, 200,\
	    210, 220, 230, 240, 250, 260, 270, 280, 290, 300,\
	    310, 320, 330, 340, 350, 360, 370, 380, 390, 400,\
	    410, 420, 430, 440, 450, 460, 470, 480, 490, 500};\
	bst.SearchBMTree(root,key, &keypos, keyidx);
	
	for(int i = 0;i < 26; ++i)
	{
		bst.InsertBMTree(&root, a[i]);
		printf("insert %d...\n", a[i]);         
		outputBS(root,0);         
		printf("|\n"); 
	}
	bst.SearchBMTree(root,key, &keypos, keyidx);
	return 0;
}

void outputBS(BMNode<int> *root, int floor) 
{     
	if (root == NULL) 
		return;
	BMNode<int> *tmp = root;

	floor++;

	for(int ii = 0; ii<floor; ii++)
		printf("  ");
	
	for(int k=1; k<=tmp->keynum; k++)
	{
		if(k!=1)printf(",");
		printf("%3d", tmp->key[k]);
	}
	printf("---------\n"); 
	for(int i=0; i<=tmp->keynum; i++)
	{
		outputBS(tmp->ptr[i], floor);
	}
     
	printf("\n");         
}