搞懂红黑树及其应用场景 |
您所在的位置：网站首页 › 设计模式及其应用场景分析 › 搞懂红黑树及其应用场景 |
搞懂红黑树及其应用场景
|
红黑树
1 性质
1. 每个结点是红的或黑的 2. 根结点是黑的 3. 每个叶子结点是黑色的 4. 如果一个结点是红的，则它的两个儿子都是黑的（不能有连续两个红色结点） 5. 对每个结点，从该节点到其子孙结点的所有路径上的包含相同数目的黑结点 2 插入 插入结点时默认是插入的红色结点，因为只有插入红色结点，在没调整的情况下，才能保证性质 5（所有路径包含相同数目的黑结点）因为插入的结点为红色，因此如果父结点也为红色，则需要调整 调整方法1). 插入结点为根结点 --> 变色 2). 插入结点的叔结点为红色 --> 父与叔结点变为黑色，祖结点变为红色，并将祖结点作为新插入的结点 3). 插入结点的叔结点为黑色 --> 这里要分 4 种情况, 下面解释 -->（/ \ < >） 调整方法有变色和旋转 调整方法 3) 详细说明 此处方法参考网上的一个方法，将分为 4 种情况，4 种情况分别用 (/ \ < >) 四个符号表示，最终目的是变成 ⋀ 当插入结点、父结点、祖结点在一条线上的时候，如图即可用符号 / 和 \ 表示 ：
此处用上面左图来说明调整方法，右图变换同理  –> 那么对于 / ，把祖节点扳下来，怎么扳？你用右手向下扳最方便，让 / 变成 ⋀，即右旋 –> 然后将父结点变为黑色，祖结点变为红色，父节点做为当前结点
当插入结点、父结点、祖结点不在一条线上时，如图即可用符号 < 和 > 表示： 
此处用上面右图来说明调整方法，左图变换同理 
–> 那么对于 >，首先把父结点右旋 ( 将nil算进去就是一个 / )，让 < 变成 –> 然后 \ 按上面1的方法左旋，即可变成 ⋀ –> 最后按上面1的方法完成变色即可 左/右旋补充说明
以下以xyz来表示结点： x —> 待删除的结点 y —> 继子结点（实际删除的是这个结点） z —> 轴心结点（继子的子结点，后续调整以它开始计算黑高） 如何找继子y 当x的子树不满（没有子树或只有一边子树），y为x本身当x拥有左右子树，y为x右子树的最左（最小）结点 ------> y可理解为中序遍历时x的下一个结点当删除的y为黑色时需要调整 因为影响了黑高 调整思想：（以下所说的子树包含z的父结点） 因为黑高 -1，因此就要通过调整来达到黑高平衡 —> z子树+1 或 z结点的兄弟子树-1（递归上去）1. 想办法将z子树+1 因为z子树-1，首先要想办在z子树上找一个红色结点变为黑色； 如果z子树没有红色结点，就去z子树的兄弟子树上找红色结点，如果有就通过旋转将它调整到z子树上，然后变色；2. z子树没有办法+1，就想办法将兄弟子树-1（z的父结点下的这棵子树就-1 如果兄弟子树也没有红色，那么就可以通过兄弟变为红色，使z和兄弟子树都-1（这样父结点下的这棵子树就-1了），然后父结点就可作为新的x去调整调整时先变色，后旋转
调整方法总结 N轴心结点，S兄弟结点，P父结点 说明：N子树黑高为-1，S子树黑高为0 兄红 S和P交换颜色(N子树-1，S子树0) --> 以P进行旋转(N子树-1，S子树0) --> N子树有红色结点（原P）可变黑色（N子树0，S子树0）兄黑 2.1 兄子树全黑 2.1.1 P为红：P与S交换颜色(N子树0，S子树0) 2.1.2P为黑：S结点变为红色(N子树-1，S子树-1，P子树-1) --> 因为P子树-1，所以将P作为N进行平衡处理 2.2 兄子树不全黑 2.2.1 红兄子与兄S在同一侧：该侧红兄子变黑(N子树-1，S子树+1) --> 以P进行旋转(N子树0，S子树0) 2.2.2 红兄子与兄S不在同一侧：S和该红兄子交换颜色 --> P-S(红)-S子红(黑)形成 > 或 按2.2.1进行调整 全部代码 #include #include #include typedef enum _node_color{ RED = 1, BLACK } EN_NODE_COLOR; typedef int KEY_TYPE; typedef struct _rbtree_node { unsigned char color; KEY_TYPE key; void *value; struct _rbtree_node *left; struct _rbtree_node *right; struct _rbtree_node *parent; } ST_RBTREE_NODE; typedef struct _rbtree { ST_RBTREE_NODE *root; ST_RBTREE_NODE *nil; } ST_RBTREE; ST_RBTREE_NODE *rbtree_mini(ST_RBTREE *T, ST_RBTREE_NODE *x) { while (x->left != T->nil) { x = x->left; } return x; } ST_RBTREE_NODE *rbtree_successor(ST_RBTREE *T, ST_RBTREE_NODE *x) { return rbtree_mini(T, x->right); } void rbtree_left_rotate(ST_RBTREE *T, ST_RBTREE_NODE *x) { ST_RBTREE_NODE *y = x->right; x->right = y->left; if (y->left != T->nil) { y->left->parent = x; } if (x->parent == T->nil) { T->root = y; } else if (x == x->parent->left) { x->parent->left = y; y->parent = x->parent; } else { x->parent->right = y; y->parent = x->parent; } x->parent = y; y->left = x; } void rbtree_right_rotate(ST_RBTREE *T, ST_RBTREE_NODE *x) { ST_RBTREE_NODE *y = x->left; x->left = y->right; if (y->right != T->nil) { y->right->parent = x; } if (x->parent == T->nil) { T->root = y; } else if (x == x->parent->right) { x->parent->right = y; y->parent = x->parent; } else { x->parent->left = y; y->parent = x->parent; } x->parent = y; y->right = x; } void rbtree_insert_fixup(ST_RBTREE *T, ST_RBTREE_NODE *x) { while (x->parent->color == RED) { if (x->parent == x->parent->parent->left) { ST_RBTREE_NODE *y = x->parent->parent->right; if (y->color == RED) // 叔结点为红色 { x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { if (x == x->parent->right) // 为 < 形式 { x = x->parent; rbtree_left_rotate(T, x); } x->parent->color = BLACK; // 为 / 形式 x->parent->parent->color = RED; rbtree_right_rotate(T, x->parent->parent); } } else { ST_RBTREE_NODE *y = x->parent->parent->left; if (y->color == RED) // 叔结点为红色 { x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { if (x == x->parent->left) // 为 > 形式 { x = x->parent; rbtree_right_rotate(T, x); } x->parent->color = BLACK; // 为 \ 形式 x->parent->parent->color = RED; rbtree_left_rotate(T, x->parent->parent); } } } T->root->color = BLACK; } void rbtree_insert(ST_RBTREE *T, ST_RBTREE_NODE *x) { ST_RBTREE_NODE *y = T->root; ST_RBTREE_NODE *z = T->nil; while (y != T->nil) { z = y; if (x->key key) { y = y->left; } else if (x->key > y->key) { y = y->right; } else { return; } } x->parent = z; if (z == T->nil) { T->root = x; } if (x->key key) { z->left = x; } else { z->right = x; } x->left = T->nil; x->right = T->nil; x->color = RED; rbtree_insert_fixup(T, x); } void rbtree_delete_fixup(ST_RBTREE *T, ST_RBTREE_NODE *N) { while ((N != T->root) && (N->color == BLACK)) { if (N == N->parent->left) // 兄在右 { ST_RBTREE_NODE *S = N->parent->right; if (S->color == RED) // 3.2兄红 { S->color = BLACK; N->parent->color = RED; rbtree_left_rotate(T, N->parent); S = N->parent->right; } if (S->color == BLACK) // 2.兄黑 { if (S->left->color == BLACK && S->right->color == BLACK) // 2.1 兄子全黑 { S->color = RED; N = N->parent; // parent如果为红，则相当于与兄交换颜色 } else // 2.2 兄子不全黑 { if (S->right->color == BLACK) { S->left->color = BLACK; S->color = RED; rbtree_right_rotate(T, S); S = N->parent->right; } S->color = N->parent->color; S->right->color = BLACK; rbtree_left_rotate(T, S->parent); N = T->root; } } } else { ST_RBTREE_NODE *S = N->parent->left; if (S->color == RED) // 3.1兄红 { S->color = BLACK; N->parent->color = RED; rbtree_right_rotate(T, N->parent); S = N->parent->left; } if (S->color == BLACK) // 2.兄黑 { if (S->right->color == BLACK && S->left->color == BLACK) // 2.1 兄子全黑 { S->color = RED; N = N->parent; // parent如果为红，则相当于与兄交换颜色 } else // 2.2 兄子不全黑 { if (S->left->color == BLACK) { S->right->color = BLACK; S->color = RED; rbtree_left_rotate(T, S); S = N->parent->left; } S->color = N->parent->color; S->left->color = BLACK; rbtree_right_rotate(T, S->parent); N = T->root; } } } } N->color = BLACK; } ST_RBTREE_NODE *rbtree_delete(ST_RBTREE *T, ST_RBTREE_NODE *x) { ST_RBTREE_NODE *y = T->nil; ST_RBTREE_NODE *z = T->nil; if (x == T->nil) { printf("delete node is nil\n"); return T->nil; } if ((x->left == T->nil) || (x->right == T->nil)) // 子树不满 { y = x; } else { y = rbtree_successor(T, x); } if (y->left != T->nil) { z = y->left; } else if (y->right != T->nil) { z = y->right; } z->parent = y->parent; if (y->parent == T->nil) { T->root = z; } else if (y == y->parent->left) { y->parent->left = z; } else { y->parent->right = z; } if (y != x) { x->key = y->key; x->value = y->value; } if (y->color == BLACK) { rbtree_delete_fixup(T, z); } return y; } ST_RBTREE_NODE *rbtree_search(ST_RBTREE *T, KEY_TYPE key) { ST_RBTREE_NODE *x = T->root; while (x != T->nil) { if (key key) { x = x->left; } else if (key > x->key) { x = x->right; } else { return x; } } return T->nil; } void rbtree_traversal(ST_RBTREE *T, ST_RBTREE_NODE *node) { if (node != T->nil) { rbtree_traversal(T, node->left); printf("key:%d, color:%d\n", node->key, node->color); rbtree_traversal(T, node->right); } } int main(void) { int array[20] = {8, 46, 70, 82, 32, 57, 38, 92, 48, 36, 74, 45, 39, 34, 84, 42, 59, 95, 20, 75}; int len = sizeof(array) / sizeof(array[0]); ST_RBTREE_NODE *node = NULL; int i; ST_RBTREE *T = (ST_RBTREE *)malloc(sizeof(ST_RBTREE)); if (T == NULL) { printf("malloc T failed\n"); return -1; } memset(T, 0, sizeof(ST_RBTREE)); T->nil = (ST_RBTREE_NODE *)malloc(sizeof(ST_RBTREE_NODE)); if (T->nil == NULL) { printf("malloc T->nil failed\n"); free(T); return -2; } memset(T->nil, 0, sizeof(ST_RBTREE)); T->nil->color = BLACK; T->root = T->nil; node = T->nil; for (i = 0; i key = array[i]; node->color = RED; node->value = NULL; rbtree_insert(T, node); } rbtree_traversal(T, T->root); printf("-----------------------------------\n"); ST_RBTREE_NODE *del_cur = T->nil; rbtree_delete(T, rbtree_search(T, 74)); if (del_cur != T->nil) { free(del_cur); del_cur = NULL; } rbtree_traversal(T, T->root); return 0; } 总结用到红黑树的地方参考文章：https://www.cnblogs.com/but999/p/12643956.html java8 hashmap中链表转红黑树。epoll在内核中的实现，用红黑树管理事件块（文件描述符）。Java的TreeMap实现linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块nginx中，用红黑树管理timer |
【本文地址】
今日新闻 |
推荐新闻 |