红黑树的性质：
- 每个结点是红色或者黑色
- 根结点是黑色的
- 每个叶子节点是黑色的
- 如果一个结点红色的，则它的两个儿子都是黑色的
- 对每个结点，从该结点到其子孙结点的所有路径上的包含相同数目的黑结点。（红黑树的平衡，黑高！）
红黑树的用处：
- map-->
- nginx-->
- 定时器
- cfs(进程的调度)
- 内存管理 （key -->起始位置 +value -->长度）
块内存管理的两种表示方法：1. 起始位置+长度；2.开始位置+结束位置
红黑树的使用情况：
- key, value --> 查找
- 中序遍历是顺序的。（例cfs, 查找速度快且有序）
红黑树的实现：
1. 结点的定义：
typedef int KEY_TYPE; //六点属性，颜色、左子树、右子树、父亲、key /value typedef struct _rbtree_node { unsigned char color; struct _rbtree_node *right; struct _rbtree_node *left; struct _rbtree_node *parent; KEY_TYPE key; void *value; //万能指针 } rbtree_node;
2. 红黑树定义：
1. typedef struct _rbtree { 2. rbtree_node *root; 3. rbtree_node *nil; // 通用的叶子结点，所有的也叶子结点都指向同一个位置 4. } rbtree;
1、2完成就完成红黑树的轮廓
3. 红黑树的结点旋转：
三个方向六个指针
左旋代码：
void rbtree_left_rotate(rbtree *T, rbtree_node *x) { rbtree_node *y = x->right; // x --> y , y --> x, right --> left, left --> right x->right = y->left; //1 1 if (y->left != T->nil) { //1 2 y->left->parent = x; } y->parent = x->parent; //1 3 if (x->parent == T->nil) { //1 4 T->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; //1 5 x->parent = y; //1 6 }
右旋把左旋的 x-->y , y-->x, left-->right, right-->left 代码如下：
void rbtree_right_rotate(rbtree *T, rbtree_node *y) { rbtree_node *x = y->left; y->left = x->right; if (x->right != T->nil) { x->right->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; }
4. 红黑树的插入：
//两个参数：1. 插入那棵树；2. 插入的结点 void rbtree_insert(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; rbtree_node *x = T->root; while (x != T->nil) { y = x; //保持 y 是 x 的父结点 if (z->key < x->key) { x = x->left; //可以单独做一个函数key_compare(KEY_TYPE* a, KEY_TYPE* a),红黑树可做成模板。 } 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); //插入修复 }
5. 红黑树的修复：
大的前提：插入当前节点前就是红黑树！！要不要牵扯到祖父节点的颜色。黑色
- 当前节点是红色
- 父节点是红色
- -->推断祖父节点是黑色
-->叔父节点是红色或者黑色
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) { //while 递归向上直到根节点 while (z->parent->color == RED) { //z ---> RED if (z->parent == z->parent->parent->left) { rbtree_node *y = z->parent->parent->right; //y 是叔父节点 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; //始终将根节点置为黑色 }
