算法导论之红黑树-插入[C语言]

1、算法导论 之 红黑树 - 插入C语言1 引言 在之前的博文中，本人对平衡二叉树的处理做了较详尽的分析，有兴趣的朋友可以参阅博文算法导论 之 平衡二叉树 - 创建 插入 搜索 销毁和算法导论 之 平衡二叉树 - 删除。平衡二叉树AVL是严格的平衡树，在增删结点时，其旋转操作的次数较多；而红黑树RBT则通过非严格的平衡来换取增删结点时旋转次数的降低。在应用中，如果搜索次数大于增删次数，则选择平衡二叉树更好一些；而如果搜索与增删次数接近时，红黑树则是更好的选择。在有些资料中显示，红黑树的统计性能要优于平衡二叉树。2 性质分析红黑树是一种二叉查找树，但在每个节点上增加一个存储位表示结点的颜色RED或B

2、LACK。通过对任一结点到叶子结点的路径上各个结点着色方式的限制，确保没有一条路径会是其他路径的2倍，因而是接近平衡的！因此，它能保证在最坏情况下，基本的动态集合操作的时间复杂度为O(log2N)log2N:以2为底数，N为对数。注：理论上平衡二叉树的性能要优于红黑树，但是仍处同一数量级红黑树有以下5种性质，所有对红黑树的处理都是围绕这5种性质进行的。但是想通过以下5种性质的简单描述就期望能够深入理解红黑树，这似乎是不太可能的事情。因此，下面将结合图1对其5种性质进行分别的解析。 、每个节点要么是红色的，要么是黑色的； 解析：任何一个结点都有一种颜色 非红即黑。从图1中可以清楚的看出这一点。

3、、根结点是黑色的； 解析：根结点只能为黑色，不可能为红色。如图1中的根结点为13，其为黑色。 、所有叶子结点（NIL）都是黑色的； 解析：在图1中的所有叶子结点（NIL）的颜色只能为黑色的，不可能为红色。 、如果一个结点是红色，则它的两个儿子都是黑色的； 解析：如图1中的结点6、8、17、22、27为红色结点，其左右孩子结点只能为黑色。即：树中决不允许存在两个连续的红色结点。注：但是允许两个连续的黑色结点 、对任何一个结点，从该结点通过其子孙结点到达叶子结点（NIL）的所有路径上包含相同数目的黑结点。 解析：以根结点为例，其通过子孙结点到达叶子节点（NIL）的路径有如下几种情况：至此，大家应该

4、能够明白性质的真实含义了。 为了便于处理红黑树代码的边界条件，我们采用一个哨兵来代表NIL。对于一个红黑树而言，哨兵NIL是一个与树内普通结点有相同域的对象。它的color域为BLACK，而其他域（parent，lchild，rchild和key）的值我们并不关心。 总之，红黑树是通过以上5种性质的限制约束了该树的平衡性能 即：该树上的最长路径长度不可能大于最短路径长度的2倍，从而确保对树操作的时间复杂度达到O（log2N）。3 编码实现3.1 结构定义、常值定义：增强代码可读性、方便代码修改cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* 常值定

5、义 */ #define RBT_COLOR_BLACK 'b' /* 颜色：黑色 */ #define RBT_COLOR_RED 'r' /* 颜色：红色 */ #define RBT_LCHILD (0) /* 类型：左孩子 */ #define RBT_RCHILD (1) /* 类型：右孩子 */ #define RBT_MAX_DEPTH (512) /* 栈的深度(栈处理红黑树时使用) */ 代码1 常值定义、节点结构：在二叉查找树的结构基础上，新增color字段cpp view plain copy print?在CODE上查看代码片派生到我的代

6、码片/* 结点结构 */ 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; 代码2 结点结构、树结构：sentinel字段用于表示叶子结点（NIL）。当树内结点的左（右）孩子为

7、叶子结点时，则将左（右）孩子指针指向sentinel字段。cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* 红黑树结构 */ typedef struct rbt_node_t *root; /* 根节点 */ rbt_node_t *sentinel; /* 哨兵节点 */ rbt_tree_t; 代码3 树结构、错误码：用来记录错误返回的类型，以便快速的确定程序中存在的异常cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* 错误码 */ typedef enum RBT_SUCCESS /* 成功 *

8、/ , RBT_FAILED = 0x7fffffff /* 失败 */ , RBT_NODE_EXIST /* 结点存在 */ rbt_ret_e; 代码4 错误码、宏定义：可有效的增强代码的简洁性、复用性、易读性cpp view plain copy print?在CODE上查看代码片派生到我的代码片#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_

9、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); /*

10、设置右孩子 */ #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); 代

11、码5 宏定义3.2 创建对象 创建的初始红黑树对象是一棵空树，其根节点为NULL，但是此时必须为叶子结点（哨兵）分配好空间，并将叶子结点的颜色置为黑色（性质3），以方便后续对树的操作处理。cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* *函数名称: rbt_creat *功 能: 创建红黑树对象(对外接口) *输入参数: NONE *输出参数: NONE *返 回: 红黑树对象地址 *实现描述: *注意事项: * 1、每个结点要么是红色的，要么是黑色的； * 2、根结点是黑色的； * 3、所有叶子结点（NIL）都是黑色的； * 4、如果一个结点是

12、红色，则它的两个儿子都是黑色的； * 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_no

13、de_t); if (NULL = tree->sentinel) free(tree); return NULL; tree->sentinel->color = RBT_COLOR_BLACK; tree->root = tree->sentinel; return tree; 代码6 创建对象3.3 旋转处理 在插入和删除过程中，可能破坏红黑树的5个性质之一，和平衡二叉树的处理相似，可通过旋转来恢复红黑树的性质，但红黑树的旋转只有右旋和左旋2种。右旋处理： 以结点N为支点，进行右旋转的处理描述：结点N的左孩子A取代N的位置，并将结点A的右孩子AR作为结点N的

14、左孩子，再将结点N作为结点A的右孩子。右旋处理对应的代码如下所示：cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* *函数名称: 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为旋转支点 *注意

15、事项: *作 者: # 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_se

16、t_lchild(tree, parent, lchild); else rbt_set_rchild(tree, parent, lchild); rbt_set_lchild(tree, node, lchild->rchild); rbt_set_rchild(tree, lchild, node); 代码7 右旋处理左旋处理： 以结点N为支点，进行右旋转的处理描述：结点N的左孩子B取代N的位置，并将结点B的左孩子BL作为结点N的右孩子，再将结点N作为结点B的左孩子。左旋处理对应的代码如下：cpp view plain copy print?在CODE上查看代码片派生到我的代码片/

17、* *函数名称: 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_e(rbt_tree_t *tree, rbt_n

18、ode_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_rchi

19、ld(tree, node, rchild->lchild); rbt_set_lchild(tree, rchild, node); 代码8 左旋处理3.4 插入操作 1）当向一棵空树中插入结点时，则新结点将作为整棵树根结点，且为黑色（性质2）；2）当向一棵非空树中插入一个结点时，新结点的颜色都是为红色。插入成功后，需要判断是否破坏了红黑树的5个性质。经过分析，可以发现，向非空树中插入一个结点，不可能破坏性质1、2、3、5，唯一可能被破坏只有性质4 出现2个连续的红结点新节点和父节点为红色，且性质4被破坏，只有如下六种情况：=前提1：父节点P为祖父节点G的左孩子= 情况1）：叔结点U为

20、红色 前提条件：新结点N和父结点P都为红色，父结点P为G的左孩子 情况描述：叔结点U为红色时 注：此时不必关心新结点N是左孩子还是右孩子 处理过程：代码：参考rb_insert_fixup()中的case 1 、将父结点P和叔结点U的颜色改为黑色，将祖父结点G改为红色 、把祖父结点作为下一次判断的对象情况2）：叔结点为黑色，新结点N为右孩子 前提条件：新结点N和父结点P都为红色，父结点P为G的左孩子 情况描述：叔结点U也为黑色，新结点N为右孩子时 处理过程：代码：参考rb_insert_fixup()中的case 2 、调整颜色：将父结点P改为黑色，将祖父结点改为红色 、向右旋转90度：父结点

21、P取代祖父结点G的位置，同时将父结点的右子树PR作为祖父结点G的左子树，祖父结点G作为父结点P的右孩子 、把祖父结点的父结点GP改为下一次判断的对象情况3）：叔结点为黑色，新结点N为右孩子 前提条件：新结点N和父结点P都为红色，父结点P为G的左孩子 情况描述：叔结点U也为黑色，新结点N为右孩子时 处理过程：代码：参考rb_insert_fixup()中的case 3 、向左旋转90度：新结点N取代父结点P的位置，同时将新结点的左子树NL作为父结点P的右子树，父结点P作为新结点N的左孩子 、把父结点P改为下一次判断的对象 注意：经过、处理后，情况3演变了情况2=前提2：父节点P为祖父节点G的右孩

22、子 = 情况4）：叔结点U为红色 前提条件：新结点N和父结点P都为红色，父结点P为祖父G的右孩子 情况描述：叔结点U为红色时 注：此时不必关心新结点N是左孩子还是右孩子 处理过程：代码：参考rb_insert_fixup()中的case 4 、将父结点P和叔结点U的颜色改为黑色，将祖父结点G改为红色 、把祖父结点作为下一次判断的对象情况5）：叔结点U为黑色，新结点N为父结点P的左孩子 前提条件：新结点N和父结点P都为红色，父结点P为祖父结点G的右孩子 情况描述：叔结点U为黑色，新结点N为左孩子时 处理过程：代码：参考rb_insert_fixup()中的case 5 、向右旋转90度：新结点N

23、取代父结点G的位置，同时将新结点的右子树NR作为父结点G的左子树，父结点G作为新结点的右孩子 、把父结点P改为下一次判断的对象此时case 5演变为case 6情况6）：叔结点U为黑色，新结点N为父结点P的右孩子 前提条件：新结点N和父结点P都为红色，父结点P为G的右孩子 情况描述：叔结点U为黑色，新结点N为右孩子时 处理过程：代码：参考rb_insert_fixup()中的case 6 、颜色调整：将祖父结点G改为红色，父结点P改为黑色 、向左旋转90度：父结点P取代祖父结点G的位置，同时将父结点的左子树PL作为祖父结点G的右子树，祖父结点G作为父结点P的左孩子 、把祖父结点的父结点GP改为

24、下一次判断的对象cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* *函数名称: rbt_creat_node *功 能: 创建关键字为key的结点(内部接口) *输入参数: * key: 红黑树 * color: 结点颜色 * type: 新结点是父结点的左孩子还是右孩子 * parent: 父结点 *输出参数: NONE *返 回: RB_SUCCESS:成功 RB_FAILED:失败 *实现描述: *注意事项: 新结点的左右孩子肯定是叶子结点 *作 者: # Qifeng.zou # 2013.12.23 # */ rbt_node_t *rb

25、t_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->senti

26、nel; if (NULL != parent) rbt_set_child(tree, parent, type, node); else node->parent = tree->sentinel; return node; 代码9 创建key值结点cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* *函数名称: rbt_insert *功 能: 向红黑树中增加节点(对外接口) *输入参数: * tree: 红黑树 * key: 需被添加的关键字 *输出参数: NONE *返 回: RBT_SUCCESS:成功 RBT_FAILED:

27、失败 RBT_NODE_EXIST:节点存在 *实现描述: * 1. 当根节点为空时，直接添加 * 2. 将节点插入树中, 检查并修复新节点造成红黑树性质的破坏 *注意事项: * 红黑树的5点性质: * 1、每个结点要么是红色的，要么是黑色的； * 2、根结点是黑色的； * 3、所有叶子结点(NIL)都是黑色的； * 4、如果一个结点是红色，则它的两个儿子都是黑色的； * 5、对任何一个结点，从该结点通过其子孙结点到达叶子结点(NIL) * 的所有路径上包含相同数目的黑结点。 *注意事项: 插入节点操作只可能破坏性质(4) *作 者: # Qifeng.zou # 2013.12.23 # *

28、/ 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) retur

29、n 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 =

30、 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); /* 防止红黑树的性质被破坏 *

31、/ node = node->rchild; return RBT_SUCCESS; 代码10 增加key值结点（内部接口）cpp view plain copy print?在CODE上查看代码片派生到我的代码片/* *函数名称: rb_insert_fixup *功 能: 插入操作修复(内部接口) *输入参数: * tree: 红黑树 * node: 新增节点的地址 *输出参数: NONE *返 回: RBT_SUCCESS:成功 RBT_FAILED:失败 *实现描述: * 1. 检查红黑树性质是否被破坏 * 2. 如果被破坏，则进行对应的处理 *注意事项: 插入节点操作只可能破坏

32、性质 *作 者: # 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_se