红黑树的基本性质和旋转
红黑树的五个性质：
1，每个结点为红色或者为黑色。
2，根结点为黑色
3，叶子结点为黑色
4，红色结点的两个儿子结点为黑色
5，对于每个结点，它的每条路径上有相同数目的黑色结点。
数据结构如下:
typedef int KEY_TYPE;
typedef struct _rbtree_node{
unsigned char color;
KEY_TYPE value;
struct rbtree_node* left;
struct rbtree_node* right;
struct rbtree_node* parent;
}rbtree_node;
typedef struct _rbtree{
struct _rbtree_node* root;
struct _rbtree_node* nil;
}rbtree;
当我们插入一个结点时，默认其颜色为红色，如果插到黑色结点下面，可不用变化树形。
如果插入到红色结点下，因为不满足第4条性质，所以需要变色或者是旋转。
我们这一篇先讨论旋转，旋转分为，左旋和右旋。
左旋：
只需要三步即可完成左旋，安排！
Node* y = x ->right;
①安排y->left。
将y->left 给给 x->left
判断y->left是否存在，如果存在，将x作为 y->left->parent
②安排y->parent
将x->parent 给给 y->parent
需要判断，x是不是根节点，即判断x->parent是否为空，
若是，则把y作为新的根结点。
若不是，判断x是父节点的左/右孩子，将y 作为 父节点的左右孩子。
③安排y
将x 作为 y->left
将y 作为 x->parent
左旋代码：
void rotate_left(rbtree* T, rbtree_node* x){rbtree_node* y = x->right;x->right = y->left;if(y->left){y->left->parent = x;}y->parent = x->parent;if(x->parent == T->nil){T->root = y;}else if(x == x->parent->left){x->parent->left = y;}else{x->parent->right = y;}y->left = x;x->parent = y;}
右旋：
只需要三步也可完成右旋，继续安排！
Node* y =x->left;
①安排y->right
将y>right 给给x->left
如果y->right 存在，则把x作为 y->right->parent
②安排y->parent
将x->parent 给给y->parent
需要判断，x是不是根节点，即判断x->parent是否为空
若是，则将y作为新的根结点
若不是，则判断x是其父节点的左/右孩子，同时将y作为其父节点的左右孩子。
③安排x
将x给给y->right
将y作为x->parent。
右旋代码：
void rotate_left(rbtree* T, rbtree_node* x){rbtree_node* y = x->left;x->left= y->right;if(y->right){y->right->parent = x;}y->parent = x->parent;if(x->parent == T->nil){T->root = y;}else if(x == x->parent->right){x->parent->right= y;}else{x->parent->left= y;}y->right= x;x->parent = y;}