myrbtree.c

红黑树生成及应用的算法程序

	if(data)
		*data = node->data;

	if(key)
		*key = node->key;

	//销毁node
	rbtree_inter_destroy_node(rbtree, node);
}

static int rbtree_inter_countlayer(myrbtree_node_t * root, int bmax)
{
	int left = 0;
	int right = 0;

	if(NULL == root)
		return 0;

	left = rbtree_inter_countlayer(root->left, bmax);
	right = rbtree_inter_countlayer(root->right, bmax);

	if(left > right && bmax)
		return left + 1;
	else
		return right + 1;
}

static myrbtree_node_t * rbtree_inter_begin(myrbtree_t * rbtree)
{
	myrbtree_node_t * node;

	assert(rbtree);

	node = rbtree->root;
	if(NULL == node)
		return NULL;

	while(node->left)
		node = node->left;

	return node;
}

static myrbtree_node_t * rbtree_inter_end(myrbtree_t * rbtree)
{
	myrbtree_node_t * node;

	assert(rbtree);

	node = rbtree->root;
	if(NULL == node)
		return NULL;

	while(node->right)
		node = node->right;

	return node;
}

static void rbtree_inter_erase(myrbtree_t * rbtree, myrbtree_node_t * node)
{
	assert(node);

	while(node)
	{
		myrbtree_node_t * y = node->left;

		if(node->right)
			rbtree_inter_erase(rbtree, node->right);

		rbtree_inter_destroy_node(rbtree, node);

		node = y;
	}
}

static int rbtree_inter_realcount(myrbtree_node_t * root)
{
	int left = 0;
	int right = 0;

	if(NULL == root)
		return 0;

	if(root->left)
		left = rbtree_inter_realcount(root->left);

	if(root->right)
		right = rbtree_inter_realcount(root->right);

	return left + right + 1;
}

static int rbtree_inter_examin(myrbtree_node_t * node)
{
	int left = 0;
	int right = 0;

	if(NULL == node)
		return 0;

	if(node->left)
		left = rbtree_inter_examin(node->left);

	if(node->right)
		right = rbtree_inter_examin(node->right);

	assert(left == right);

	if(rbtree_colour_black == node->colour)
		return left + 1;
	else
		return left;
}


/*
*
*创建rb树
*
*/
HMYRBTREE MyRBTreeConstruct(HMYMEMPOOL hm, myrbtree_compare compare)
{
	myrbtree_t * rbtree = NULL;

	rbtree = (myrbtree_t *)MyMemPoolMalloc(hm, sizeof(*rbtree));

	if(NULL == rbtree)
		return NULL;

	memset(rbtree, 0, sizeof(*rbtree));

	rbtree->compare = compare;
	rbtree->hm = hm;

	return (HMYRBTREE)rbtree;
}

/*
*
*销毁rb树
*
*/
void MyRBTreeDestruct(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = NULL;

	if(NULL == rbtree)
		return;

	//遍历树,释放每个节点
	if(rbtree->root)
		rbtree_inter_erase(rbtree, rbtree->root);

	MyMemPoolFree(rbtree->hm, rbtree);
}

/*
*
*删除所有节点
*
*/
void MyRBTreeClear(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return;

	if(NULL == rbtree->root)
		return;

	//遍历树,释放每个节点
	rbtree_inter_erase(rbtree, rbtree->root);
	rbtree->root = NULL;
}

/*
*
*往rb树中插入一个节点
*
*/
HMYRBTREE_ITER MyRBTreeInsertEqual(HMYRBTREE htree, void * key, void * userdata)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = NULL;
	myrbtree_node_t * node_new = NULL;
	myrbtree_node_t * parent = NULL;

	if(NULL == rbtree)
        return NULL;

	parent = node = rbtree->root;
	while(node)
	{
		parent = node;

		//如果比节点值域"大" 找右孩子 如果"小" 找左孩子
		if(rbtree_inter_compare(rbtree, key, node->key))
			node = node->right;
		else
			node = node->left;
	}

	node_new = rbtree_inter_insert(rbtree, parent, key);

	if(node_new)
		node_new->data = userdata;

	return (HMYRBTREE_ITER)node_new;
}

/*
*
*往rb树中插入一个节点
*
*/
HMYRBTREE_ITER MyRBTreeInsertUnique(HMYRBTREE htree, void * key, void * userdata)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	myrbtree_node_t * y = NULL;
	myrbtree_node_t * x = NULL;
	myrbtree_node_t * parent = NULL;
	myrbtree_node_t * node_new = NULL;

	if(NULL == rbtree)
        return NULL;

	parent = x = rbtree->root;
	while(x)
	{
		parent = x;

		if(!rbtree_inter_compare(rbtree, x->key, key))
			y = x, x = x->right;
		else
			x = x->left;
	}

	if(NULL != y && !rbtree_inter_compare(rbtree, key, y->key))
		return (HMYRBTREE_ITER)y;

	node_new = rbtree_inter_insert(rbtree, parent, key);

	if(node_new)
		node_new->data = userdata;

	return (HMYRBTREE_ITER)node_new;
}

/*
*
*从rb树中删除一个节点 iter失效
*
*/
void MyRBTreeDelIter(HMYRBTREE htree, HMYRBTREE_ITER iter, void ** key, void ** data)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = (myrbtree_node_t *)iter;

	if(NULL == rbtree || NULL == node)
		return;

	assert(rbtree_inter_search(rbtree, node->key));

	rbtree_inter_del(rbtree, node, key, data);
}

/*
*
*根据键值删除一个节点
*成功删除返回0, 否则返回-1
*
*/
int MyRBTreeDelKey(HMYRBTREE htree, void * key, void ** key_ret, void ** data_ret)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = NULL;

	if(NULL == rbtree)
		return -1;

	node = rbtree_inter_search(rbtree, key);

	if(NULL == node)
		return -1;

	rbtree_inter_del(rbtree, node, key_ret, data_ret);

	return 0;
}

/*
*
*获取节点的用户数据
*
*/
void * MyRBTreeGetIterData(HMYRBTREE_ITER iter)
{
	myrbtree_node_t * node = (myrbtree_node_t *)iter;

	if(NULL == node)
		return NULL;

	return node->data;
}

/*
*
*查找节点
*
*/
HMYRBTREE_ITER MyRBTreeSearch(HMYRBTREE htree, void * key)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = NULL;

	if(NULL == rbtree || NULL == rbtree->compare)
		return NULL;

	node = rbtree_inter_search(rbtree, key);

	return (HMYRBTREE_ITER)node;
}

/*
*
*计算最大层数
*
*/
int MyRBTreeLayer(HMYRBTREE htree, int bmax)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return rbtree_inter_countlayer(rbtree->root, bmax);
}

/*
*
*"获取第一个节点"
*
*/
HMYRBTREE_ITER MyRBTreeBegin(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return (HMYRBTREE_ITER)rbtree_inter_begin(rbtree);
}

/*
*
*"获取最后一个节点"
*
*/
HMYRBTREE_ITER MyRBTreeEnd(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return (HMYRBTREE_ITER)rbtree_inter_end(rbtree);
}

/*
*
*检查红黑树是否合法
*
*/
int MyRBTreeExamin(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return rbtree_inter_examin(rbtree->root);
}

/*
*
*获取个数
*
*/
int MyRBTreeGetRealCount(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return rbtree_inter_realcount(rbtree->root);
}