btree.cpp

其他人不需帐号就可自由下载此源码 其他人不需帐号就可自由下载此源码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#include "btree.h"


/*

bs_开头的都是实现B-树的接口函数

*/


static int  bs_search_key(BSTREE_NODE *p, BSTREE_KEY k);
static int  bs_split_node(BSTREE_NODE *&q, BSTREE_NODE *&ap);
static int  bs_new_root(BSTREE_NODE *&t, BSTREE_NODE *p, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap);
static void bs_remove(BSTREE_NODE *p, int i);
static void bs_successor(BSTREE_NODE *p, int i);
static void bs_move_right(BSTREE_NODE *p, int i) ;
static void bs_move_left(BSTREE_NODE *p, int i) ;
static void bs_combine(BSTREE_NODE *p, int i) ;
static void bs_restore(BSTREE_NODE *p,int i);
static void bs_insert_node(BSTREE_NODE *&q, int i, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap) ;
static int  bs_search_node(BSTREE_KEY k, BSTREE_NODE *p, int &i);
static int  bs_delete_record(BSTREE_KEY k, BSTREE_NODE * p);
static void bs_display_tree(BSTREE_NODE *t);
void        bs_test_tree(void) ;



/*

在p-key[1..keynum]中找i,使得p->key[i]<= k < p->key[i + 1]

*/
static int bs_search_key(BSTREE_NODE *p, BSTREE_KEY k) {
	int i;
	for(i = 0; i < p->keynum && p->key[i + 1] <= k; i++);
	return i;
}



/*

在M阶t树上查找关键字k,返回结果BSTREE_RESULT(ptr, i, tag),查找成功
tag = 1,ptr指向找到节点i个关键字等于k;否则特征值tag=0,等于k的值应
当插入在指针ptr所指结点中第i和第i+1个关键字之间

*/
BSTREE_RESULT bs_search_tree(BSTREE_NODE *t, BSTREE_KEY k) {

	BSTREE_NODE *p = t, *q = NULL;
	int found = 0, i = 0;
	BSTREE_RESULT rs;

	while(p != NULL && !found) {

		i = bs_search_key(p, k);

		if (i > 0 && p->key[i] == k) {
			found = 1;
		} else {
			q = p;
			p = p->ptr[i];
		}
	}

	rs.i = i;
	if (found == 1) { 
		rs.ptr = p; rs.tag = 1; 
	} else { 
		rs.ptr = q; rs.tag = 0;
	}
	return rs;

}



/*

将x和ap与rec分别插入到q->key[i + 1]和q->ptr[i + 1]中q->rec[i + 1]

*/
static void bs_insert_node(BSTREE_NODE *&q, int i, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap) {
	int j;

	for(j = q->keynum; j > i; j--) {
		q->key[j + 1] = q->key[j];
		q->rec[j + 1] = q->rec[j];
		q->ptr[j + 1] = q->ptr[j];
	}
	q->rec[i + 1] = r;
	q->key[i + 1] = x;
	q->ptr[i + 1] = ap;

	if (ap != NULL) 
		ap->parent = q;
	q->keynum++;

}



/*

将节点q分裂成两个节点，前一半保留，后一半移入新生节点ap

*/
static int bs_split_node(BSTREE_NODE *&q, BSTREE_NODE *&ap) {

	int s = (DEF_BSTREE_STEPS + 1) / 2;
	int i;
	
	ap = (BSTREE_NODE *)calloc(1, sizeof(BSTREE_NODE));
	if (ap == NULL) return -1;

	ap->ptr[0] = q->ptr[s];

	for( i = s + 1; i <= DEF_BSTREE_STEPS; i++) {

		ap->key[i - s] = q->key[i];
		ap->rec[i - s] = q->rec[i];
		ap->ptr[i - s] = q->ptr[i];
		
		if (ap->ptr[i - s] != NULL) {
			ap->ptr[i - s]->parent = ap;
		}
	}
	ap->keynum = q->keynum - s;
	ap->parent = q->parent;

	for(i = 0; i <= q->keynum - s; i++) {
		if (ap->ptr[i] != NULL) {
			ap->ptr[i]->parent = ap;
		}
	}
	q->keynum = s - 1;
	return 0;
}



/*

生成含信息(t,x,r,ap,p)的新的根节点*t,原t和ap为子树指针

*/
static int bs_new_root(BSTREE_NODE *&t, BSTREE_NODE *p, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap) {

	t = (BSTREE_NODE *)calloc(1, sizeof(BSTREE_NODE));
	if (t == NULL) return -1;	
	t->keynum = 1;
	t->ptr[0] = p;
	t->key[1] = x;
	t->rec[1] = r;
	t->ptr[1] = ap;

	if (p  != NULL) p->parent  = t;
	if (ap != NULL) ap->parent = t;
	t->parent = NULL;	
	return 0;

}




/*

在m阶B-树T上结点*q的key[i]与key[i+1]之间插入关键字K的指针r。若引起
结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B-树。

*/
int bs_insert_tree(BSTREE_NODE *&t, BSTREE_KEY k, BSTREE_RECORD *r, BSTREE_NODE *q, int i) {

	BSTREE_KEY x;
	BSTREE_NODE *ap;
	BSTREE_RECORD *e;
	int finish, nr, s, status, max;
	
	max = DEF_BSTREE_STEPS - 1;
	if (q == NULL) {
		status = bs_new_root(t, NULL, k, r, NULL);
		return status;
	} else {
		x  = k;	e  = r;	ap = NULL;
		finish = nr = 0; 
		while(nr == 0 && finish == 0) {
			bs_insert_node(q, i, x, e, ap);
			if(q->keynum <= max) {
				finish = 1;
				break;
			} else {
				s = (DEF_BSTREE_STEPS + 1)/2;
				status = bs_split_node(q, ap);
				if (status < 0) { //内存申请失败
					return status;
				}
				x = q->key[s];
				e = q->rec[s];
				if(q->parent) {
					q = q->parent;
					i = bs_search_key(q, x);
				} else {
					nr = 1;
					break;
				}
			}
		}

		if(nr == 1) {
			status = bs_new_root(t, q, x, e, ap);
			return status;
		}
	}
	return 0;
}




/*

删除节点P第i个元素

*/
static void bs_remove(BSTREE_NODE *p, int i) {
	int j;

	for(j = i + 1; j <= p->keynum; j++) {
		p->key[j - 1] = p->key[j];
		p->rec[j - 1] = p->rec[j];
		p->ptr[j - 1] = p->ptr[j];		
	}
	p->keynum--;
}


/*

查找被删除关键字p-key[i](在非叶子节点中)的替代叶子节点

*/
static void bs_successor(BSTREE_NODE *p, int i) {
	BSTREE_NODE *q;
	for(q = p->ptr[i]; q->ptr[0] != NULL; q = q->ptr[0]);
	p->key[i] = q->key[1];
	p->rec[i] = q->rec[1];
}


/*

把一个关键字移动到右兄弟中

*/
static void bs_move_right(BSTREE_NODE *p, int i) {
	int c;

	BSTREE_NODE *t = p->ptr[i];

	for(c = t->keynum; c > 0; c--) {
		t->key[c + 1] = t->key[c];
		t->ptr[c + 1] = t->ptr[c];
		t->rec[c + 1] = t->rec[c];
	}

	t->ptr[1] = t->ptr[0];
	t->key[1] = p->key[i];
	t->rec[1] = p->rec[i];
	t->keynum++;

	t = p->ptr[i-1];
	p->key[i] = t->key[t->keynum];
	p->rec[i] = t->rec[t->keynum];
	p->ptr[i]->ptr[0] = t->ptr[t->keynum];
	t->keynum--;

}


/*

把关键字移动到左兄弟中

*/
static void bs_move_left(BSTREE_NODE *p, int i) {   
	
	int c;
	BSTREE_NODE *t;
	
	t = p->ptr[i-1];
	t->key[t->keynum] = p->key[i];
	t->rec[t->keynum] = p->rec[i];
	t->ptr[t->keynum] = p->ptr[i]->ptr[0];
	t->keynum++;

	t = p->ptr[i];
	p->key[i] = t->key[1];
	p->rec[i] = t->rec[1];
	p->ptr[0] = t->ptr[1];
	t->keynum--;

	for(c = 1;c <= t->keynum; c++) {

		t->key[c] = t->key[c + 1];
		t->rec[c] = t->rec[c + 1];
		t->ptr[c] = t->ptr[c + 1];

	}
}


/*

将三个节点合并到一个节点中

*/
static void bs_combine(BSTREE_NODE *p, int i) {   
	int c;

	BSTREE_NODE *q = p->ptr[i];
	BSTREE_NODE *l = p->ptr[i-1];

	l->keynum++;

	l->key[l->keynum] = p->key[i];
	l->rec[l->keynum] = p->rec[i];
	l->ptr[l->keynum] = q->ptr[0];
	
	for(c = 1;c <= q->keynum; c++) {
		l->keynum++;
		l->key[l->keynum] = q->key[c];
		l->rec[l->keynum] = q->rec[c];
		l->ptr[l->keynum] = q->ptr[c];
		
	}
	
	for(c = i; c < p->keynum; c++) {
		p->key[c] = p->key[c + 1];
		p->rec[c] = p->rec[c + 1];
		p->ptr[c] = p->ptr[c + 1];
	}
	p->keynum--;
	
	free(q);
}


/*

关键字删除后，调整B-树，找到一个关键字将其插入到p->ptr[i]中

*/
static void bs_restore(BSTREE_NODE *p,int i) {

	int min = (DEF_BSTREE_STEPS - 1) / 2;
	
	if(i == 0) {
		if (p->ptr[1]->keynum > min) {
			bs_move_left(p, 1);
		} else {
			bs_combine(p, 1);
		}
	} else if (i == p->keynum) {
		if(p->ptr[i - 1]->keynum > min) {
			bs_move_right(p, i);
		} else {
			bs_combine(p, i);
		}
	} else if (p->ptr[i - 1]->keynum > min) {
		bs_move_right(p, i);	
	} else if (p->ptr[i + 1]->keynum > min) {
		bs_move_left(p, i + 1);
	} else {
		bs_combine(p, i);
	}
}


/*

在节点p中找关键字为看的位置i，成功返回1,否则返回0

*/
static int bs_search_node(BSTREE_KEY k, BSTREE_NODE *p, int &i) {   

	if(k < p->key[1])	{
		i = 0; 
		return 0;
	} else{
		i = p->keynum;
		while(k < p->key[i] && i> 1)
			i--;
		return (k == p->key[i]);
	}
}


/*

查找并删除关键字k

*/
static int bs_delete_record(BSTREE_KEY k, BSTREE_NODE * p) {  

	int i;
	int found;
	int min = (DEF_BSTREE_STEPS - 1) / 2;
	
	if(p == NULL)
		return 0;
	else {
		if (( found = bs_search_node(k,p,i)) == 1) {
			if(p->ptr[i-1] != NULL)	{
				bs_successor(p, i);
				bs_delete_record(p->key[i], p->ptr[i]);
			} else 
				bs_remove(p, i);
		} else 
			found = bs_delete_record(k, p->ptr[i]);
		
		if(p->ptr[i] != NULL)
			if(p->ptr[i]->keynum < min)
				bs_restore(p, i);
		return found;
	}
}


/*

从B-树root中删除关键k,若在一个节点中删除指定关键字，不再有其他关键字，则删除该节点
0: 表示没有该关键字
1: 表示删除成功,并且删除了该节点
2: 成功删除该关键字

*/
int bs_delete_tree(BSTREE_NODE * &root, BSTREE_KEY k)  {
	
	BSTREE_NODE *p;
	if(bs_delete_record(k, root) == 0)
		return 0;
	else if (root->keynum == 0) {
		p = root;
		root = root->ptr[0];
		free(p);
		return 1;
	}
	return 2;
}



/*++++++++++++++++++测试代码+++++++++++++++++++++++++++++++++++++++/
/*

显示B-树的数据

*/
void bs_display_tree(BSTREE_NODE *t) {
	int i;

	if (t != NULL) {

		printf("[");
		for(i = 1; i < t->keynum; i++)
			printf(" %d ", t->key[i]);
		printf(" %d ", t->key[i]);
		printf("]");

		if (t->keynum > 0) {
			if (t->ptr[0] != NULL) printf("(");

			for( i = 0; i < t->keynum; i++) {
				bs_display_tree(t->ptr[i]);
				if (t->ptr[i + 1] != NULL)
					printf(",");
			}
			bs_display_tree(t->ptr[t->keynum]);
			if (t->ptr[0] != 0)
				printf(")");
		}
	}
}

void bs_test_tree(void) {

	BSTREE_NODE *t = NULL;
	BSTREE_RESULT s;
	int j, n = 10;
	typedef struct MREC {
		int i;
		char a[20];
		SOCKET s;
	} MREC;

	BSTREE_KEY a[] = {4,9,0,1,8,6,3,5,2,7}, k;
	MREC rec[10];
	rec[0].i = 1000;strcpy(rec[0].a, "ABCDEF"); rec[1].i = 2; strcpy(rec[1].a, "GH");rec[2].i = 3; rec[3].i = 4; rec[4].i = 5;rec[5].i = 6;rec[6].i = 7;rec[7].i=8;rec[8].i=9;rec[9].i = 10;
	printf("\n");
	printf("创建一棵%d阶B-树:\n", DEF_BSTREE_STEPS);

	for(j = 0; j < n; j++) {
		s = bs_search_tree(t, a[j]);
		if (s.tag == 0) 
			bs_insert_tree(t, a[j], (BSTREE_RECORD *)&rec[j], s.ptr, s.i);
		printf("  第%2d步,插入%d: ", j + 1, a[j]);
		bs_display_tree(t);
		printf("\n");
	}
	printf("查询操作\n");
	k = 9;
	s = bs_search_tree(t, k);
	if (s.tag == 0) {
		printf("没有找到key=%d\n", k);
	} else {
		printf("找到 key = %d, rec.i=%d,rec.a=%s\n", k, ((MREC *)s.ptr->rec[s.i])->i,((MREC *)s.ptr->rec[s.i])->a);
	}
	printf("删除操作:\n");
	k = 8;
	bs_delete_tree(t, k);
	printf(" 删除 %d:", k);

	bs_display_tree(t);
	printf("\n");
	k = 1;
	bs_delete_tree(t, k);
	printf("  删除%d: ", k);
	bs_display_tree(t);
	printf("\n\n");

}

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/