红黑树是avl树的变种，通过满足以下的四个条件来确保对所有的路径，它的长度不会超过其他路径的两倍，从而达到接近平衡的目的。
它要满足的四条规则是：
1.每个节点不是黑色就是红色
2.根节点为黑色
3.如果节点为红色，其子节点必须为黑色
4.任意一个节点到树尾端（null）的任何路径，所经过的黑色节点数目必须相同
红黑树的增删操作如果一但破坏了以上四条规则，就需要进行一系列的调整，使树经过调整后满足上述四个条件。
一、 红黑树的插入
当我们插入一个结点节点时根据规则4，为了保证黑色节点数相同，其必须是红色的节点。
在其插入后，为了调整树使其重新满足4条规则，我们需要分好几种情况来讨论
1.插入节点的父节点为黑色节点
如下图所示，当插入节点的父节点为黑节点时，二叉树的4条规则一条也没有打破。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。
2.插入节点的父节点为红色
由于规则3，新增节点的父节点是红色的，由于规则3，则其祖父节点必然是黑色的。这时候树肯定是不满足的条件的，需要对树进行变色或者旋转等操作对树进行改变，而具体要进行何种改变，需要根据新增节点的叔父节点的颜色的不同来决定。
（1）叔父节点为红色
当叔父节点为红色时，如下图所示
将父节点、叔父节点、祖父节点的颜色进行改变，如果由于祖父节点变红而引起了新的不满足规则，则将祖父节点当成新的新增节点，进行递归调用来满足平衡即可。
（2）叔父节点为黑色
当叔父节点为黑色时，对树进行旋转操作即可，由于新增节点插入的位置不同，旋转操作可分为以下4种：
a.
b.
c.
d.
以下为用java实现的红黑树插入的代码：
