网站seo推广优化报价表,无费用开网店,上海包装设计公司有哪些,网站定制哪家安全红黑树讲解和实现1 红黑树介绍1.1 红黑树特性1.2 红黑树的插入1.3 红黑树的删除2 完整代码实现2.1 rtbtree.h头文件2.2 main.c源文件1 红黑树介绍 红黑树( Red-Black tree#xff0c;简称RB树)是一种自平衡二叉查找树#xff0c;是计算机科学中常见的一种数据结构#xff0c…
红黑树讲解和实现1 红黑树介绍1.1 红黑树特性1.2 红黑树的插入1.3 红黑树的删除2 完整代码实现2.1 rtbtree.h头文件2.2 main.c源文件1 红黑树介绍 红黑树( Red-Black tree简称RB树)是一种自平衡二叉查找树是计算机科学中常见的一种数据结构其典型用途是实现关联数组。红黑树的结构复杂但其操作有着良好的最坏情况运行时间且在实践中有着较高的效率:它可以在O(log2n)时间内完成查找、插入和删除操作其中的n是树中结点的数量。 红黑树(RB树)是二叉树中重要的知识点因为在操作系统的内核中、C的STL和Java的数据结构中都大量使用了红黑树红黑树的增删查改的复杂度均为log2n。
1.1 红黑树特性 红黑树是每个结点都带有颜色属性的二叉查找树颜色为红色或黑色给结点进行染色的原因是用颜色和红黑树性质对树进行平衡使得红黑树的任意一条路径长度都不可能超过其他路径的两倍。在二叉查找树的–般要求以外对于任何有效的红黑树我们额外增加了如下性质
结点是红色的或黑色的。根是黑色的。所有叶子结点都是黑色的(叶子是NIL结点)。每个红色结点必须有两个黑色的子结点(从每个叶子到根的所有路径上不能有两个连续的红色结点)。从任意一个点到其每个叶子的所有简单路径都包含相同数量的黑色结点。
王道408考研的咸鱼学长总结了一个口诀左根右、根叶黑、不红红、黑路同。
1.2 红黑树的插入 红黑树的插入结点首先标记为红色按照二叉排序树的方式插入后再做调整。红黑树的插入分为5种情况。 **情形一**新结点N是树根没有子节点。这种空树的情况直接将新结点作为根插入染成黑色即可。具体代码如下
void insert_case1(node *n)
{if(n-parent NULL)//如果新插入结点没有父结点即此结点为根结点n-color BLACK;//直接染黑else insert_case2(n);//否则转入情形2即有父结点的情况
}**情形二**父结点为黑色则直接将新结点插入满足性质四不红红即没有两个连续红色。还满足性质5不会增减该路径上黑色结点的数量。具体代码如下
void insert_case2(node *n)
{if(n-parent-color BLACK) //如果父结点为黑色则直接插入return; //不需要调整else insert_case3(n); //如果父结点为红色则需要调整
}**情形三**如果父结点和叔结点都是红色的那么我们可以将父结点和叔结点都染黑保证不红红性质4然后将爷结点染红插入的子结点仍然是红色满足路黑同性质5。此时需要考虑爷结点是否为根结点如果爷结点为根结点则需要将爷结点染黑保证性质不变如果爷结点不为根结点则向上将爷结点红作为其父结点的新插入结点递归情形一。下面给出图示和实现代码
void insert_case3(node *n)
{if(uncle(n)!NULL uncle(n)-color RED n-parent-color RED){//这里父结点颜色可以不考虑否则违反黑路同性质5为了和算法描述一致也加入判断n-parent-color BLACK;//将父结点染黑uncle(n)-color BLACK;//将叔结点染黑grandparent(n)-color RED;//将爷结点染红insert_case1(grandparent(n));//将红色的爷结点作为新结点对上级进行调整}else insert_case4(n);//不满足情形3则考虑情形4
}**情形四**父结点是红色叔结点是黑色或者缺少的情况并且新结点是父结点的右子节点而父结点又是爷结点的左子节点。这种情况需要左旋调换新结点和父结点。
void insert_case4(node *n)
{if(n n-parent-right n-parent grandparent(n)-left){roate_left(n-parent);n n-left;}else if(n-parent-left n-parent grandparent(n)-right){rotate_right(n-parent);//上图中对称的情况父结点在爷结点右边子结点在父结点左边n n-right;}insert_case5(n);//情形5
}**情形五**父结点是红色叔结点是黑色或缺少子结点是父节点的左子节点而父结点又是爷结点的左下结点。这种情况需要将爷结点右旋并且改变相应结点的颜色完成插入。
void insert_case5(node *n)
{n-parent-color BLACK;grandparent(n)-color RED;if(n-parent-left n n-parent grandparent(n)-left){rotate_right(grandparent(n));}else if(n-parent-right n n-parent grandparent(n)-right){//与上图中完全对称的情况rotate_left(grparent(n);}
}插入修正函数 对于上述情景3、4、5红黑树插入结点后可能会失去平衡调用此函数保持性质。对于下图中情形三可以单独处理而情形四可以通过旋转到情形五进而调整。
static void rbtree_insert_fixup(RBRoot *root, Node *node)
{Node *parent,*gparent;//如果父结点存在且为红色需要调整while((parent rb_parent(node)) rb_is_red(parent)){gparent rb_parent(parent);//若父结点是爷结点的左孩子结点if(parent gparent-left){//情况1条件叔结点存在且为红色这种是情形3Node *uncle gparent-right;if(uncle rb_is_red(uncle)){//将父结点和叔结点染黑将爷结点染红rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node gparent;//node调整完毕回到父结点}}//情况2条件叔结点是黑色或不存在且当前结点是父节点的有孩子情形4//父节点右旋交换父子结点if (parent-right node){Node *tmp;rbtree_left_rotate(root, parent);tmp parent;parent node;node tmp;}//情形3条件叔结点是黑色且当前结点是父节点的左孩子结点。这里是情形 5rb_set_black(parent); //旋转前设置好颜色rb_set_red(gparent); //旋转前设置好颜色rbtree_right_rotate(root, gparent);//爷结点右旋} else{//若父结点是祖父结点的右孩子结点则下面三种和上面的是对称的Node *uncle gparent-left;if (uncle rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node gparent;continue; //继续进行调整}if (parent-left node){Node *tmp;rbtree_right_rotate(root, parent);tmp parent;parent node;node tmp;}//Case 3 条件叔父结点是黑色的且当前结点是右孩子结点。这里是情形 5rb_set_black(parent); //旋转前设置好颜色rb_set_red(gparent); //旋转前设置好颜色rbtree_left_rotate(root, gparent);}//将根结点设为黑色rb_set_black(root-node);
}1.3 红黑树的删除
emps;emps;对于红黑树的删除中考虑删除结点为黑色或红色如果删除结点为红色则不需要做调整正常删除因为删除红色结点不会影响黑高。而删除黑色结点则比较复杂需要考虑以下六种情形。 **注意**接下来的删除讲解均按照此图进行此图是指删除结点后红黑树删除规则按照二叉平衡树的方式之后未作其他的调整。我们把删除结点N后的替代的结点记为X。
情形一 红黑树仅有一个黑根删除此根满足所有性质。代码如下
void delete_case1(struct node *n)
{if(n-parent!NULL)delete_case2(n);//如果删除的结点不是根
}情形二 被删除的黑色结点N黑色结点X是N的顶替结点X的兄弟结点W结点是红色。这种删除的情况会使左边黑高-1破坏了黑路同性质5所以需要做染色左旋操作。先将父结点染红再将兄弟结点W染黑然后对父结点进行左旋操作这样不会破坏红黑树的性质。
void delete_case2(struct node *n)
{struct node *s sibling(n);//n的兄弟结点if(s-color RED){//如果兄弟结点是红色n-parent-color RED;//将父结点染红s-color BLACK;//将父结点染黑if(n-parent-left n)//如果n是左孩子rotate_ left(n-parent);//父结点左旋 else //如果n是右孩子rotate_right(n-parent);//父结点右旋}delete_case3(n);//考虑情景3}情形三 被删除的黑色结点N黑色结点X是N的顶替结点X的父结点、兄弟结点W及其子结点均为黑色。左侧黑高-1破坏了黑路同性质5此时将兄弟结点W染红使得满足黑路同性质5但是如果A树作为左子树或者右子树整体黑高-1此时需要将矛盾上移在A结点上重新做平衡处理。代码如下
void delete_case3(struct node *n)
{struct node *s sibling(n);if((n-parent-color BLACK) (S-color BLACK) (s-left-color BLACK) (s-right-color BLACK)){s-color RED;//将兄弟结点染红delete_case1(n-parent);//将父结点作为新的处理结点从case1开始平衡}else delete_case4(n);//如果不符合情形三请看情形4
}**情形四**被删除的黑色结点N黑色结点X是N的顶替结点父结点A是红色兄弟结点W及其子结点都是黑色。此时左侧黑高-1不满足黑路同性质5所以需要调整将父结点A染黑兄弟结点W染红则满足性质。代码如下
void delete_case4(struct node *n)
{struct node *s sibling(n);if((n-parent-color RED) (S-color BLACK) (s-left-color BLACK) (s-right-color BLACK)){s-color RED;//将兄弟结点染红n-parent BLACK;//将父结点染黑}else delete_case5(n);//如果不符合情形4考虑情形五
}情形五 被删除的黑色结点N黑色结点X是N的顶替结点X的兄弟结点W是黑色W结点的左子结点是红色W结点的右子结点是黑色。此时将兄弟结点W染红W的左子结点染黑然后进行右旋操作此时代替结点X和父结点A都不受右旋影响。然后继续情形六。代码如下
void
delete_case5(struct node *n)
{struct node *s sibling (n);ifs-color BLACK){if((n n-parent-left)(s-right-color BLACK)(s-left-color RED)) { // 这种情况下 n 结点是其父结点的左子结点S 结点是其父结点的右子结s-color RED;s-left-color BLACK;rotate_right (s);} else if((n n-parent-right)(s-left-color BLACK)(s-right-color RED)) {// 这种情况下 n 结点是其父结点的右子结点S 结点是其父结点的左子结点s-color RED;s-right-color BLACK;rotate_left (s);}}delete_case6 (n); //调整完毕后再通过情形 6 进行调整
}情形六 被删除的黑色结点N黑色结点X是N的顶替结点兄弟结点W结点是黑色的W结点的右子结点是红色的而替代结点X是其父结点A的左子结点。将兄弟结点W染红将父结点A染黑W的右子结点也染黑然后W左旋操作。就达到了情形四的情况。代码如下
void delete_case6(struct node *n)
{struct node *s sibling(n);s-color n-parent-color;n-parent-color BLACK;if(n-parent-leftn){s-right-color BLACK;rotate_left(n-parent);}else{s-left-color BLACK;rotate_right(n-parent);}
}删除修正函数
static void rbtree_delete_fixup(RBRoot *root, Node *node, Node *parent)
{Node *other;//下面的x说的是nodewhile ((!node || rb_is_black(node)) node ! root-node){if (parent-left node){//删除other parent-right;if (rb_is_red(other)){// Case 1: x的兄弟w是红色的,删除77 rb_set_black(other);rb_set_red(parent);rbtree_left_rotate(root, parent);other parent-right;}if ((!other-left || rb_is_black(other-left)) (!other-right || rb_is_black(other-right))){// Case 2: x的兄弟w是黑色且w的俩个孩子也都是黑色的,删除65时删除82时二级进入循环rb_set_red(other);node parent;parent rb_parent(node);}else{if (!other-right || rb_is_black(other-right)){// Case 3: x的兄弟w是黑色的并且w的右孩子为黑色。 rb_set_black(other-left);rb_set_red(other);rbtree_right_rotate(root, other);other parent-right;}// Case 4: x的兄弟w是黑色的并且w的右孩子是红色的左孩子任意颜色。rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other-right);rbtree_left_rotate(root, parent);node root-node;break;}}else{//删除other parent-left;if (rb_is_red(other)){// Case 1: x的兄弟w是红色的 rb_set_black(other);rb_set_red(parent);rbtree_right_rotate(root, parent);other parent-left;}if ((!other-left || rb_is_black(other-left)) (!other-right || rb_is_black(other-right))){// Case 2: x的兄弟w是黑色且w的俩个孩子也都是黑色的删除77 rb_set_red(other);node parent;parent rb_parent(node);}else{if (!other-left || rb_is_black(other-left)){//删除99时应该是w的左孩子是黑色// Case 3: x的兄弟w是黑色的并且w的左孩子是为黑色。 rb_set_black(other-right);rb_set_red(other);rbtree_left_rotate(root, other);other parent-left;}// Case 4: x的兄弟w是黑色的并且w的右孩子是红色的左孩子任意颜色。rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other-left);rbtree_right_rotate(root, parent);node root-node;break;}}}if (node)rb_set_black(node);
}2 完整代码实现
2.1 rtbtree.h头文件
#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_#define RED 0 // 红色节点
#define BLACK 1 // 黑色节点typedef int Type;// 红黑树的节点
typedef struct RBTreeNode{unsigned char color; // 颜色(RED 或 BLACK)Type key; // 关键字(键值)struct RBTreeNode *left; // 左孩子struct RBTreeNode *right; // 右孩子struct RBTreeNode *parent; // 父结点
}Node, *RBTree;// 红黑树的根
typedef struct rb_root{Node *node;
}RBRoot;// 创建红黑树返回红黑树的根
RBRoot* create_rbtree();// 销毁红黑树
void destroy_rbtree(RBRoot *root);// 将结点插入到红黑树中。插入成功返回0失败返回-1。
int insert_rbtree(RBRoot *root, Type key);// 删除结点(key为节点的值)
void delete_rbtree(RBRoot *root, Type key);// 前序遍历红黑树
void preorder_rbtree(RBRoot *root);
// 中序遍历红黑树
void inorder_rbtree(RBRoot *root);
// 后序遍历红黑树
void postorder_rbtree(RBRoot *root);// (递归实现)查找红黑树中键值为key的节点。找到的话返回0否则返回-1。
int rbtree_search(RBRoot *root, Type key);
// (非递归实现)查找红黑树中键值为key的节点。找到的话返回0否则返回-1。
int iterative_rbtree_search(RBRoot *root, Type key);// 返回最小结点的值(将值保存到val中)。找到的话返回0否则返回-1。
int rbtree_minimum(RBRoot *root, int *val);
// 返回最大结点的值(将值保存到val中)。找到的话返回0否则返回-1。
int rbtree_maximum(RBRoot *root, int *val);// 打印红黑树
void print_rbtree(RBRoot *root);#endif2.2 main.c源文件
/*** C语言实现的红黑树(Red Black Tree)** author skywang* date 2013/11/18*/#include stdio.h
#include stdlib.h
#include rbtree.h#define rb_parent(r) ((r)-parent)
#define rb_color(r) ((r)-color)
#define rb_is_red(r) ((r)-colorRED)
#define rb_is_black(r) ((r)-colorBLACK)
#define rb_set_black(r) do { (r)-color BLACK; } while (0)
#define rb_set_red(r) do { (r)-color RED; } while (0)
#define rb_set_parent(r,p) do { (r)-parent (p); } while (0)
#define rb_set_color(r,c) do { (r)-color (c); } while (0)/** 创建红黑树返回红黑树的根*/
RBRoot* create_rbtree()
{RBRoot *root (RBRoot *)malloc(sizeof(RBRoot));root-node NULL;return root;
}/** 前序遍历红黑树*/
static void preorder(RBTree tree)
{if(tree ! NULL){printf(%d , tree-key);preorder(tree-left);preorder(tree-right);}
}
void preorder_rbtree(RBRoot *root)
{if (root)preorder(root-node);
}/** 中序遍历红黑树*/
static void inorder(RBTree tree)
{if(tree ! NULL){inorder(tree-left);printf(%d , tree-key);inorder(tree-right);}
}void inorder_rbtree(RBRoot *root)
{if (root)inorder(root-node);
}/** 后序遍历红黑树*/
static void postorder(RBTree tree)
{if(tree ! NULL){postorder(tree-left);postorder(tree-right);printf(%d , tree-key);}
}void postorder_rbtree(RBRoot *root)
{if (root)postorder(root-node);
}/** (递归实现)查找红黑树x中键值为key的节点*/
static Node* search(RBTree x, Type key)
{if (xNULL || x-keykey)return x;if (key x-key)return search(x-left, key);elsereturn search(x-right, key);
}
int rbtree_search(RBRoot *root, Type key)
{if (root)return search(root-node, key)? 0 : -1;
}/** (非递归实现)查找红黑树x中键值为key的节点*/
static Node* iterative_search(RBTree x, Type key)
{while ((x!NULL) (x-key!key)){if (key x-key)x x-left;elsex x-right;}return x;
}
int iterative_rbtree_search(RBRoot *root, Type key)
{if (root)return iterative_search(root-node, key) ? 0 : -1;
}/* * 查找最小结点返回tree为根结点的红黑树的最小结点。*/
static Node* minimum(RBTree tree)
{if (tree NULL)return NULL;while(tree-left ! NULL)tree tree-left;return tree;
}int rbtree_minimum(RBRoot *root, int *val)
{Node *node;if (root)node minimum(root-node);if (node NULL)return -1;*val node-key;return 0;
}/* * 查找最大结点返回tree为根结点的红黑树的最大结点。*/
static Node* maximum(RBTree tree)
{if (tree NULL)return NULL;while(tree-right ! NULL)tree tree-right;return tree;
}int rbtree_maximum(RBRoot *root, int *val)
{Node *node;if (root)node maximum(root-node);if (node NULL)return -1;*val node-key;return 0;
}/* * 找结点(x)的后继结点。即查找红黑树中数据值大于该结点的最小结点。*/
static Node* rbtree_successor(RBTree x)
{// 如果x存在右孩子则x的后继结点为 以其右孩子为根的子树的最小结点。if (x-right ! NULL)return minimum(x-right);// 如果x没有右孩子。则x有以下两种可能// (01) x是一个左孩子则x的后继结点为 它的父结点。// (02) x是一个右孩子则查找x的最低的父结点并且该父结点要具有左孩子找到的这个最低的父结点就是x的后继结点。Node* y x-parent;while ((y!NULL) (xy-right)){x y;y y-parent;}return y;
}/* * 找结点(x)的前驱结点。即查找红黑树中数据值小于该结点的最大结点。*/
static Node* rbtree_predecessor(RBTree x)
{// 如果x存在左孩子则x的前驱结点为 以其左孩子为根的子树的最大结点。if (x-left ! NULL)return maximum(x-left);// 如果x没有左孩子。则x有以下两种可能// (01) x是一个右孩子则x的前驱结点为 它的父结点。// (01) x是一个左孩子则查找x的最低的父结点并且该父结点要具有右孩子找到的这个最低的父结点就是x的前驱结点。Node* y x-parent;while ((y!NULL) (xy-left)){x y;y y-parent;}return y;
}/* * 对红黑树的节点(x)进行左旋转** 左旋示意图(对节点x进行左旋)* px px* / /* x y * / \ --(左旋)-- / \ #* lx y x ry * / \ / \* ly ry lx ly ***/
static void rbtree_left_rotate(RBRoot *root, Node *x)
{// 设置x的右孩子为yNode *y x-right;// 将 “y的左孩子” 设为 “x的右孩子”// 如果y的左孩子非空将 “x” 设为 “y的左孩子的父亲”x-right y-left;if (y-left ! NULL)y-left-parent x;// 将 “x的父亲” 设为 “y的父亲”y-parent x-parent;if (x-parent NULL)//修改红黑树的根节点{//tree y; // 如果 “x的父亲” 是空节点则将y设为根节点root-node y; // 如果 “x的父亲” 是空节点则将y设为根节点}else{if (x-parent-left x) x-parent-left y; // 如果 x是它父节点的左孩子则将y设为“x的父节点的左孩子”elsex-parent-right y; // 如果 x是它父节点的左孩子则将y设为“x的父节点的左孩子”}// 将 “x” 设为 “y的左孩子”y-left x;// 将 “x的父节点” 设为 “y”x-parent y;
}/* * 对红黑树的节点(y)进行右旋转** 右旋示意图(对节点y进行左旋)* py py* / /* y x * / \ --(右旋)-- / \ #* x ry lx y * / \ / \ #* lx rx rx ry* */
static void rbtree_right_rotate(RBRoot *root, Node *y)
{// 设置x是当前节点的左孩子。Node *x y-left;// 将 “x的右孩子” 设为 “y的左孩子”// 如果x的右孩子不为空的话将 “y” 设为 “x的右孩子的父亲”y-left x-right;if (x-right ! NULL)x-right-parent y;// 将 “y的父亲” 设为 “x的父亲”x-parent y-parent;if (y-parent NULL) {//tree x; // 如果 “y的父亲” 是空节点则将x设为根节点root-node x; // 如果 “y的父亲” 是空节点则将x设为根节点}else{if (y y-parent-right)y-parent-right x; // 如果 y是它父节点的右孩子则将x设为“y的父节点的右孩子”elsey-parent-left x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”}// 将 “y” 设为 “x的右孩子”x-right y;// 将 “y的父节点” 设为 “x”y-parent x;
}/** 红黑树插入修正函数** 在向红黑树中插入节点之后(失去平衡)再调用该函数* 目的是将它重新塑造成一颗红黑树。** 参数说明* root 红黑树的根* node 插入的结点 // 对应《算法导论》中的z*/
static void rbtree_insert_fixup1(RBRoot *root, Node *node)
{Node *parent, *gparent;// 若“父节点存在并且父节点的颜色是红色”while ((parent rb_parent(node)) rb_is_red(parent)){gparent rb_parent(parent);//若“父节点”是“祖父节点的左孩子”if (parent gparent-left){// Case 1条件叔叔节点是红色{Node *uncle gparent-right;if (uncle rb_is_red(uncle))//没有节点进入该分支如何构造{rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node gparent;continue;}}// Case 2条件叔叔是黑色且当前节点是右孩子,叔叔不存在也认为是黑色if (parent-right node)//插入80节点时先左旋后右旋{Node *tmp;rbtree_left_rotate(root, parent);tmp parent;parent node;node tmp;}// Case 3条件叔叔是黑色且当前节点是左孩子。rb_set_black(parent);//旋转前设置好颜色rb_set_red(gparent);//旋转前设置好颜色rbtree_right_rotate(root, gparent);} else//若父节点是祖父节点的右孩子{// Case 1条件叔叔节点是红色{Node *uncle gparent-left;//当插入60时调整颜色即可调整颜色后不符合红黑树递归进行if (uncle rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node gparent;continue;//继续进行调整}}// Case 2条件叔叔是黑色且当前节点是左孩子插入30时先右旋后左旋if (parent-left node){Node *tmp;rbtree_right_rotate(root, parent);tmp parent;parent node;node tmp;}// Case 3条件叔叔是黑色且当前节点是右孩子。rb_set_black(parent);//旋转前设置好颜色rb_set_red(gparent);//旋转前设置好颜色rbtree_left_rotate(root, gparent);}}// 将根节点设为黑色rb_set_black(root-node);
}static void rbtree_insert_fixup(RBRoot *root, Node *node)
{Node* parent;Node *tmp;while((parent rb_parent(node))parent-colorRED){Node *gparentrb_parent(parent);if(gparent-leftparent){//情形三Node *unclegparent-right;if(unclerb_is_red(uncle)){rb_set_black(parent);rb_set_black(uncle);rb_set_red(gparent);nodegparent;continue;}//情形四if(parent-rightnode){rbtree_left_rotate(root,parent);tmpparent;parentnode;nodetmp;}//情形五rbtree_right_rotate(root,gparent);rb_set_black(parent);rb_set_red(gparent);}else{//情形三Node *unclegparent-left;if(unclerb_is_red(uncle)){rb_set_black(parent);rb_set_black(uncle);rb_set_red(gparent);nodegparent;continue;}//情形四if(parent-leftnode){rbtree_right_rotate(root,parent);tmpparent;parentnode;nodetmp;}//情形五rbtree_left_rotate(root,gparent);rb_set_black(parent);rb_set_red(gparent);}}rb_set_black(root-node);
}/** 添加节点将节点(node)插入到红黑树中** 参数说明* root 红黑树的根* node 插入的结点 // 对应《算法导论》中的z*/
static void rbtree_insert(RBRoot *root, Node *node)
{Node *y NULL;Node *x root-node;// 1. 将红黑树当作一颗二叉查找树将节点添加到二叉查找树中。while (x ! NULL){y x;if (node-key x-key)x x-left;elsex x-right;}rb_parent(node) y;//找到父节点并把要插入节点的父节点的指针修改//修改父节点的子节点指针if (y ! NULL){if (node-key y-key)y-left node; // 情况2若“node所包含的值” “y所包含的值”则将node设为“y的左孩子”elsey-right node; // 情况3(“node所包含的值” “y所包含的值”)将node设为“y的右孩子” }else{root-node node; // 情况1若y是空节点则将node设为根}// 2. 设置节点的颜色为红色node-color RED;// 3. 将它重新修正为一颗rb树rbtree_insert_fixup(root, node);
}/** 创建结点** 参数说明* key 是键值。* parent 是父结点。* left 是左孩子。* right 是右孩子。*/
static Node* create_rbtree_node(Type key, Node *parent, Node *left, Node* right)
{Node* p;if ((p (Node *)malloc(sizeof(Node))) NULL)return NULL;p-key key;p-left left;p-right right;p-parent parent;p-color BLACK; // 默认为黑色return p;
}/* * 新建结点(节点键值为key)并将其插入到红黑树中** 参数说明* root 红黑树的根* key 插入结点的键值* 返回值* 0插入成功* -1插入失败*/
int insert_rbtree(RBRoot *root, Type key)
{Node *node; // 新建结点// 不允许插入相同键值的节点。// (若想允许插入相同键值的节点注释掉下面两句话即可)if (search(root-node, key) ! NULL)return -1;// 如果新建结点失败则返回。if ((nodecreate_rbtree_node(key, NULL, NULL, NULL)) NULL)return -1;rbtree_insert(root, node);return 0;
}/** 红黑树删除修正函数** 在从红黑树中删除插入节点之后(红黑树失去平衡)再调用该函数* 目的是将它重新塑造成一颗红黑树。** 参数说明* root 红黑树的根* node 待修正的节点*/
static void rbtree_delete_fixup(RBRoot *root, Node *node, Node *parent)
{Node *other;//下面的x说的是nodewhile ((!node || rb_is_black(node)) node ! root-node){if (parent-left node){//删除other parent-right;if (rb_is_red(other)){// Case 1: x的兄弟w是红色的,删除77 rb_set_black(other);rb_set_red(parent);rbtree_left_rotate(root, parent);other parent-right;}if ((!other-left || rb_is_black(other-left)) (!other-right || rb_is_black(other-right))){// Case 2: x的兄弟w是黑色且w的俩个孩子也都是黑色的,删除65时删除82时二级进入循环rb_set_red(other);node parent;parent rb_parent(node);}else{if (!other-right || rb_is_black(other-right)){// Case 3: x的兄弟w是黑色的并且w的右孩子为黑色。 rb_set_black(other-left);rb_set_red(other);rbtree_right_rotate(root, other);other parent-right;}// Case 4: x的兄弟w是黑色的并且w的右孩子是红色的左孩子任意颜色。rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other-right);rbtree_left_rotate(root, parent);node root-node;break;}}else{//删除other parent-left;if (rb_is_red(other)){// Case 1: x的兄弟w是红色的 rb_set_black(other);rb_set_red(parent);rbtree_right_rotate(root, parent);other parent-left;}if ((!other-left || rb_is_black(other-left)) (!other-right || rb_is_black(other-right))){// Case 2: x的兄弟w是黑色且w的俩个孩子也都是黑色的删除77 rb_set_red(other);node parent;parent rb_parent(node);}else{if (!other-left || rb_is_black(other-left)){//删除99时应该是w的左孩子是黑色// Case 3: x的兄弟w是黑色的并且w的左孩子是为黑色。 rb_set_black(other-right);rb_set_red(other);rbtree_left_rotate(root, other);other parent-left;}// Case 4: x的兄弟w是黑色的并且w的右孩子是红色的左孩子任意颜色。rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other-left);rbtree_right_rotate(root, parent);node root-node;break;}}}if (node)rb_set_black(node);
}/* * 删除结点** 参数说明* tree 红黑树的根结点* node 删除的结点*/
void rbtree_delete(RBRoot *root, Node *node)
{Node *child, *parent;int color;// 被删除节点的左右孩子都不为空的情况。if ( (node-left!NULL) (node-right!NULL) ) {// 被删节点的后继节点。(称为取代节点)// 用它来取代被删节点的位置然后再将被删节点去掉。Node *replace node;// 获取后继节点,右分支最左的结点就是我们要找的replace replace-right;while (replace-left ! NULL)replace replace-left;// node节点不是根节点(只有根节点不存在父节点)开始替换if (rb_parent(node)){if (rb_parent(node)-left node)rb_parent(node)-left replace;elserb_parent(node)-right replace;} else // node节点是根节点更新根节点。删除60在这里root-node replace;// child是取代节点的右孩子也是需要调整的节点。// 取代节点肯定不存在左孩子因为它是一个后继节点。child replace-right;parent rb_parent(replace);// 保存取代节点的颜色color rb_color(replace);// 被删除节点是它的后继节点的父节点if (parent node){parent replace;} else{// child不为空if (child)rb_set_parent(child, parent);//因为结点要移到删除位所以它的右节点变为其父亲的左结点parent-left child;replace-right node-right;rb_set_parent(node-right, replace);}replace-parent node-parent;replace-color node-color;replace-left node-left;node-left-parent replace;//移除一个红色结点不需要调整但是移除一个黑色结点红黑树平衡就会打破if (color BLACK)rbtree_delete_fixup(root, child, parent);free(node);return ;}//删除结点有一边是NULLif (node-left !NULL)child node-left;else child node-right;//获取删除结点的父亲parent node-parent;// 保存取代节点的颜色color node-color;if (child)child-parent parent;// node节点不是根节点if (parent){//在父亲的左边就把自己孩子放左边在右边就把自己孩子放右边if (parent-left node)parent-left child;elseparent-right child;}elseroot-node child;//如果是根孩子就变为根if (color BLACK)rbtree_delete_fixup(root, child, parent);free(node);
}/* * 删除键值为key的结点** 参数说明* tree 红黑树的根结点* key 键值*/
void delete_rbtree(RBRoot *root, Type key)
{Node *z, *node; if ((z search(root-node, key)) ! NULL)rbtree_delete(root, z);
}/** 销毁红黑树*/
static void rbtree_destroy(RBTree tree)
{if (treeNULL)return ;if (tree-left ! NULL)rbtree_destroy(tree-left);if (tree-right ! NULL)rbtree_destroy(tree-right);free(tree);
}void destroy_rbtree(RBRoot *root)
{if (root ! NULL)rbtree_destroy(root-node);free(root);
}/** 打印红黑树** tree -- 红黑树的节点* key -- 节点的键值 * direction -- 0表示该节点是根节点;* -1表示该节点是它的父结点的左孩子;* 1表示该节点是它的父结点的右孩子。*/
static void rbtree_print(RBTree tree, Type key, int direction)
{if(tree ! NULL){if(direction0) // tree是根节点printf(%2d(B) is root\n, tree-key);else // tree是分支节点printf(%2d(%s) is %2ds %6s child\n, tree-key, rb_is_red(tree)?R:B, key, direction1?right : left);rbtree_print(tree-left, tree-key, -1);rbtree_print(tree-right,tree-key, 1);}
}void print_rbtree(RBRoot *root)
{if (root!NULL root-node!NULL)rbtree_print(root-node, root-node-key, 0);
}/*** C语言实现的红黑树(Red Black Tree)** author skywang* date 2013/11/18*/#define CHECK_INSERT 1 // 插入动作的检测开关(0关闭1打开)
#define CHECK_DELETE 1 // 删除动作的检测开关(0关闭1打开)
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )void main()
{int a[] {10, 40, 30, 60, 90, 70, 20, 50, 80,65};//int a[] {10, 40, 30, 60, 90, 70, 20, 50, 80,65,66,45,77,99,82,23,55,88,33,47};int i, ilenLENGTH(a);RBRoot *rootNULL;root create_rbtree();//给指针申请对应的结构体空间printf( 原始数据: );for(i0; iilen; i)printf(%d , a[i]);printf(\n);for(i0; iilen; i){insert_rbtree(root, a[i]);
#if CHECK_INSERTprintf( 添加节点: %d\n, a[i]);printf( 树的详细信息: \n);print_rbtree(root);printf(\n);
#endif}printf( 前序遍历: );preorder_rbtree(root);printf(\n 中序遍历: );inorder_rbtree(root);printf(\n 后序遍历: );postorder_rbtree(root);printf(\n);if (rbtree_minimum(root, i)0)printf( 最小值: %d\n, i);if (rbtree_maximum(root, i)0)printf( 最大值: %d\n, i);printf( 树的详细信息: \n);print_rbtree(root);printf(\n);#if CHECK_DELETEfor(i0; iilen; i){printf( 删除节点: %d\n, a[i]);delete_rbtree(root, a[i]);if (root){printf( 树的详细信息: \n);print_rbtree(root);printf(\n);}}
#endifdestroy_rbtree(root);
}
