常见的查找算法汇总（含详细代码）4
rbtree.c
/** * c语言实现的红黑树(red black tree) * * @author skywang * @date 2013/11/18 */#include #include #include rbtree.h#define rb_parent(r) ((r)->parent)#define rb_color(r) ((r)->color)#define rb_is_red(r) ((r)->color==red)#define rb_is_black(r) ((r)->color==black)#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 (x==null || x->key==key) return x; if (key key) return search(x->left, key); else return 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 key) x = x->left; else x = 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) && (x==y->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) && (x==y->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的右孩子为y node *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的父节点的左孩子” else x->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的父节点的右孩子” else y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x->right = y; // 将 “y的父节点” 设为 “x” y->parent = x;}/* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * root 红黑树的根 * node 插入的结点 // 对应《算法导论》中的z */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) { // 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) { 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//若“z的父节点”是“z的祖父节点的右孩子” { // case 1条件：叔叔节点是红色 { 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; } } // case 2条件：叔叔是黑色，且当前节点是左孩子 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);}/* * 添加节点：将节点(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 key) x = x->left; else x = x->right; } rb_parent(node) = y; if (y != null) { if (node->key key) y->left = node; // 情况2：若“node所包含的值” right = node; // 情况3：(“node所包含的值” >= “y所包含的值”)将node设为“y的右孩子” } else { root->node = node; // 情况1：若y是空节点，则将node设为根 } // 2. 设置节点的颜色为红色 node->color = red; // 3. 将它重新修正为一颗二叉查找树 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 ((node=create_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; while ((!node || rb_is_black(node)) && node != root->node) { if (parent->left == node) { other = parent->right; if (rb_is_red(other)) { // case 1: x的兄弟w是红色的 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的俩个孩子也都是黑色的 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的俩个孩子也都是黑色的 rb_set_red(other); node = parent; parent = rb_parent(node); } else { if (!other->left || rb_is_black(other->left)) { // 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; else rb_parent(node)->right = replace; } else // node节点是根节点，更新根节点。 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 ; } if (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; else parent->right = child; } else root->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 (tree==null) 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(direction==0) // tree是根节点 printf(%2d(b) is root\\n, tree->key); else // tree是分支节点 printf(%2d(%s) is %2d's %6s child\\n, tree->key, rb_is_red(tree)?r:b, key, direction==1?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);}
评估示波器：要深挖细找次要技术指标
创建升级数据架构是企业加强竞争优势和提高创新的关键
魅族Pro6s评测 为实用主义者打造的旗舰手机
高压差分探头超出量程使用会怎样？
PFA材质与PTFE材质的区别
常见的查找算法汇总（含详细代码）4
如何了解区块链是否适合您的业务
马斯克让特斯拉退市实现私有化 腾讯可能获得超额收益
利用高激发的里德堡态原子实现高速太赫兹成像系统
延续摩尔定律，英特尔强推新制程
坐标北京，迈威通信邀您共赴煤炭行业盛会
一文看懂码灵半导体CFW32C7UL系列MPU产品应用（三）： 国际标准加解密算法
欲与谷歌IBM争雄 微软花大价钱研发量子计算机
PLC的使用过程
超实用！高低温拉力试验机的应用领域分类和应用场景，最新应用攻略！
中国电信与诺基亚贝尔合作，共同繁荣5G终端产业
中国大陆跃升为全球制造业的霸主
详细剖析黑客利用机器学习发起网络攻击的六种方式
飞行中使用VR有可能导致乘客晕机，机上VR娱乐实施困难重重
云网融合运营系统的两大需求
/** * c语言实现的红黑树(red black tree) * * @author skywang * @date 2013/11/18 */#include #include #include rbtree.h#define rb_parent(r) ((r)->parent)#define rb_color(r) ((r)->color)#define rb_is_red(r) ((r)->color==red)#define rb_is_black(r) ((r)->color==black)#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 (x==null || x->key==key) return x; if (key key) return search(x->left, key); else return 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 key) x = x->left; else x = 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) && (x==y->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) && (x==y->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的右孩子为y node *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的父节点的左孩子” else x->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的父节点的右孩子” else y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x->right = y; // 将 “y的父节点” 设为 “x” y->parent = x;}/* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * root 红黑树的根 * node 插入的结点 // 对应《算法导论》中的z */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) { // 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) { 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//若“z的父节点”是“z的祖父节点的右孩子” { // case 1条件：叔叔节点是红色 { 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; } } // case 2条件：叔叔是黑色，且当前节点是左孩子 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);}/* * 添加节点：将节点(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 key) x = x->left; else x = x->right; } rb_parent(node) = y; if (y != null) { if (node->key key) y->left = node; // 情况2：若“node所包含的值” right = node; // 情况3：(“node所包含的值” >= “y所包含的值”)将node设为“y的右孩子” } else { root->node = node; // 情况1：若y是空节点，则将node设为根 } // 2. 设置节点的颜色为红色 node->color = red; // 3. 将它重新修正为一颗二叉查找树 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 ((node=create_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; while ((!node || rb_is_black(node)) && node != root->node) { if (parent->left == node) { other = parent->right; if (rb_is_red(other)) { // case 1: x的兄弟w是红色的 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的俩个孩子也都是黑色的 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的俩个孩子也都是黑色的 rb_set_red(other); node = parent; parent = rb_parent(node); } else { if (!other->left || rb_is_black(other->left)) { // 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; else rb_parent(node)->right = replace; } else // node节点是根节点，更新根节点。 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 ; } if (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; else parent->right = child; } else root->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 (tree==null) 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(direction==0) // tree是根节点 printf(%2d(b) is root\\n, tree->key); else // tree是分支节点 printf(%2d(%s) is %2d's %6s child\\n, tree->key, rb_is_red(tree)?r:b, key, direction==1?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);}
评估示波器：要深挖细找次要技术指标
创建升级数据架构是企业加强竞争优势和提高创新的关键
魅族Pro6s评测 为实用主义者打造的旗舰手机
高压差分探头超出量程使用会怎样？
PFA材质与PTFE材质的区别
常见的查找算法汇总（含详细代码）4
如何了解区块链是否适合您的业务
马斯克让特斯拉退市实现私有化 腾讯可能获得超额收益
利用高激发的里德堡态原子实现高速太赫兹成像系统
延续摩尔定律，英特尔强推新制程
坐标北京，迈威通信邀您共赴煤炭行业盛会
一文看懂码灵半导体CFW32C7UL系列MPU产品应用（三）： 国际标准加解密算法
欲与谷歌IBM争雄 微软花大价钱研发量子计算机
PLC的使用过程
超实用！高低温拉力试验机的应用领域分类和应用场景，最新应用攻略！
中国电信与诺基亚贝尔合作，共同繁荣5G终端产业
中国大陆跃升为全球制造业的霸主
详细剖析黑客利用机器学习发起网络攻击的六种方式
飞行中使用VR有可能导致乘客晕机，机上VR娱乐实施困难重重
云网融合运营系统的两大需求