红黑树概念
- 每个结点是红的或者黑的；
- 根结点是黑色的；
- 每个叶子结点是黑色的；
- 如果一个结点是红色的，则它的两个儿子都是黑色的；
- 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑节点；
红黑树特点
保持红黑树中黑数高度平衡
红黑树的左右子树的高度差最大相差2n-1
黑色高度（black-height）: 红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）.
红黑树路径：黑色高度为n的红黑树，从根结点到叶结点的简单路径的最短长度为(n-1)，最大长度为2(n-1)。
**红黑树时间复杂度 O(log2(N))
红黑树使用场景
红黑树的使用场景就是利用了红黑树的特点。
红黑树重查找，利用key就可以快速的查找红黑树中序遍历是有序的特征
内存管理
内存表示有两种，1> 首地址+长度；2>首地址+尾地址
内存管理中 使用1> 表示内存。使用红黑树的key 指向每一块内存的首地址，value 存储内存长度。 分配一块内存就在红黑树中添加一个节点。释放一块内存就在红黑树中删除一个节点。
进程调度CFS中
进程调度过程当中进程的集合。n个进程用红黑树存储。在调度过程当中查找最小的值来调度。利用红黑树的中序遍历是有序的特点。能够快速的找到最小值。在存储过程当中把调度时间当作key值来存储。
红黑树的实现
该红黑树隐藏了叶子节点，所有的叶子节点都是黑色的。
红黑树实现结构体
#define KEY_TYPE int #deifne RET 1; #define BLACK 0; typedef struct _rbtree_node_s rbtree_node_t; /* 定义一颗红黑树结点*/ struct _rbtree_node_s { unsigned char color; /* 红黑树颜色*/ struct _rbtree_node_s *left; /* 左子树结点*/ struct _rbtree_node_s *right; /* 右子树结点*/ struct _rbtree_node_s *parent; /* 父结点*/ KEY_TYPE keys; /* keys 值*/ voide * value; /* 通用的指针存储value 值*/ } /* 定义红黑树*/ typedef struct _rbtree_s rbtree_t; struct _rbtree_s { rbtree_node_t *root; /* 红黑树的根*/ rbtree_node_t *nil; /* 定义叶子结点*/ }
定义基础组件
红黑树左旋右旋
红黑树左旋或者右旋，一共需要旋转三个方向，修改六个指针；
左旋：
修改x结点右子树指向 y结点的左子树；
修改y结点的父节点指向x结点的父节点，x节点的父节点指向y结点；
修改y结点的左子树指向x结点，x结点的父节点指向y;
右旋组件实现的时候把左旋组件函数中 x替换成y ,y 替换成x ,right 替换成left, left 替换成right
/** * rbtree_t 表示是一颗红黑树， x 表示旋转结点 */ void _left_rotate(rbtree_t *T, rbtree_node_t *x) { rbtree_node_t *y = x->right; // x 轴心结点 // 建立x 结点右子树和y左子树结点关联 x->right = y->left; if (y->left != T->nil){ y->left->parent = x; } // 2. x 父结点和y结点建立关联 y->parent = x->parent; if (x->parent == T->nil) { T->root = y; }elst if (x == x->parent->left) { x->patent->left = y; }elst { x->parent->right = y; } // 3. x结点和y结点建立关联 y->left = x; x->parent = y; } 右旋 /** * rbtree_t 表示是一颗红黑树， x 表示旋转结点 */ void _right_rotate(rbtree_t *T, rbtree_node_t *x) { rbtree_node_t *x = y->left; // x 轴心结点 // 建立x 结点右子树和y左子树结点关联 y->left = x->right; if (x->right != T->nil){ x->right->parent = y; } // 2. x 父结点和y结点建立关联 x->parent = y->parent; if (y->parent == T->nil) { T->root = x; }elst if (y == y->parent->right) { y->patent->right = x; }elst { y->parent->left = x; } // 3. x结点和y结点建立关联 x->right = y; y->parent = x; }
红黑树调整结点
结点调整的前提是，目前该树已经是一颗红黑树 /** * rbtree_t T 表示是红黑树 * z 新插入的调整结点,Z结点是红色的不影响红黑树的高度 */ void rbtree_insert_fixup(rbtree_t *T, rbtree_node_t *z) { while(z->parent->color == RED){ if (z->parent == z->parent->parent->left){ //判断z->parent 结点是z祖父结点的左节点 rbtree_t *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; }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{ // z->parent 结点是zz祖父结点的又结点 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 *T, rbtree_node_t *z){ rbtree_node_t *y = T->nil; rbtree_node_t *x = T->root; while (x != T->nil) { y = x; if (z->key < x->key) { x = x->left; }else if (z->key > x->key){ x = x->right; } elst { /*TODO 根据具体情况填写*/ return ; } } //x 没有分支了 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; }
