不多说啥了,这里不讲理论,需要的可以自己去看书(如算法导论等),就给出一份实现代码,供有需要的人参考之用,前后写了好久,参考的是linux内核中红黑树的实现代码:http://lxr.linux.no/linux/lib/rbtree.c
实现的操作有:插入,查找,删除.
/*-----------------------------------------------------------
RB-Tree的插入和删除操作的实现算法
参考资料:
1)<<Introductiontoalgorithm>>
2)http://lxr.linux.no/linux/lib/rbtree.c
作者：http://www.cppblog.com/converse/
您可以自由的传播，修改这份代码，转载处请注明原作者
红黑树的几个性质:
1)每个结点只有红和黑两种颜色
2)根结点是黑色的
3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
4)如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
5)对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
的数目相同
-------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedefintkey_t;
typedefintdata_t;
typedefenumcolor_t
{
RED=0,
BLACK=1
}color_t;
typedefstructrb_node_t
{
structrb_node_t*left,*right,*parent;
key_tkey;
data_tdata;
color_tcolor;
}rb_node_t;
/*forwarddeclaration*/
rb_node_t*rb_insert(key_tkey,data_tdata,rb_node_t*root);
rb_node_t*rb_search(key_tkey,rb_node_t*root);
rb_node_t*rb_erase(key_tkey,rb_node_t*root);
intmain()
{
inti,count=900000;
key_tkey;
rb_node_t*root=NULL,*node=NULL;
srand(time(NULL));
for(i=1;i<count;++i)
{
key=rand()%count;
if((root=rb_insert(key,i,root)))
{
printf("[i=%d]insertkey%dsuccess!/n",i,key);
}
else
{
printf("[i=%d]insertkey%derror!/n",i,key);
exit(-1);
}
if((node=rb_search(key,root)))
{
printf("[i=%d]searchkey%dsuccess!/n",i,key);
}
else
{
printf("[i=%d]searchkey%derror!/n",i,key);
exit(-1);
}
if(!(i%10))
{
if((root=rb_erase(key,root)))
{
printf("[i=%d]erasekey%dsuccess/n",i,key);
}
else
{
printf("[i=%d]erasekey%derror/n",i,key);
}
}
}
return0;
}
staticrb_node_t*rb_new_node(key_tkey,data_tdata)
{
rb_node_t*node=(rb_node_t*)malloc(sizeof(structrb_node_t));
if(!node)
{
printf("mallocerror!/n");
exit(-1);
}
node->key=key,node->data=data;
returnnode;
}
/*-----------------------------------------------------------
|noderight
|//==>//
|arightnodey
|////
|byab
-----------------------------------------------------------*/
staticrb_node_t*rb_rotate_left(rb_node_t*node,rb_node_t*root)
{
rb_node_t*right=node->right;
if((node->right=right->left))
{
right->left->parent=node;
}
right->left=node;
if((right->parent=node->parent))
{
if(node==node->parent->right)
{
node->parent->right=right;
}
else
{
node->parent->left=right;
}
}
else
{
root=right;
}
node->parent=right;
returnroot;
}
/*-----------------------------------------------------------
|nodeleft
|////
|lefty==>anode
|////
|abby
-----------------------------------------------------------*/
staticrb_node_t*rb_rotate_right(rb_node_t*node,rb_node_t*root)
{
rb_node_t*left=node->left;
if((node->left=left->right))
{
left->right->parent=node;
}
left->right=node;
if((left->parent=node->parent))
{
if(node==node->parent->right)
{
node->parent->right=left;
}
else
{
node->parent->left=left;
}
}
else
{
root=left;
}
node->parent=left;
returnroot;
}
staticrb_node_t*rb_insert_rebalance(rb_node_t*node,rb_node_t*root)
{
rb_node_t*parent,*gparent,*uncle,*tmp;
while((parent=node->parent)&&parent->color==RED)
{
gparent=parent->parent;
if(parent==gparent->left)
{
uncle=gparent->right;
if(uncle&&uncle->color==RED)
{
uncle->color=BLACK;
parent->color=BLACK;
gparent->color=RED;
node=gparent;
}
else
{
if(parent->right==node)
{
root=rb_rotate_left(parent,root);
tmp=parent;
parent=node;
node=tmp;
}
parent->color=BLACK;
gparent->color=RED;
root=rb_rotate_right(gparent,root);
}
}
else
{
uncle=gparent->left;
if(uncle&&uncle->color==RED)
{
uncle->color=BLACK;
parent->color=BLACK;
gparent->color=RED;
node=gparent;
}
else
{
if(parent->left==node)
{
root=rb_rotate_right(parent,root);
tmp=parent;
parent=node;
node=tmp;
}
parent->color=BLACK;
gparent->color=RED;
root=rb_rotate_left(gparent,root);
}
}
}
root->color=BLACK;
returnroot;
}
staticrb_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;
while((!node||node->color==BLACK)&&node!=root)
{
if(parent->left==node)
{
other=parent->right;
if(other->color==RED)
{
other->color=BLACK;
parent->color=RED;
root=rb_rotate_left(parent,root);
other=parent->right;
}
if((!other->left||other->left->color==BLACK)&&
(!other->right||other->right->color==BLACK))
{
other->color=RED;
node=parent;
parent=node->parent;
}
else
{
if(!other->right||other->right->color==BLACK)
{
if((o_left=other->left))
{
o_left->color=BLACK;
}
other->color=RED;
root=rb_rotate_right(other,root);
other=parent->right;
}
other->color=parent->color;
parent->color=BLACK;
if(other->right)
{
other->right->color=BLACK;
}
root=rb_rotate_left(parent,root);
node=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;
}
returnroot;
}
staticrb_node_t*rb_search_auxiliary(key_tkey,rb_node_t*root,rb_node_t**save)
{
rb_node_t*node=root,*parent=NULL;
intret;
while(node)
{
parent=node;
ret=node->key-key;
if(0<ret)
{
node=node->left;
}
elseif(0>ret)
{
node=node->right;
}
else
{
returnnode;
}
}
if(save)
{
*save=parent;
}
returnNULL;
}
rb_node_t*rb_insert(key_tkey,data_tdata,rb_node_t*root)
{
rb_node_t*parent=NULL,*node;
parent=NULL;
if((node=rb_search_auxiliary(key,root,&parent)))
{
returnroot;
}
node=rb_new_node(key,data);
node->parent=parent;
node->left=node->right=NULL;
node->color=RED;
if(parent)
{
if(parent->key>key)
{
parent->left=node;
}
else
{
parent->right=node;
}
}
else
{
root=node;
}
returnrb_insert_rebalance(node,root);
}
rb_node_t*rb_search(key_tkey,rb_node_t*root)
{
returnrb_search_auxiliary(key,root,NULL);
}
rb_node_t*rb_erase(key_tkey,rb_node_t*root)
{
rb_node_t*child,*parent,*old,*left,*node;
color_tcolor;
if(!(node=rb_search_auxiliary(key,root,NULL)))
{
printf("key%disnotexist!/n");
returnroot;
}
old=node;
if(node->left&&node->right)
{
node=node->right;
while((left=node->left)!=NULL)
{
node=left;
}
child=node->right;
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;
}
if(node->parent==old)
{
parent=node;
}
node->parent=old->parent;
node->color=old->color;
node->right=old->right;
node->left=old->left;
if(old->parent)
{
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;
}
}
else
{
if(!node->left)
{
child=node->right;
}
elseif(!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);
}
returnroot;
}
分享到：
相关推荐
本篇文章将深入探讨红黑树的基本概念、特性、以及C语言实现的关键点。 **红黑树的性质** 1. **每个节点都带有颜色属性，要么是红色要么是黑色。** 2. **根节点是黑色。** 3. **所有叶子节点（NIL或空节点）都是...
红黑树的C语言实现，附加了顺序统计域，思想源自《算法导论》第三版ch13伪代码，基于的具体问题为：学校举办了一个在线ACM比赛，快速实现榜单的插入、删除、第k小查询
红黑树的c实现源码与剖析 原作者：那谁 源码剖析作者：July ===================== July说明： 由于原来的程序没有任何一行注释，我把它深入剖析，并一行一行的添加了注释， 详情请参见此文： 教你彻底实现红黑树：...
红黑树的C语言实现中，`RBTree` 结构体定义了一个节点，包含了指针到父节点、左子节点、右子节点，以及节点的键值和颜色。颜色枚举类型`NODECOLOR`定义了黑色和红色。`RB_InsertNode`函数用于插入新节点，`RB_Insert...
基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序源码+详细注释+exe执行程序.zip数据结构课程作业-基于C语言实现了红黑树及用户测试程序...
本资源“若干平衡树的C语言实现_C语言_平衡树_源码.zip”包含了一些平衡树算法的C语言实现，对于学习数据结构、算法以及C语言编程的开发者来说是非常有价值的。 首先，平衡树的主要目的是解决二叉搜索树（BST）在...
"数据结构C语言版严蔚敏完整源码"是一个包含严蔚敏教授编著的《数据结构》一书的C语言实现代码库，对于学习和理解数据结构有着极高的参考价值。 首先，严蔚敏的《数据结构》是中国计算机教育的经典教材，书中详细...
C语言是一种强大的、低级的编程语言，适合实现底层的数据操作，因此，C语言版的数据结构源码是学习和理解数据结构的理想工具。清华大学出版社的这本教材，通常以其严谨性和深度而闻名，其配套源码提供了丰富的实践...
### 红黑树C语言实现详解 #### 一、红黑树简介 红黑树是一种自平衡二叉查找树，其每个节点除了包含基本的二叉树节点信息（如左子节点、右子节点、父节点等）外，还包含了一个颜色属性，用于在插入和删除操作后重新...
4. **树**：二叉树、平衡树（如AVL树和红黑树）等，源码将涵盖插入、删除、查找等基本操作，以及树的遍历算法。 5. **图**：邻接矩阵和邻接表的实现，以及图的遍历算法（深度优先搜索DFS和广度优先搜索BFS）。 6. ...
《数据结构（C语言版）》是由著名计算机科学家严蔚敏教授编著的一本经典教材，这本书深入浅出地介绍了各种常用的数据结构及其在C语言中的实现。 在C语言中实现数据结构，可以更好地理解底层的内存管理和算法执行...
在C语言中实现红黑树，通常会包含两个核心文件：rbtree.c和rbtree.h。 **rbtree.c** 文件是红黑树的具体实现，可能包含了红黑树节点的定义、插入、删除、旋转等操作的函数。这些函数通常包括： 1. **节点定义**：...
《严版C语言版》数据结构源码是一个珍贵的学习资源，包含了数据结构这一核心计算机科学概念的实现。这本书以其严谨的讲解和清晰的C语言代码示例，深受程序员和计算机科学学生的喜爱。数据结构是理解和解决复杂计算...
总的来说，这个C语言实现的树数据结构源码涵盖了数据结构的基础知识，包括树的定义、节点结构、基本操作以及高级平衡树的概念。通过学习和理解这段代码，学生可以深入理解树数据结构的工作原理，并为今后的算法和...
除此之外，还有红黑树、AVL树等自平衡二叉树，它们通过保持树的平衡来确保高效的查找性能。 4. **图结构**：图由顶点和边组成，可以用来表示复杂的网络关系。图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS...
学习数据结构C语言版源码，建议先理解每种数据结构的概念和特性，然后逐步分析源码，结合实例运行调试，最后尝试自己设计和实现新的数据结构，以巩固理论知识并提升编程技能。 7. **进阶研究**： 在掌握了基础...
常见的树有二叉树、平衡二叉树（如AVL树、红黑树）、堆（优先队列）等。在C语言中，通过结构体定义节点，包含数据和多个子节点的指针。 5. **图** 图由顶点和边组成，表示对象间的关系。图可以是无向的，也可以是...
第三部分可能深入到树和二叉树的实现，包括二叉搜索树、平衡树（AVL树、红黑树）等。这些数据结构对于排序、查找和关联操作非常有用。例如，二叉搜索树可以快速地进行插入、删除和查找操作，而平衡树则保证了在频繁...