一、引入：
在理想情况下，二叉搜索树增删查改的时间复杂度为O(logN)。但是，在插入数据的时候，可能会导致树会倾斜，不同的插入顺序会导致树的高度不一样，树的高度决定了它查找的时间复杂度。例如，最坏的情况下是所有的节点都在一条斜线上，这样树的高度为N，查找的时间复杂度直接退化为O(N)。
基于二叉搜索树存在的问题，一种新的树——平衡二叉查找树产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。
最坏情况下例子：当插入顺序为 5-6-7-8-9-15-18时，二叉搜索树退化为链表，当查找18时，需要进行7次查找，时间复杂度为O(N)。
二、红黑二叉树的定义：
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。
在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
1.节点是红色或黑色。
2.根是黑色。
3.所有叶子都是黑色（叶子是NIL节点）。
4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
正是红黑树的这5条性质，使一棵n个节点的红黑树始终保持了logN的高度，使得红黑树的查找、插入、删除的时间复杂度最坏为O(logN)。
三、旋转：
当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对节点进行重新着色，以及对树进行相关的旋转操作，来达到对红黑树进行插入或删除节点等操作后继续保持它的性质或平衡的目的。
红黑树的旋转操作，准确地说是二叉树的旋转操作，也就是在二叉树中的一种子树调整操作, 旋转并不影响对该二叉树进行中序遍历的结果，也就是旋转前后两棵树上的节点直线投影来的序列一样的，这样旋转不会违反节点的大小关系(即左小右大)。树旋转通常应用于需要调整树的局部平衡性的场合。旋转分为左旋转和右旋转。
左旋转：
如上图所示：以pivot节点为图心，向左旋转，此时pivot右子节点Y上升替代pivot原来位置，再将pivot右节点指向Y左节点，Y左节点指向pivot，左旋转操作完成。
右旋转：
右旋与左旋差不多，不做详细介绍。
四、插入操作：
首先，所以新增的节点都标记为红色。（如果标记 为黑色，就会导致根到叶子的路径上，有一条路径多一个额外的黑节点，破坏了红黑树的性质5。）
以下插入情景不会对红黑树造成性质破坏：
情景1：插入节点作为根节点的子节点
情景2：插入节点的父结节点是黑色的
以下插入情景需要修复:
情景1：当前节点为根节点，将根节点染成黑色即可。
情景2：插入节点的父节点为红色：
情景2.1：叔节点存在，并且为红色，将父叔节点染为黑色，将祖父节点染为红色，并且再以祖父节点为当前节点，进行递归处理，直到当前节点的父节点为黑色。
情景2.2：父节点为祖父节点的右子树，叔节点不存在，或者为黑色。
情景2.2.1：插入节点为其父节点的右子节点，以祖父节点为圈心左旋转，再将父节点染色为黑色，将祖父节点染为红色。
情景2.2.2：插入节点为其父节点的左子节点，以父节点为圆心进行右旋转，得到情景（2.2.1）然后将父节点设置为当前节点进行递归处理。
情景2.3：父节点为祖父节点的左子树，叔节点不存在，或者为黑色。
情景2.3.1：插入节点为其父节点的左子节点，与情景2.2.1为镜像结构，只需要将对应的左旋转变成右旋转，右旋转变成左旋转即可。
情景2.3.2：插入节点为其父节点的右子节点。与情景2.2.2为镜像结构，只需要将对应的左旋变成右旋转，右旋转变成左旋转即可。
五、 插入总结：
在上面两种修复情况当中第二种是不会改变所在子树的黑色路径长度的，只有第一种情况可能改变黑色路径长度，因为它可能子树根节点涂红，如果子树根节点就是整棵树的根节点时，在修复结束后会被重新设置成黑色，黑色路径长度就加1了，但这个时候黑色路径增加针对的不再是这个子树了，而是整颗红黑树，所以是不会破坏性质5的。至于性质4看修补后的图中结点的颜色就知道是不会破坏了。
插入结束之后，这颗子树的满足了性质4(不能有两个连续的红色节点)和性质5(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点)，又是一颗新的红黑树了。
六：简单实现：
红黑树及节点节点定义：
//红黑定义
public static final boolean RED =true;
public static final boolean BLACK =false;
//树根的引用
private RBNoderoot;
static class RBNode<K extends Comparable<K>, V> {
private RBNodeparent;
private RBNodeleft;
private RBNoderight;
private boolean color;
private K key;
private V value;
}
旋转操作：
private void leftRotate(RBNode x) { //左旋方法
RBNode y = x.right;
// 1.将x的右子节点指向y的左子节点,将y的左子节点的父节点更新为x
x.right = y.left;
if (y.left !=null)
y.left.parent = x;
if (x.parent !=null) { //2.当x的父节点（不为空时） ，更新y的父节点为x的父节点，并将x的父节点指定为y
y.parent = x.parent;
if (x == x.parent.left)
x.parent.left = y;
else
x.parent.right = y;
}else {
this.root = y;
this.root.parent =null;
}
//3.将x的父节点更新为y，将y的左子节点更新为x
x.parent = y;
y.left = x;
}
private void rightRotate(RBNode y) { //右旋方法
RBNode x = y.left;
//1.将y的左子节点指向x的右子节点，并且更新x的右子节点的父节点为y
y.left = x.right;
if (x.right !=null)
x.right.parent = y;
//2.当y的父节点不为空时，更新x的父节点为y的父节点，更新y的父节点的指定为x
if (y.parent !=null) {
x.parent = y.parent;
if (y == y.parent.left)
y.parent.left = x;
else
y.parent.right = x;
}else {
this.root = y;
this.root.parent =null;
}
//3.更新y的父节点为x，更新x的右子节点为y
y.parent = x;
x.right = y;
}
插入操作：
public void insert(RBNode node) {
//查找当前node的父节点
RBNode parent =null;
RBNode x =this.root;
while (x !=null) {
parent = x;
//cmp>0 说明node.key 大于 x.key 需要x的右子树查找
//cmp==0 说明node.key 等于 x.key 说明需要进行替换操作
//cmp<0 说明node.key 小于 x.key 需要x的左子树查找
int cmp = node.key.compareTo(x.key);
if (cmp >0)
x = x.right;
else if (cmp ==0) {
x.setValue(node.getValue());
return;
}else
x = x.left;
}
node.parent = parent;
if (parent !=null) {
//判断node应该插入parent的左节点还是右节点
int cmp = node.key.compareTo(parent.key);
if (cmp >0)
parent.right = node;
else
parent.left = node;
}else
this.root = node;
//进行红黑树平衡
insertFixUp(node);
}
修复：
private void insertFixUp(RBNode node) {
this.root.setColor(BLACK);
RBNode parent = parentOf(node);
RBNode Gparent = parentOf(parent);
//插入节点的父节点为红色
if (parent !=null && isRed(parent)) {
//如果父节点是红色，那么一定存在祖父节点。因为根节点不可能是红色
RBNode uncle =null;
if (parent == Gparent.left) {//父节点为祖父节点的左子树
uncle = Gparent.right;
//叔节点存在，并且为红色
if (uncle !=null && isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(Gparent);
insertFixUp(Gparent);
return;
}
if (uncle ==null || isBlack(uncle)) { //叔节点不存在，或者为黑色
if (node == parent.left) {
setBlack(parent);
setRed(Gparent);
rightRotate(Gparent);
return;
}
if (node == parent.right) { //插入节点为其父节点的右子节点
leftRotate(parent);
insertFixUp(parent);
return;
}
}
}else { //父节点为爷节点的右子数
uncle = Gparent.left;
if (uncle !=null && isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(Gparent);
insertFixUp(Gparent);
return;
}
if (uncle ==null || isBlack(uncle)) { //插入节点为其父节点的左子节点
if (node == parent.right) {
setBlack(parent);
setRed(Gparent);
leftRotate(Gparent);
return;
}
if (node == parent.left) { //插入节点为其父节点的右子节点
rightRotate(parent);
insertFixUp(parent);
return;
}
}
}
}
}
