B-树 插入删除 C代码实现

#include 
#include 

#define MAX_M 5

static int m = MAX_M;
static int max = MAX_M - 1;
static int min = （MAX_M - 1） / 2;

typedef struct b_node
{
	int key_num;
	int key_list[MAX_M+1]; // 空出一个位，从1开始
	struct b_node *parent;
	struct b_node *ptr_list[MAX_M+1];
} b_node_t;

void b_node_destroy（b_node_t *b_node）
{
	int i;
	for（i = 0; i < MAX_M + 1; ++i）
	{
		if（b_node->ptr_list[i] != NULL） b_node_destroy（b_node->ptr_list[i]）;
	}
	free（b_node）;
}

void b_node_display（b_node_t *b_node）
{
	int i;
	printf（“node_keynum:%d  “ b_node->key_num）;
	for（i = 1; i <= b_node->key_num; ++i）
	{
		printf（“%d “ b_node->key_list[i]）;
	}
	printf（“\n“）;
	for（i = 0; i <= b_node->key_num; ++i）
	{
		if（b_node->ptr_list[i] != NULL） b_node_display（b_node->ptr_list[i]）;
	}
}

typedef struct result
{
	b_node_t *ptr;
	int i;
	int tag;
} result_t;

int node_search（b_node_t *b_node int k）
{
	int i;
	for（i = 1; i <= b_node->key_num; ++i）
	{
		if（b_node->key_list[i] >= k） break;
	}
	return i;
}

/* 
	在b_node搜索key为k的节点，若查找成功，则特征值tag = 1 指针ptr指向第i个关键字等于k，
	否则特征值等于0，等于k的关键字应插入在指针ptr所指节点中第i个和i + 1个关键字之间
*/
result_t tree_search（b_node_t *b_node int k）
{
	int i found = 0;
	result_t result;
	b_node_t *cur *pre;
	cur = b_node;
	while（cur != NULL）
	{
		i = node_search（cur k）;
		if（cur->key_list[i] == k）
		{
			found = 1;
			break;
		}
		else
		{
			pre = cur;
			cur = cur->ptr_list[i-1];
		}
	}
	result.i = i;
	if（found）
	{
		result.ptr = cur;
		result.tag = 1;
	}
	else
	{
		result.ptr = pre;
		result.tag = 0;
	}
	return result;
}

void new_root（b_node_t **root b_node_t *p int x b_node_t *ap）
{
	（*root） = （b_node_t *）malloc（sizeof（b_node_t））;
	（*root）->parent = NULL;
	（*root）->key_list[1] = x;
	（*root）->key_num = 1;
	（*root）->ptr_list[0] = p;
	（*root）->ptr_list[1] = ap;
	if（p != NULL） p->parent = （*root）;
	if（ap != NULL） ap->parent = （*root）;
}

// 将k和ap插入到p指向的节点里的i到i+1位置中
void insert_node（b_node_t *p int i int k b_node_t *ap）
{
	int j;
	for（j = p->key_num; j >= i; --j）
	{
		p->key_list[j+1] = p->key_list[j];
		p->ptr_list[j+1] = p->ptr_list[j];
	}
	p->key_list[i] = k;
	p->ptr_list[i] = ap;
	if（ap != NULL） ap->parent = p;
	p->key_num++;
}

// 将p所指的节点分裂一半到ap里
void split（b_node_t *p b_node_t **ap）
{
	int s j;
	s = （m + 1） / 2;
	p->key_num = s - 1;
	（*ap） = （b_node_t *）malloc（sizeof（b_node_t））;
	（*ap）->ptr_list[0] = p->ptr_list[s];

	for（j = s+1; j <= m; ++j）
	{
		（*ap）->key_list[j-s] = p->key_list[j];
		（*ap）->ptr_list[j-s] = p->ptr_list[j];
	}

	（*ap）->key_num = m - s;
	（*ap）->parent = p->parent;
	
	for（j = 0; j <= （*ap）->key_num; j++）
	{
		if（（*ap）->ptr_list[j] != NULL） （*ap）->ptr_list[j]->parent = （*ap）;
	}
}

void insert_b_tree（b_node_t **t int k）
{
	int x = k s finish = 0;
	result_t r;
	b_node_t *ap = NULL *tmp;
	if（（*t） == NULL）
	{
		new_root（t NULL k NULL）;
		return;
	}
	r = tree_search（（*t）