介绍
红黑树是网红，应用非常广泛。对于二叉排序树，有些极端的情况下会转成链表，降低了效率，所以引入了平衡因子，而对于AVL平衡树是强平衡，实现起来较复杂；所以引入了弱平衡的红黑树。
定义性质
1 每个结点都是红的或黑的
2 根结点为黑
3 叶子结点为黑
4 若一个结点为红，则两个儿子都是黑
5 对于每个结点，从该结点到其子孙结点的所有路径上包含相同的黑结点高度。
应用
两种用法：
a) key_value方式用于查找，性能快O(logn)
b) 使用中序遍历（注意层次遍历和中序遍历是一样的）
应用：
1 Linux进度调度CFS
2 Nginx Timer事件管理
3 Epoll事件块处理等
旋转
三个方向，六根指针进行操作
//左旋 参数：红黑树T,当前结点轴心 void rbtree_left_rotate(rbtree *T, rbstree_node *x){ rbtree_node *y = x->right; //x y 都拿到了 //1 第一步 x的柚子树指向y的左子树 x->right = y->left; //2 第二步 y的左子树不等nil if (y->left != T->nil){ y->left->parent = x; } //3 第三部 y的parent指向原来x的parent y->parent = x->parent; //4 第四部 x的parent为nil,则x是根结点 if (x->parent == T->nil){ T->root = y; }else if(x == x->parent->left){ x->parent->left = y; }else{ x->parent->right = y; } //5 第五部 y->left = x; //6 第六部 x->parent = y; } //右旋 的基础上 x-->y y-->x left-->right right-->left void rbtree_right_rotate(rbtree *T, rbstree_node *x){ rbtree_node *x = y->left; //x y 都拿到了 y->left = x->right; if (x->right != T->nil){ x->left->parent = y; } x->parent = y->parent; if (y->parent == T->nil){ T->root = x; }else if(y == y->parent->right){ y->parent->right = x; }else{ y->parent->left = x; } x->right = y; y->parent = x; }
添加
三种情况：
父节点是祖父结点的左子树情况
1 叔结点是红色
2 叔结点是黑色，且当前结点是右子树
3 叔结点是黑色，且当前结点是左子树
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) { while (z->parent->color == RED) { //z ---> RED if (z->parent == z->parent->parent->left) { rbtree_node *y = z->parent->parent->right; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; //z --> RED } else { if (z == z->parent->right) { z = z->parent; rbtree_left_rotate(T, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rbtree_right_rotate(T, z->parent->parent); } }else { rbtree_node *y = z->parent->parent->left; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; //z --> RED } else { if (z == z->parent->left) { z = z->parent; rbtree_right_rotate(T, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rbtree_left_rotate(T, z->parent->parent); } } } T->root->color = BLACK; } void rbtree_insert(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; rbtree_node *x = T->root; //找到z指定的位置 while (x != T->nil) { y = x; if (z->key < x->key) { x = x->left; } else if (z->key > x->key) { x = x->right; } else { //Exist return ; } } z->parent = y; if (y == T->nil) { T->root = z; } else if (z->key < y->key) { y->left = z; } else { y->right = z; } z->left = T->nil; z->right = T->nil; z->color = RED; rbtree_insert_fixup(T, z); }
删除
void rbtree_delete_fixup(rbtree *T, rbtree_node *x) { while ((x != T->root) && (x->color == BLACK)) { if (x == x->parent->left) { rbtree_node *w= x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rbtree_left_rotate(T, x->parent); w = x->parent->right; } if ((w->left->color == BLACK) && (w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rbtree_right_rotate(T, w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; rbtree_left_rotate(T, x->parent); x = T->root; } } else { rbtree_node *w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rbtree_right_rotate(T, x->parent); w = x->parent->left; } if ((w->left->color == BLACK) && (w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; rbtree_left_rotate(T, w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rbtree_right_rotate(T, x->parent); x = T->root; } } } x->color = BLACK; } rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; rbtree_node *x = T->nil; //1 当前就只有一个结点 if ((z->left == T->nil) || (z->right == T->nil)) { y = z; } else { y = rbtree_successor(T, z); } if (y->left != T->nil) { x = y->left; } else if (y->right != T->nil) { x = y->right; } x->parent = y->parent; if (y->parent == T->nil) { T->root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } if (y != z) { z->key = y->key; z->value = y->value; } if (y->color == BLACK) { rbtree_delete_fixup(T, x); } return y; }
完整代码
https://github.com/hengfengyaoren/Data-Structure-Algorithm/blob/main/rbtree.c
