首页 > 代码库 > 算法导论 之 红黑树 - 插入[C语言]
算法导论 之 红黑树 - 插入[C语言]
- 作者:邹祁峰
- 邮箱:Qifeng.zou.job@gmail.com
- 博客:http://blog.csdn.net/qifengzou
- 日期:2013.12.24 21:00
- 转载请注明来自"祁峰"的CSDN博客
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语言]