数据结构之红黑树C源码实现与剖析

前言

    红黑树作为一种经典而高级的数据结构，相信已经被不少人实现过，但是因为程序不够完善而无法运行，就是因为程序完全没有注释，初学者根本就看不懂。——这句话相对赞

    此份红黑树的C源码最初从linux-lib-rbtree.c而来，后经一网友那谁（http://www.cppblog.com/converse/）用C写了出来。在此，向原作者表示敬意。但原来的程序没有任何一行注释。没有一行注释的程序，令程序的价值大打折扣。

    所以，特把这份源代码在VC6.0上，一行一行的完善，一行一行的给它添加注释。至此，红黑树C带注释源码，就摆在了您的眼前，如有不妥、不正之处，还望不吝指正。

一、红黑树C语言源码实现

//------------------------------------------------------------------------------------------------- 
#include  
#include  
#include 
#include  

typedef int key_t; 
typedef int data_t; 

typedef enum color_t 
{ 
    RED = 0, 
    BLACK =1 
}color_t; 

typedef struct rb_node_t 
{ 
    struct rb_node_t *left, *right, *parent; 	
    key_t key; 					//这个是关键值
    data_t data;				//这个是标号
    color_t color; 
}rb_node_t; 

/*forward declaration */ 

/*插入结点*/
rb_node_t *rb_insert(key_t key, data_t data, rb_node_t *root); 

/*查找结点*/
rb_node_t *rb_search(key_t key, rb_node_t *root); 

/*释放结点*/
rb_node_t *rb_erase(key_t key, rb_node_t *root); 

int main() 
{ 
	
	int i, count = 7; 
	key_t key; 
	rb_node_t *root = NULL;
	rb_node_t *node =NULL; 
	
	srand(time(NULL)); 
	
	for(i = 1; i < count; ++i) 
	{ 
		key = rand() % count; 
		
		if((root = rb_insert(key , i, root))) 
		{ 
			
			printf("[i = %d] insert key %d success!\\n", i, key); 
		} 
		else 			
		{ 
			printf("[i = %d] insert key %d error!\\n", i, key); 	
			exit(-1); 
		} 	
		if((node = rb_search(key,root))) 
		{ 	
			printf("[i = %d] search key %d success!\\n",i, key); 
		} 		
		else 
		{ 			
			printf("[i = %d] search key %d error!\\n",i, key); 			
			exit(-1); 
		} 
		
		if (!(i % 5)) 
		{ 
			
			if((root = rb_erase(key,root))) 	
			{ 
				printf("[i = %d] erase key %d success\\n", i, key); 	
			} 	
			else 
			{ 
				printf("[i = %d] erase key %d error\\n", i, key); 		
			} 
		} 
	} 
	
	return 0; 
} 

static rb_node_t *rb_new_node(key_t key, data_t data) 
{ 
	rb_node_t *node = (rb_node_t*)malloc(sizeof(struct rb_node_t)); 
	
	if(!node) 
	{ 	
		printf("malloc error!\\n"); 
		exit(-1); 
	} 

	node->key = key;
	node->data = data; 
	
	return node; 
} 

/*----------------------------------------------------------- 
|  node                  right 

|  /\\         ==>         /\\ 
|  a right             node y 
  
|      /\\              /\\ 
	
|      b y            a  b        //原程序给的这丁点注释错了，我已修正。 
-----------------------------------------------------------*/ 
/* 左旋转代码 */
static rb_node_t *rb_rotate_left(rb_node_t *node, rb_node_t *root) 
{ 
	
	rb_node_t *right = node->right;			//指定指针指向right
	
	if((node->right = right->left)) 		//将right的左孩子结点 挂接 给node的右孩子
	{ 
		right->left->parent = node;		//node成为right左孩子的父母结点
	} 
	
	right->left= node;				//node成为right的左孩子
	
	if((right->parent = node->parent))		//判断node不为根结点
	{ 	
		if(node == node->parent->right)		//node为父亲结点的右孩子		
		{ 
			node->parent->right = right; 
		} 		
		else					//node为父亲结点的左孩子
		{ 
			node->parent->left = right;					
		} 
	} 
	else 		
	{ 
		root = right; 				//如果node为根结点	
	} 
	node->parent = right;			        //right成为node的父母
	
	return root; 
} 

/*----------------------------------------------------------- 

|       node                 left 
|        /\\                  /\\ 
  
|     left y  ==>          a  node 
|	   /\\                      /\\ 
	
|     a  b                    b  y //右旋与左旋差不多，分析略过 
	  
-----------------------------------------------------------*/ 
/* 右旋代码 */
static rb_node_t *rb_rotate_right(rb_node_t *node, rb_node_t *root) 
{ 
	rb_node_t *left = node->left;			//指定指针指向left
	
	if ((node->left = left->right))			//将left的右孩子赋值给node的左孩子，且left的右孩子不为空
	{ 	
		left->right->parent = node;		//node成为left右孩子的父亲结点
	} 
	
	left->right = node;				//node成为left的右孩子
	
	if((left->parent = node->parent)) 		//将left的父结点指向node的父结点，并且此时，node不为根结点	
	{ 
		if(node == node->parent->right)		//node为其父结点的右孩子			
		{ 
			node->parent->right = left; 			
		} 			
		else					//node为其父结点的左孩子
		{ 
			
			node->parent->left = left;	
			
		} 
	} 
	else 						//node为根结点	
	{ 
		root = left; 
	} 
	
	node->parent = left;				//left成为node的父结点
	
	return root; 
	
} 

//红黑树查找结点
//-------------------------------------------------------------
//rb_search_auxiliary：查找
//rb_node_t * rb_search：返回找到的结点
//-------------------------------------------------------------
static rb_node_t *rb_search_auxiliary(key_t key,rb_node_t *root,rb_node_t **save) 
{ 
	rb_node_t *node = root, *parent = NULL; 
	
	int ret; 
	
	while(node) 
	{ 
		parent = node; 
		ret = node->key - key; 
		if (0 < ret) 			//key 小于当前结点的key，所以，往其左子树查找
		{ 
			node = node->left; 
		} 
		else if (0 > ret)		//key 大于当前结点的key，所以，往其右子树查找
		{ 
			
			node = node->right; 
		} 
		else 	
		{ 
			return node;		//查找成功，返回
		} 
	} 

	if(save)					//
	{ 	
		*save= parent; 
	} 
	
	return NULL; 
} 

//返回上述rb_search_auxiliary查找结构
rb_node_t *rb_search(key_t key, rb_node_t *root) 
{ 	
	return rb_search_auxiliary(key, root, NULL); 
} 


/* 插入结点之后，重新调整红黑树的结构 */

//插入的三种情况，用z表示当前结点，p[z]表示父母，p[p[z]]表示祖父，y表示叔叔
static rb_node_t *rb_insert_rebalance(rb_node_t *node, rb_node_t *root) 
{ 
	rb_node_t *parent, *gparent, *uncle, *tmp; 
	
	//循环条件：parent为node的父结点且不为空，另外，node的父结点的颜色为红色时
	while((parent = node->parent) && (parent->color == RED)) 	
	{ 
		gparent = parent->parent;		
		
		if(parent == gparent->left)				        //当祖父的左孩子为父结点时
		{ 							       //其实上述几行语句，无非就是理顺孩子、父母、祖父的关系
			uncle = gparent->right;				        //定义叔叔的概念，叔叔y就是父母的右孩子
	
			if(uncle && uncle->color == RED) 	                //情况1：z的叔叔结点y是红色的（叔叔结点为红色，必须保证叔叔y不为NULL）	
			{ 			
				uncle->color = BLACK;			        //对策如下：a、b、c
				parent->color = BLACK;			        //a. 把node的父结点和叔叔结点涂黑
				    
				gparent->color = RED;			         //b. 把祖父结点涂红
				node = gparent;				         //c. 把当前结点指向祖父结点，即指针z在树中上移了两层哦
				
				//上述情况1只考虑了z的父结点为祖父的左孩子的情况
			} 		
			else						           //情况2：z的叔叔结点y是黑色的
			{ 				
				if(parent->right == node)		            //且z为右孩子
				{ 						    //对策如下：
					root = rb_rotate_left(parent, root);	    //当前结点的父结点作为新的当前结点
					tmp = parent;				    //以新的当前结点为支点左旋
					parent = node; 
					node = tmp; 
				} 
						//情况3：z的叔叔y是黑色的，此时z成为了左孩子
						//注意：1、情况3是由上述情况2变化而来的
						//......2、z的叔叔总是黑色的，否则就是情况1了
						//对策如下：a,b,c
				parent->color = BLACK;		                    //a. 父结点图为黑色
				
				gparent->color = RED;		                    //b. 祖父结点变为红色
				
				root = rb_rotate_right(gparent, root);             //c. 以祖父结点为支点右旋
			} 		
		} 
		else	//if(parent == gparent->right)，即当父结点为祖父结点的右孩子时
		{ 
			uncle = gparent->left;				            //祖父结点的左孩子作为叔叔结点
			
			if(uncle && uncle->color == RED)	                   //情况1：z的叔叔y是红色的
			{ 
				uncle->color = BLACK; 
				
				parent->color = BLACK; 
				gparent->color = RED; 
				node = gparent; 
				
			} 
			else 						            //情况2：z的叔叔y是黑色的
			{ 
				if(parent->left == node)		            //且z为左孩子
				{ 				
					root = rb_rotate_right(parent, root);        //右旋
					tmp = parent; 
					parent = node; 
					node = tmp;			             //互换角色
				} 
					//经过情况2的变化，成为了情况3.
				parent->color = BLACK;					
				
				gparent->color = RED; 
				root = rb_rotate_left(gparent, root); 
				
			} 
		} 
	} 
	
	root->color = BLACK;				                //根结点，不论怎么样，都得置为黑色
	
	return root;					                //返回根结点
} 

//红黑树插入结点
rb_node_t *rb_insert(key_t key, data_t data, rb_node_t *root) 
{ 
	
	rb_node_t *parent = NULL, *node; 
	
	parent = NULL; 
	if((node = rb_search_auxiliary(key, root, &parent)))             //调用rb_search_auxiliary查找到插入结点的地方
	{ 
		return root; 
	} 
	
	node = rb_new_node(key, data);				          //分配结点
	
	node->parent = parent;					          //初始化
	node->left = node->right = NULL; 
	node->color = RED; 
	
	if(parent) 						           //parent保存的是要插入结点的地方
	{ 	
		if(parent->key > key) 
		{ 
			parent->left = node; 
		} 
		else 
		{ 	
			parent->right = node; 
		} 
	} 	
	else 
	{ 		
		root = node; 
	} 
	
	return rb_insert_rebalance(node, root);		                    //插入结点后，调用rb_search_rebalance修复红黑树
} 

//红黑树的4种删除情况
/* 删除结点之后，重新调整红黑树的结构 */
//x表示要删除的结点，*other、w表示兄弟结点
static rb_node_t *rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root) 

{ 
	rb_node_t *other, *o_left, *o_right;                             //x的兄弟*other, 兄弟左孩子*o_left, 右孩子*o_right
	
	while((!node || node->color == BLACK) && node != root) 
	{ 		
		if(parent->left == node)		
		{ 		
			other = parent->right; 
			
			if(other->color == RED)			        //情况1：x的兄弟结点w是红色的
			{ 					        //对策如下
				other->color = BLACK;		        //a. 把兄弟结点染成黑色
				
				parent->color = RED;		        //b. 把父结点染成红色
				root = rb_rotate_left(parent, root);     //对p[x]进行左旋
				other = parent->right;		         //x的新兄弟结点new w 是旋转之前w的某个孩子。其实是左旋后的效果
			} 
			
			//情况2：x的兄弟结点w是黑色，且w的两个孩子全为黑色
			if((!other->left || other->left->color == BLACK) && (!other->right || other->right->color == BLACK)) 	
			{ 
								       //对策：把当前结点和兄弟结点中抽取出一重黑色追加到父结点上，把父结点当成新的当前结点
				other->color = RED;		        //a. 兄弟结点为红色
				node = parent;			        //b. 把父结点当作新的当前结点
				
				parent = node->parent; 
			} 
			else 
			{ 
				//情况3：x的兄弟结点w是黑色的，且w的左孩子是红色，右孩子为黑色
				if(!other->right || other->right->color == BLACK) 			
				{ 
					if((o_left = other->left)) 			//w和其左孩子left[w]，颜色互换	
					{ 
						o_left->color = BLACK;			//w的左孩子颜色由红->黑
					} 
					
					other->color = RED;				//兄弟结点w由黑->红
					root = rb_rotate_right(other, root);            //对w进行右旋，从而红黑性质恢复 
					
					other = parent->right;				//变化后，父结点的右孩子，作为新的兄弟结点
				} 
				
						//情况4：x的兄弟结点w是黑色的，兄弟结点的右孩子是红色
				other->color = parent->color;			        //a. 把兄弟结点染成当前结点父结点的颜色
				
				parent->color = BLACK;					//b. 把当前结点的父结点染成黑色
				if(other->right) 						
				{ 
					other->right->color = BLACK;		        //c. 兄弟结点的右孩子染成黑色
					
				} 
				
				root = rb_rotate_left(parent, root);	                //d. 以当前结点的父结点为支点进行左旋
				node =root;						//e. 把当前结点x置为根root
											//此时算法结束，红黑树所有性质调转正确
				
				break; 
			} 
		} 
		else 	//下面情况与上述情况，原理一致。分析略
		{ 
			
			other = parent->left; 
			if(other->color == RED) 			
			{ 
				other->color = BLACK; 
				
				parent->color = RED; 
				
				root = rb_rotate_right(parent, root); 
				other = parent->left; 			
			} 		
			if(( !other->left || other->left->color == BLACK) && ( !other->right || other->right->color == BLACK)) 
			{ 	
				other->color = RED; 
				node = parent; 
				parent = node->parent; 			
			} 
			else 
			{ 			
				if( !other->left || other->left->color == BLACK) 
				{ 				
					if((o_right = other->right)) 
					{ 
						o_right->color = BLACK; 
						
					} 
					other->color = RED; 
					
					root = rb_rotate_left(other, root); 
					other = parent->left; 
				} 
				
				other->color = parent->color; 
				parent->color = BLACK; 
				
				if(other->left) 
				{ 
					
					other->left->color = BLACK; 
					
				} 
				root = rb_rotate_right(parent, root); 
				
				node = root; 
				break; 
			} 
		} 
     } 
	 
     if(node)  
     { 
		 node->color =BLACK;  
     } 
	 
	 return root; 
} 

//红黑树的删除结点
rb_node_t *rb_erase(key_t key, rb_node_t *root) 
{ 
	
	rb_node_t *child, *parent, *old, *left, *node; 
	color_t color; 
	
	if(!(node = rb_search_auxiliary(key, root, NULL)))	//调用rb_search_auxiliary查找要删除的结点	
	{
		printf("key %d is not exist!\\n"); 
		return root; 
	} 
	
	old = node; 
	
	//删除结点有两个孩子结点
	//策略：可以选择把当前删除结点左子树中的最大元素或者是右子树中的最小元素放到放到待删除结点的位置
	if(node->left && node->right) 
	{ 
		node = node->right; 
		
		while((left = node->left) != NULL)			    //找到右子树的最小元素结点，保存到node中
		{ 
			node =left; 	
		} 
		child = node->right;						//child为node的右儿子，即node左儿子的兄弟结点				
		
		parent = node->parent;						//parent为node结点的父结点
		
		color = node->color;						//color保存的是node结点的color
		if(child) 							//node的右儿子不为空，则把其祖父结点作为父结点
		{ 
			child->parent = parent; 
		} 
		
		if(parent)							//如果node结点的父结点不为空，即不为根结点吧？
		{ 
			if(parent->left == node) 				//进行结点的移动，即将node的孩子结点挂接到node的父结点上	
			{ 
				parent->left = child; 
				
			} 
			else 
			{ 
				
				parent->right = child; 
			} 						      //同上
		} 
		else							       //node的父结点为根结点
		{ 
			root = child; 
		} 
		
		if(node->parent == old) 					//node的父结点等于要删除的结点
		{ 
			
			parent = node; 
		} 
		
		node->parent = old->parent;					//进行把右子树最小元素结点放到当前删除结点处的操作
		
		node->color = old->color;					
		
		node->right = old->right; 
		node->left = old->left; 
		
		if(old->parent) 					//如果当前删除结点的父结点存在，即old不为根结点
		{ 
			if(old->parent->left == old) 			//当前删除结点是其父结点的左孩子
			{ 
				old->parent->left = node; 
			} 		
			else 
			{ 	
				old->parent->right = node;		//当前删除结点是其父结点的右孩子
				
			} 
		} 		
		else 			
		{ 
			root = node;					//当前删除结点为根结点
		} 
		
		old->left->parent = node; 
		if(old->right) 	
		{ 
			old->right->parent = node; 
		} 		
	}//if(node->left && node->right) 
	
	else		//此else语句处理的是：删除结点没有儿子、只有一个儿子时的情况 		
	{ 
		if(!node->left)			//删除结点
		{ 
			
			child = node->right; 
		} 		
		else if(!node->right) 
		{ 
			child = node->left; 		
		} 
		parent = node->parent; 
		
		color = node->color; 
		
		if(child) 	
		{ 
			child->parent = parent; 
			
		} 
		if(parent) 			
		{ 
			
			if(parent->left == node) 
			{ 	
				parent->left = child; 
			} 		
			else 
			{ 
				parent->right = child; 		
			} 
		} 	
		else 
		{ 
			
			root = child; 
			
		} 
	} 
	
	free(old); 
	if(color == BLACK) 	
	{ 
		root= rb_erase_rebalance(child, parent, root); //调用rb_erase_rebalance来恢复红黑树性质
	} 
	
	return root; 
} 

    

    对于上面的代码注释，原注释代码作者已经做的非常的好了，我在前辈的基础上，做了部分修改，以及把前辈没有注释的部分代码，进行了相应的注释，希望不要有错误。
    对于上面的代码，通过前面两篇文章的基础，看起来基本上不费力气了，思想完全是按照前面介绍的原理来编写的，对于此份代码，以及红黑树系列作者的工作，我非常的钦佩，同时也非常的感谢。
    真的，对红黑树的这份代码，感觉写的非常的美，或许是自己还太差劲吧。

    加油，为了自己可以写出美丽的代码。

    

    

    参考：http://blog.csdn.net/v_JULY_v/article/details/6114226
    代码下载链接：rbtree.zip

                                                                                                                梦醒潇湘love

                                                                                                             2013-01-22 22:06