1 介绍
引入：二叉排序树当本来数据列表就已经是有序的，若采用就是蜕化成链表。故引入平衡树，而对于AVL是绝对平衡的，在工业生产中应用较少，故采用平衡规则没有那么严格的相对平衡的红黑树。
本文章主要总结红黑树的性质，应用场景，以及简单的实现一个红黑树的旋转，插入，删除等操作。
应用场景：nginx定时器，内存管理，linux内核线程调度，hashmap等
常见的两种工业用法：
1 以key_value方式主要用于查找，性能快O(logn)
2 使用中序遍历，得到有序数据。
2 定义性质
1:每个节点是红的或者黑的
2:根节点是黑色的
3:每个叶子节点是黑的
4:如果一个节点是红的,则它的两个儿子都是黑的
5:对每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点
注意：主要平衡的是黑色结点的高度，而红色主要是用来做选择判断用途
3 数据结构
一般情况下业务要与红黑树的性质进行分离的，这里只是为了搞理清流程。故就暂时未分离
结点
typedef int KEY_VALUE; //结点 typedef struct _rbtree_node{ unsigned char color;//颜色 struct rbtree_node *left; //左子树 struct rbtree_node *right;//右子树 struct rbtree_node *parent; //父结点 KEY_VALUE key; void *value; //存储具体的数据 }rbtree_node;
红黑树的结构
typedef struct _rbtree{ struct _rbtree_node *root; //根结点 struct _rbtree_node *nil; //叶子结点全部隐藏 }rbtree;
4 左右旋转
旋转主要为了达到黑结点高度一致的问题
主要是操作3对指针，总共6跟指针。
左旋具体流程图：
代码实现
//红黑树的旋转 主要是为了平衡黑高 //红黑树 + 当前结点 void rbtree_left_rotate(rbtree *T, rbtree_node *x){ rbtree_node *y = x->right; // 找到轴心y结点 //x y都已经拿到 操作3对指针，6个指针 //第一步 把 x->right = y->left; if(y->left != T->nil){ y->left->parent = x;//第二步 } y->parent = x->parent; //第三步 if (x->parent == T->nil){ //第四步 //代表x是root T->root = y; }else if (x == x->parent->left){ x->parent->left = y; }else{ x->parent->right = y; } y->left = x; //第五部 x->parent = y; //第六步 }
对于右旋转：将rbtree_left_rotate函数中的x–>y y–>x right–>left left—>right
代码实现：
void rbtree_right_rotate(rbtree *T, rbtree_node *y){ // 找到轴心y结点 rbtree_node *x = y->left; //x y都已经拿到 操作3对指针，6个指针 //第一步 把 y->left = x->right; if(x->right != T->nil){ //第二步 x->right->parent = y; } //第三步 x->parent = y->parent; //第四步 if (y->parent == T->nil){ //代表x是root T->root = x; }else if (y == y->parent->right){ y->parent->right = x; }else{ y->parent->left = x; } //第五部 x->left = y; //第六步 y->parent = x; }
5 插入的三种情况
插入不会引起旋转，是插入完成后调整会引起旋转
插入之前就已经是一个红黑树，通过左旋或者右旋可以改变黑高
6 删除四种情况
完整代码参考：
https://github.com/hengfengyaoren/Data-Structure-Algorithm/blob/main/rbtree.c
