- 浏览: 586628 次
-
文章分类
最新评论
算法导论 之 红黑树 - 插入[C语言]
1 引言
2 性质分析
红黑树是一种二叉查找树，但在每个节点上增加一个存储位表示结点的颜色[RED或BLACK]。通过对任一结点到叶子结点的路径上各个结点着色方式的限制，确保没有一条路径会是其他路径的2倍，因而是接近平衡的！因此，它能保证在最坏情况下，基本的动态集合操作的时间复杂度为O(log2@N)[log2@N:以2为底数，N为对数]。[注：理论上平衡二叉树的性能要优于红黑树，但是仍处同一数量级]
图1 红黑树
红黑树有以下5种性质，所有对红黑树的处理都是围绕这5种性质进行的。但是想通过以下5种性质的简单描述就期望能够深入理解红黑树，这似乎是不太可能的事情。因此，下面将结合图1对其5种性质进行分别的解析。
①、每个节点要么是红色的，要么是黑色的；
解析：任何一个结点都有一种颜色 —— 非红即黑。从图1中可以清楚的看出这一点。
②、根结点是黑色的；
解析：根结点只能为黑色，不可能为红色。如图1中的根结点为13，其为黑色。
③、所有叶子结点（NIL）都是黑色的；
解析：在图1中的所有叶子结点（NIL）的颜色只能为黑色的，不可能为红色。
④、如果一个结点是红色，则它的两个儿子都是黑色的；
解析：如图1中的结点6、8、17、22、27为红色结点，其左右孩子结点只能为黑色。即：树中决不允许存在两个连续的红色结点。[注：但是允许两个连续的黑色结点]
⑤、对任何一个结点，从该结点通过其子孙结点到达叶子结点（NIL）的所有路径上包含相同数目的黑结点。
解析：以根结点为例，其通过子孙结点到达叶子节点（NIL）的路径有如下几种情况：
路径1：13(b) ->8(r)-> 1(b) -> 叶子(b) | 3个黑结点：13、1、叶子
路径2：13(b) ->8(r)-> 11(b) -> 叶子(b) | 3个黑结点：13、11、叶子
路径3：13(b) ->8(r)-> 1(b) ->6(r)-> 叶子(b) | 3个黑结点：13、1、叶子
路径4: 13(b) ->17(r)-> 25(b) ->22(r)-> 叶子(b) | 3个黑结点：13、25、叶子
路径5: 13(b) ->17(r)-> 25(b) ->27(r)-> 叶子(b) | 3个黑结点：13、25、叶子
路径6: 13(b) ->17(r)-> 15(b) -> 叶子(b) | 3个黑结点：13、15、叶子
....
至此，大家应该能够明白性质⑤的真实含义了。
为了便于处理红黑树代码的边界条件，我们采用一个哨兵来代表NIL。对于一个红黑树而言，哨兵NIL是一个与树内普通结点有相同域的对象。它的color域为BLACK，而其他域（parent，lchild，rchild和key）的值我们并不关心。
总之，红黑树是通过以上5种性质的限制约束了该树的平衡性能 —— 即：该树上的最长路径长度不可能大于最短路径长度的2倍，从而确保对树操作的时间复杂度达到O（log2@N）。
3 编码实现
3.1 结构定义
/* 常值定义 */ #define RBT_COLOR_BLACK 'b' /* 颜色：黑色 */ #define RBT_COLOR_RED 'r' /* 颜色：红色 */ #define RBT_LCHILD (0) /* 类型：左孩子 */ #define RBT_RCHILD (1) /* 类型：右孩子 */ #define RBT_MAX_DEPTH (512) /* 栈的深度(栈处理红黑树时使用) */
/* 结点结构 */
typedef struct _rbt_node_t
{
int key; /* 关键字 */
int color; /* 结点颜色: RBT_COLOR_BLACK(黑) 或 RBT_COLOR_RED(红) */
struct _rbt_node_t *parent; /* 父节点 */
struct _rbt_node_t *lchild; /* 左孩子节点 */
struct _rbt_node_t *rchild; /* 右孩子节点 */
}rbt_node_t;
/* 红黑树结构 */
typedef struct
{
rbt_node_t *root; /* 根节点 */
rbt_node_t *sentinel; /* 哨兵节点 */
}rbt_tree_t;
/* 错误码 */
typedef enum
{
RBT_SUCCESS /* 成功 */
, RBT_FAILED = ~0x7fffffff /* 失败 */
, RBT_NODE_EXIST /* 结点存在 */
}rbt_ret_e;
#define rbt_set_color(node, c) ((node)->color = (c))
#define rbt_set_red(node) rbt_set_color(node, RBT_COLOR_RED)
#define rbt_set_black(node) rbt_set_color(node, RBT_COLOR_BLACK)
#define rbt_is_red(node) (RBT_COLOR_RED == (node)->color)
#define rbt_is_black(node) (RBT_COLOR_BLACK == (node)->color)
/* 设置左孩子 */
#define rbt_set_lchild(tree, node, left) \
{ \
(node)->lchild = (left); \
if(tree->sentinel != left) \
{ \
(left)->parent = (node); \
} \
}
/* 设置右孩子 */
#define rbt_set_rchild(tree, node, right) \
{ \
(node)->rchild = (right); \
if(tree->sentinel != right) \
{ \
(right)->parent = (node); \
} \
}
/* 设置孩子节点 */
#define rbt_set_child(tree, node, type, child) \
{ \
if(RBT_LCHILD == type) \
{ \
rbt_set_lchild(tree, node, child); \
} \
else \
{ \
rbt_set_rchild(tree, node, child); \
} \
}
3.2 创建对象
/******************************************************************************
**函数名称: rbt_creat
**功 能: 创建红黑树对象(对外接口)
**输入参数: NONE
**输出参数: NONE
**返 回: 红黑树对象地址
**实现描述:
**注意事项:
** 1、每个结点要么是红色的，要么是黑色的；
** 2、根结点是黑色的；
** 3、所有叶子结点（NIL）都是黑色的；
** 4、如果一个结点是红色，则它的两个儿子都是黑色的；
** 5、对任何一个结点，从该结点通过其子孙结点到达叶子结点（NIL）
** 的所有路径上包含相同数目的黑结点。
**作 者: # Qifeng.zou # 2013.12.24 #
******************************************************************************/
rbt_tree_t *rbt_creat(void)
{
rbt_tree_t *tree = NULL;
tree = (rbt_tree_t *)calloc(1, sizeof(rbt_tree_t));
if(NULL == tree)
{
return NULL;
}
tree->sentinel = (rbt_node_t *)calloc(1, sizeof(rbt_node_t));
if(NULL == tree->sentinel)
{
free(tree);
return NULL;
}
tree->sentinel->color = RBT_COLOR_BLACK;
tree->root = tree->sentinel;
return tree;
}
3.3 旋转处理
/******************************************************************************
**函数名称: rbt_right_rotate
**功 能: 右旋处理
**输入参数:
** tree: 红黑树
** node: 旋转支点
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败
**实现描述:
** G G
** | |
** N -> L
** / \ / \
** L R LL N
** / \ / \ / \
** LL LR RL RR LR R
** / \
** RL RR
** 说明: 节点N为旋转支点
**注意事项:
**作 者: # Qifeng.zou # 2014.01.15 #
******************************************************************************/
void rbt_right_rotate(rbt_tree_t *tree, rbt_node_t *node)
{
rbt_node_t *parent = node->parent, *lchild = node->lchild;
if(tree->sentinel == parent)
{
tree->root = lchild;
lchild->parent = tree->sentinel;
}
else if(node == parent->lchild)
{
rbt_set_lchild(tree, parent, lchild);
}
else
{
rbt_set_rchild(tree, parent, lchild);
}
rbt_set_lchild(tree, node, lchild->rchild);
rbt_set_rchild(tree, lchild, node);
}
/******************************************************************************
**函数名称: rbt_left_rotate
**功 能: 左旋处理
**输入参数:
** tree: 红黑树
** node: 旋转支点
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败
**实现描述:
** G G
** | |
** N -> R
** / \ / \
** L R N RR
** / \ / \ / \
** LL LR RL RR L RL
** / \
** LL LR
** 说明: 节点N为旋转支点
**注意事项:
**作 者: # Qifeng.zou # 2014.01.15 #
******************************************************************************/
void rbt_left_rotate(rbt_tree_t *tree, rbt_node_t *node)
{
rbt_node_t *parent = node->parent, *rchild = node->rchild;
if(tree->sentinel == parent)
{
tree->root = rchild;
rchild->parent = tree->sentinel;
}
else if(node == parent->lchild)
{
rbt_set_lchild(tree, parent, rchild);
}
else
{
rbt_set_rchild(tree, parent, rchild);
}
rbt_set_rchild(tree, node, rchild->lchild);
rbt_set_lchild(tree, rchild, node);
}
3.4 插入操作
1）当向一棵空树中插入结点时，则新结点将作为整棵树根结点，且为黑色（性质2）；
图4 空树中添加根结点R
2）当向一棵非空树中插入一个结点时，新结点的颜色都是为红色。插入成功后，需要判断是否破坏了红黑树的5个性质。经过分析，可以发现，向非空树中插入一个结点，不可能破坏性质1、2、3、5，唯一可能被破坏只有性质4 —— 出现2个连续的红结点[新节点和父节点为红色]，且性质4被破坏，只有如下六种情况：
============================================================================
情况1）：叔结点U为红色
前提条件：新结点N和父结点P都为红色，父结点P为G的左孩子
情况描述：叔结点U为红色时[注：此时不必关心新结点N是左孩子还是右孩子]
处理过程：[代码：参考rb_insert_fixup()中的case 1]
①、将父结点P和叔结点U的颜色改为黑色，将祖父结点G改为红色
②、把祖父结点作为下一次判断的对象
图5 叔结点U为红色，新结点N为左孩子
图6 叔结点U为红色，新结点N为右孩子
情况2）：叔结点为黑色，新结点N为右孩子
前提条件：新结点N和父结点P都为红色，父结点P为G的左孩子
情况描述：叔结点U也为黑色，新结点N为右孩子时
处理过程：[代码：参考rb_insert_fixup()中的case 2]
①、调整颜色：将父结点P改为黑色，将祖父结点改为红色
②、向右旋转90度：父结点P取代祖父结点G的位置，同时将父结点的右子树PR作为祖父结点G的左子树，祖父结点G作为父结点P的右孩子
③、把祖父结点的父结点GP改为下一次判断的对象
图7 叔结点U为黑色，新结点N为左孩子
[注意：蓝色结点表示颜色可能为红，也可能为黑]
情况3）：叔结点为黑色，新结点N为右孩子
前提条件：新结点N和父结点P都为红色，父结点P为G的左孩子
情况描述：叔结点U也为黑色，新结点N为右孩子时
处理过程：[代码：参考rb_insert_fixup()中的case 3]
①、向左旋转90度：新结点N取代父结点P的位置，同时将新结点的左子树NL作为父结点P的右子树，父结点P作为新结点N的左孩子
②、把父结点P改为下一次判断的对象[注意：经过①、②、③处理后，情况3演变了情况2]
============================================================================
前提条件：新结点N和父结点P都为红色，父结点P为祖父G的右孩子
情况描述：叔结点U为红色时[注：此时不必关心新结点N是左孩子还是右孩子]
处理过程：[代码：参考rb_insert_fixup()中的case 4]
①、将父结点P和叔结点U的颜色改为黑色，将祖父结点G改为红色
②、把祖父结点作为下一次判断的对象
图9 叔结点U为红色 新结点N为右孩子
图10 叔结点U为红色 新结点N为左孩子
前提条件：新结点N和父结点P都为红色，父结点P为祖父结点G的右孩子
情况描述：叔结点U为黑色，新结点N为左孩子时
处理过程：[代码：参考rb_insert_fixup()中的case 5]
①、向右旋转90度：新结点N取代父结点G的位置，同时将新结点的右子树NR作为父结点G的左子树，父结点G作为新结点的右孩子
②、把父结点P改为下一次判断的对象[此时case 5演变为case 6]
前提条件：新结点N和父结点P都为红色，父结点P为G的右孩子
情况描述：叔结点U为黑色，新结点N为右孩子时
处理过程：[代码：参考rb_insert_fixup()中的case 6]
①、颜色调整：将祖父结点G改为红色，父结点P改为黑色
②、向左旋转90度：父结点P取代祖父结点G的位置，同时将父结点的左子树PL作为祖父结点G的右子树，祖父结点G作为父结点P的左孩子
③、把祖父结点的父结点GP改为下一次判断的对象
/******************************************************************************
**函数名称: rbt_creat_node
**功 能: 创建关键字为key的结点(内部接口)
**输入参数:
** key: 红黑树
** color: 结点颜色
** type: 新结点是父结点的左孩子还是右孩子
** parent: 父结点
**输出参数: NONE
**返 回: RB_SUCCESS:成功 RB_FAILED:失败
**实现描述:
**注意事项: 新结点的左右孩子肯定是叶子结点
**作 者: # Qifeng.zou # 2013.12.23 #
******************************************************************************/
rbt_node_t *rbt_creat_node(rbt_tree_t *tree, int key, int color, int type, rbt_node_t *parent)
{
rbt_node_t *node = NULL;
node = (rbt_node_t *)calloc(1, sizeof(rbt_node_t));
if(NULL == node)
{
return NULL;
}
node->color = color;
node->key = key;
node->lchild = tree->sentinel;
node->rchild = tree->sentinel;
if(NULL != parent)
{
rbt_set_child(tree, parent, type, node);
}
else
{
node->parent = tree->sentinel;
}
return node;
}
/******************************************************************************
**函数名称: rbt_insert
**功 能: 向红黑树中增加节点(对外接口)
**输入参数:
** tree: 红黑树
** key: 需被添加的关键字
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败 RBT_NODE_EXIST:节点存在
**实现描述:
** 1. 当根节点为空时，直接添加
** 2. 将节点插入树中, 检查并修复新节点造成红黑树性质的破坏
**注意事项:
** 红黑树的5点性质:
** 1、每个结点要么是红色的，要么是黑色的；
** 2、根结点是黑色的；
** 3、所有叶子结点(NIL)都是黑色的；
** 4、如果一个结点是红色，则它的两个儿子都是黑色的；
** 5、对任何一个结点，从该结点通过其子孙结点到达叶子结点(NIL)
** 的所有路径上包含相同数目的黑结点。
**注意事项: 插入节点操作只可能破坏性质(4)
**作 者: # Qifeng.zou # 2013.12.23 #
******************************************************************************/
int rbt_insert(rbt_tree_t *tree, int key)
{
rbt_node_t *node = tree->root,
*add = NULL, *parent = NULL;
/* 1. 当根节点为空时，直接添加 */
if(tree->sentinel == tree->root)
{
/* 性质2: 根结点是黑色的 */
tree->root = rbt_creat_node(tree, key, RBT_COLOR_BLACK, 0, NULL);
if(tree->sentinel == tree->root)
{
return RBT_FAILED;
}
return RBT_SUCCESS;
}
/* 2. 将节点插入树中, 检查并修复新节点造成红黑树性质的破坏 */
while(tree->sentinel != node)
{
if(key == node->key)
{
return RBT_NODE_EXIST;
}
else if(key < node->key)
{
if(tree->sentinel == node->lchild)
{
add = rbt_creat_node(tree, key, RBT_COLOR_RED, RBT_LCHILD, node);
if(NULL == add)
{
return RBT_FAILED;
}
return rb_insert_fixup(tree, add); /* 防止红黑树的性质被破坏 */
}
node = node->lchild;
}
else
{
if(tree->sentinel == node->rchild)
{
add = rbt_creat_node(tree, key, RBT_COLOR_RED, RBT_RCHILD, node);
if(NULL == add)
{
return RBT_FAILED;
}
return rb_insert_fixup(tree, add); /* 防止红黑树的性质被破坏 */
}
node = node->rchild;
}
}
return RBT_SUCCESS;
}
/******************************************************************************
**函数名称: rb_insert_fixup
**功 能: 插入操作修复(内部接口)
**输入参数:
** tree: 红黑树
** node: 新增节点的地址
**输出参数: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失败
**实现描述:
** 1. 检查红黑树性质是否被破坏
** 2. 如果被破坏，则进行对应的处理
**注意事项: 插入节点操作只可能破坏性质④
**作 者: # Qifeng.zou # 2013.12.23 #
******************************************************************************/
int rb_insert_fixup(rbt_tree_t *tree, rbt_node_t *node)
{
rbt_node_t *parent = NULL, *uncle = NULL, *grandpa = NULL, *gparent = NULL;
while(rbt_is_red(node))
{
parent = node->parent;
if(rbt_is_black(parent))
{
return RBT_SUCCESS;
}
grandpa = parent->parent;
if(parent == grandpa->lchild) /* 父节点为左节点 */
{
uncle = grandpa->rchild;
/* case 1: 父节点和叔节点为红色 */
if(rbt_is_red(uncle))
{
rbt_set_black(parent);
rbt_set_black(uncle);
if(grandpa != tree->root)
{
rbt_set_red(grandpa);
}
node = grandpa;
continue;
}
/* case 2: 叔结点为黑色，结点为左孩子 */
else if(node == parent->lchild)
{
/* 右旋转: 以grandpa为支点 */
gparent = grandpa->parent;
rbt_set_red(grandpa);
rbt_set_black(parent);
rbt_right_rotate(tree, grandpa);
node = gparent;
continue;
}
/* case 3: 叔结点为黑色，结点为右孩子 */
else
{
/* 左旋转: 以parent为支点 */
rbt_left_rotate(tree, parent);
node = parent;
continue;
}
}
else /* 父节点为右孩子 */
{
uncle = grandpa->lchild;
/* case 1: 父节点和叔节点为红色 */
if(rbt_is_red(uncle))
{
rbt_set_black(parent);
rbt_set_black(uncle);
if(grandpa != tree->root)
{
rbt_set_red(grandpa);
}
node = grandpa;
continue;
}
/* case 2: 叔结点为黑色，结点为左孩子 */
else if(node == parent->lchild)
{
/* 右旋转: 以parent为支点 */
rbt_right_rotate(tree, parent);
node = parent;
continue;
}
/* case 3: 叔结点为黑色，结点为右孩子 */
else
{
/* 左旋转: 以grandpa为支点 */
gparent = grandpa->parent;
rbt_set_black(parent);
rbt_set_red(grandpa);
rbt_left_rotate(tree, grandpa);
node = gparent;
continue;
}
}
}
return RBT_SUCCESS;
}
3.4 结果展示
发表评论
相关推荐
c语言常用算法-----列举C语言各种常用算法，详尽。对编程大有裨益！
红黑树的C语言实现 算法导论的红黑树C实现
根据算法导论中红黑树的讲解，用C写了一个关于红黑树的建立，查询节点，插入，删除操作
RAS加密算法的----——————-C语言实现
算法导论的红黑树的C++实现源码,并附加测试验证代码
操作系统实验报告--C语言实现银行家算法.doc
经典的LZW算法----C语言实现.txt
算法导论思考题 6-3 young氏矩阵生成，提取最小，插入，查询实现c语言代码，作者亲测，运行效果良好。
中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部
实验1：实现红黑树的基本算法， 对n的取值分别为 12、24、36、48、60，随机生成n 个互异的正整数（K1, K2, K3, ……, Kn）作为节点的关键字，向一棵初始空的红黑树中依次插入这n 个节点，统计算法运行所需时间 ，画...
数据结构与算法分析---C语言描述 作者：Mark Allen Weiss
时间片轮转算法和优先级调度算法-C语言模拟实现-收藏.doc
各类排序算法整理--C语言描述--本人编写 排序算法种类有： 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
自己写的b-树模板,已通过800万个数据测试,用的结构是算法导论上的,严渭敏树上的3叉树是2-3树,做删除操作比较麻烦,而算法导论上的是2-3-4树,可以方便实现删除.
红黑树的完整代码实现。按照算法导论给出的算法。附二叉查找树的完整代码。纯C语言实现。
数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构与...
数据结构与算法分析--C语言描述 内容不错
高级数据结构及其实现12.1 自顶向下伸展树12.2 红黑树12.2.1 自底向上插入12.2.2 自顶向下红黑树12.2.3 自顶向下删除12.3 确定性跳跃表12.4 AA-树12.5 treap树12.6 k-d树12.7 配对堆总结练习参考文献索引
操作系统课设-基于C语言实现调度算法以及多进程模拟和测试源码.zip操作系统课设-基于C语言实现调度算法以及多进程模拟和测试源码.zip操作系统课设-基于C语言实现调度算法以及多进程模拟和测试源码.zip操作系统课设-...
数据结构与算法分析--C语言描述(英文第2版)