myrbtree.c

sourceforge历史版本完整下载: http://sourceforge.net/project/showfiles.php?group_id=202044 提供了基于b树索引算法的文件数据数据

*key:新节点的关键字
*
*/
static __INLINE__ void rbtree_inter_insert(myrbtree_t * rbtree, myrbtree_node_t ** root, myrbtree_node_t * node_new, myrbtree_node_t * parent)
{
	assert(rbtree && node_new && root);

	//如果父节点为空，表明添加的是根节点
	if(NULL == parent)
	{
		//根节点必有黑色
		node_new->colour = rbtree_colour_black;
		*root = node_new;

		assert(NULL == *root || NULL == (*root)->parent);

		return;
	}

	node_new->parent = parent;

	//比较节点键值与父节点键值大小
	if(rbtree_inter_compare(rbtree, node_new->key,parent->key))
		parent->right = node_new;
	else
		parent->left = node_new;

	//旋转树，使之符合红黑树的规则
	rbtree_inter_rebalance(root, node_new);
}

/*
*
*从rb树中删除一个节点
*
*删除除节点 z , 则可以用y完全取代z(位置,颜色,用户数据), 删除z演变成删除y
*
* 图1
*      a                         a
*     / \                       / \
*    ?   z                     ?   y
*       / \       ---->           / \ 
*      ?   b                     ?   b
*         / \                       / \
*        y   ?            del ---> z   ?
*         \                         \
*          ?1                        ?1
*
*
*如果z是红色 则?1对应的子树根节点直接挪到z对应的位置,即完成了删除工作，并保证了红黑树的平衡性
*如果z是黑色 并且?1对应的子树根节点x为红色，则把?1挪到z的位置，并把x改成黑色，即完成了删除工作，并保证了红黑树的平衡性
*如果z是黑色 并且?1对应的子树根节点x也为黑色。
*图2
*
*     ?
*    / \
*   ?   x_parent
*      / \
*     x   ?2 = w
*    / \
*   ?   ?
*图2即最终要面临的情况
*x这个分支，由于去除了一个黑色的结点，而x又是黑色，它比 ?2 那个分支相比，"少了一个黑色的结点"
*
*图3
*       x_parent              x_parent->parent
*       /   \                   /           \
*      x     w     -->        x_parent       w_new
*     / \   / \               / \
*    ?   ? ?b  ?b            ?   ?
*假如?b ?b均为"黑" w也为黑 则把 w涂成红  此时x分支与w分支"黑层数"相同 , 
*(x_parent有可能为红，但这不影响结果,因为在下一个循环中,x = x_parent,循环将退出,x即x_parent将被涂成黑,不违反红黑树规则)
*以x = x_parent比 w = w_new这个分支"少了一层" 持续向上迭代 (x = x_parent x_parent = x->parent) 至到根节点为至,即完成了删除工作，并保证了红黑树的平衡
*
*如果w为红,通过旋转，可以演化成图3的情况
*演化步骤如下:
*把w涂成黑色,x_parent涂成红色(根据红黑树定义x_parent必为黑色, w的左右子节点必为黑色)
*以x_parent为轴左旋
*                   w 
*                  / \
*          x_parent    ?b 
*          /    \
*         x     ?b = w_new(必为黑)
*        / \
*       ?   ?
*  x 分支比 ?b分支少了一层
*
* 即，不管w为红还是为黑,最终都可以演化成w为黑的情况
*
*w的子节点中有红色节点的情况
*这种情况可以考虑把w的红色节点转移到x分支，作为x分支的根节点，并涂成黑色，即完成了删除，并保证了红黑树的平衡
*具体变换如下 如果a不为红，可以经过旋转变换为红
*
*     x_parent?
*      /      \
*     x        w黑      
*    / \      / \
*   ?   ?    黑b 红a
*
*              w?
*             /  \
*      x_parent黑 黑a
*     /  \
*    x   黑b
*即完成了删除，并保证了红黑树的平衡性
*
*/
static __INLINE__ myrbtree_node_t * rbtree_inter_rebalance_for_erase(/*myrbtree_t * rbtree*/myrbtree_node_t ** root, myrbtree_node_t * node)
{
	myrbtree_node_t * x = NULL;
	myrbtree_node_t * x_parent = NULL;
	myrbtree_node_t * y = node;

	assert(node && root);
	
	if(NULL == node->left)
		x = node->right;
	else if(NULL == node->right)
		x = node->left;
	else
	{
		//如果node不是叶子结点，则寻找右子树中最"左"边的那个节点替代node
		y = node->right;
		while(y->left)
			y = y->left;

		x = y->right;
	}

	//要删除的节点左右孩子都不为空,y与node 互换
	if(y != node)
	{
		//颜色互换
		rbtree_colour colour = y->colour;
		y->colour = node->colour;
		node->colour = colour;

		if(node->parent)
		{
			if(node == node->parent->left)
				node->parent->left = y;
			else
				node->parent->right = y;
		}
		else if(node == *root)
			*root = y;
		else
			assert(0);//如果走到这一步 bug here

		if(node->left)
			node->left->parent = y;

		//如果y是node的右孩子
		if(y == node->right)
		{
			x_parent = y;
		}
		else
		{
			if(node->right)
				node->right->parent = y;

			assert(y->parent);
			x_parent = y->parent;

			if(y == x_parent->left)
				x_parent->left = x;
			else
				assert(0);//x_parent->right = x; //y不可能是x_parent的右孩子 如果走到这一步,bug

			y->right = node->right;
		}

		y->parent = node->parent;
		y->left = node->left;

		y = node;
	}
	else//y就是要删除的节点，不必做替换，且y必有一孩子节点为空
	{
		//如果要删除的是根节点
		if(y == *root)
		{
			*root = x;
			if(*root)
			{
				(*root)->colour = rbtree_colour_black;
				(*root)->parent = NULL;
			}

			assert(NULL == *root || NULL == (*root)->parent);

			return y;
		}
		else
		{
			assert(y->parent);

			x_parent = y->parent;
			if(y == x_parent->left)
				x_parent->left = x;
			else
				x_parent->right = x;
		}
	}

	assert(x_parent);	

	if(x)
		x->parent = x_parent;

	//转化成
	//*      a                         a
	//*     / \                       / \
	//*    ?   z                     ?   y
	//*       / \       ---->           / \ 
	//*      ?   b                     ?   b
	//*         / \                       / \
	//*        y   ?            del ---> z   ?
	//*         \                         \
	//*          ?1                        ?1

	//如果要删除的节点为红色，函数返回
	if(y->colour == rbtree_colour_red)
	{
		assert(NULL == *root || NULL == (*root)->parent);
		return y;
	}

	while((x != *root) && (x == NULL || rbtree_colour_black == x->colour))
	{
		assert(x_parent);

		if(x == x_parent->left)
		{
			myrbtree_node_t * w = x_parent->right;
			assert(w);//x分支为0/1个黑结点,w分支至少有一个黑结点,所以w分支不可能为null,

			//如果w是红，需要进行转换,
			if(rbtree_colour_red == w->colour)
			{
				//x_parent必定是黑色的,且w的两个子节点必不空，且一定为黑色
				assert(rbtree_colour_black == x_parent->colour);
				assert(w->left && rbtree_colour_black == w->left->colour);
				assert(w->right && rbtree_colour_black == w->right->colour);

				w->colour = rbtree_colour_black;
				x_parent->colour = rbtree_colour_red;

				//旋转
				rbtree_inter_rotate_left(root, w);

				w = x_parent->right;
			}

			//x分支比w分支"少了一层",且x,w均为黑
			assert(w);

			//如果w的左右子节点均为黑
			if( (NULL == w->left || rbtree_colour_black == w->left->colour) &&
				(NULL == w->right || rbtree_colour_black == w->right->colour) )
			{
				//x_parent有可能为红，但这不影响结果,因为在下一个循环中,x = x_parent,循环将退出,x即x_parent将被涂成黑,不违反红黑树规则
				w->colour = rbtree_colour_red;
				x = x_parent;
				x_parent = x->parent;
				continue;
			}

			//如果至少有一个子节点为红, 通过旋转变换,让为红的那个节点始终为右节点
			if(NULL == w->right || rbtree_colour_black == w->right->colour)
			{
				assert(w->left && rbtree_colour_red == w->left->colour);//根据逻辑得出,必为不空,且必为红色
				
				w->left->colour = rbtree_colour_black;
				w->colour = rbtree_colour_red;
				rbtree_inter_rotate_right(root, w->left);
				w = x_parent->right;
			}

			//现在演变成这种情况
			//*     x_parent?
			//*      /      \
			//*     x        w黑      
			//*    / \      / \
			//*   ?   ?    ?b 红a
			assert(w->right && rbtree_colour_red == w->right->colour);//根据逻辑,这个条件必成立

			//旋转,完成了平衡的工作,变换过程如下图
			//*     x_parent?
			//*      /      \
			//*     x        w黑      
			//*    / \      / \
			//*   ?   ?    黑b 红a
			//*
			//*              w?
			//*             /  \
			//*      x_parent黑 黑a
			//*     /  \
			//*    x   黑b
			w->colour = x_parent->colour;
			x_parent->colour = rbtree_colour_black;
			w->right->colour = rbtree_colour_black;
			rbtree_inter_rotate_left(root, w);
			break;
		}
		else//x 是 x_parent的右孩子,操作与x == x_parent->left相同,但左右相反
		{
			myrbtree_node_t * w = x_parent->left;
			assert(w);//x分支为0/1个黑结点,w分支至少有一个黑结点,所以w分支不可能为null,

			//如果w是红，需要进行转换,
			if(rbtree_colour_red == w->colour)
			{
				//x_parent必定是黑色的,且w的两个子节点必不空，且一定为黑色
				assert(rbtree_colour_black == x_parent->colour);
				assert(w->left && rbtree_colour_black == w->left->colour);
				assert(w->right && rbtree_colour_black == w->right->colour);

				w->colour = rbtree_colour_black;
				x_parent->colour = rbtree_colour_red;

				//旋转
				rbtree_inter_rotate_right(root, w);

				w = x_parent->left;
			}

			//x分支比w分支"少了一层",且x,w均为黑
			assert(w);

			//如果w的左右子节点均为黑
			if( (NULL == w->left || rbtree_colour_black == w->left->colour) &&
				(NULL == w->right || rbtree_colour_black == w->right->colour) )
			{
				//x_parent有可能为红，但这不影响结果,因为在下一个循环中,x = x_parent,循环将退出,x即x_parent将被涂成黑,不违反红黑树规则
				w->colour = rbtree_colour_red;
				x = x_parent;
				x_parent = x->parent;
				continue;
			}

			//如果至少有一个子节点为红, 通过旋转变换,让为红的那个节点始终为右节点
			if(NULL == w->left || rbtree_colour_black == w->left->colour)
			{
				assert(w->right && rbtree_colour_red == w->right->colour);//根据逻辑得出,必为不空,且必为红色
				
				w->right->colour = rbtree_colour_black;
				w->colour = rbtree_colour_red;
				rbtree_inter_rotate_left(root, w->right);
				w = x_parent->left;
			}

			assert(w->left && rbtree_colour_red == w->left->colour);//根据逻辑,这个条件必成立

			w->colour = x_parent->colour;
			x_parent->colour = rbtree_colour_black;
			w->left->colour = rbtree_colour_black;
			rbtree_inter_rotate_right(root, w);
			break;
		}
	}

	if(x) 
		x->colour = rbtree_colour_black;

	//assert(!rbtree_inter_ismynode(rbtree->root, y));
	assert(NULL == (*root) || NULL == (*root)->parent);

	return y;
}

static __INLINE__ void rbtree_inter_del(myrbtree_t * rbtree, myrbtree_node_t ** root, myrbtree_node_t * node, void ** key, void ** data)
{
	assert(rbtree && node && root);

	//旋转平衡红黑树
	node = rbtree_inter_rebalance_for_erase(root, node);

	if(NULL == node)
		return;

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

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

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

static __INLINE__ 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 __INLINE__ 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 __INLINE__ 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;