一、什么是红黑树
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。 由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
左旋或者右旋，就是修改6个指针
二、定义红黑树
typedef int KEY_TYPE; 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; typedef struct _rbtree { rbtree_node *root; rbtree_node *nil;//定义一个通用叶子节点，因为叶子节点是黑，并且左右子树都为空， 直接定义一个通用的叶子节点，如果节点是这个公共的叶子节点，那么就判断当前节点是叶子节点 } rbtree;
三、左旋和右旋
左旋
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 x的parent是空的，也就是说x是根节点 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; }
四、红黑树插入节点
如果要插入一个节点，就要插入到最底层的非叶子节点（因为叶子节点不显示）
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; } 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);//修复 }
当父节点是红色的时候才需要调整
1.父节点是红色
2.祖父节点是黑色(因为插入前就是一颗红黑树，红色的子节点一定是黑色)
3.叔节点 可能是 红色 也可能是 黑色
1.当父节点和叔节点都是红色的时候
（比如插入370）
因为插入的是红色的节点，只需要把父和叔节点都变黑色，祖父节点变成红色…
那么会不会出现祖父节点和祖父的父节点都是红色的情况呢？
可能会。那就需要从下往上调整了，z = z->parent->parent，把当前节点变成祖父节点，可以发现z一定是红色的，自下往上修复就行了,所以需要一个while。
2.当叔节点是黑节点时(包括隐藏的叶子节点的情况)
比如要插入350
如果插入为父节点的右节点，那么就额外需要一步左旋 从（1）开始
如果插入为父节点的左节点，那么就从(2)开始
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;//由于可能存在把根节点置为红色的情况，因此把根节点置为黑色 }
