一说到红黑树，有人就特别恐惧，立马想到的是红黑树的性质啊，插入方式啊，复杂的旋转啊。网上一搜索红黑树，也是这些。基本上都是先介绍下红黑树是什么，然后介绍一下它是怎么旋转，变化的。看了之后，不一会儿又忘了。
其实我们不妨先问一下，为什么要有红黑树这种结构，它的红节点和黑节点区分开来有什么意义？为什么就不能拥有连续两个红节点呢？
想要回答这些问题，我们要先从什么是二叉树说起。
二叉树：
一个桶里有50个小球，小球上有编号1~50 。这些小球都是凌乱的放在一起。桶的洞口比较小，一次只能取1个小球出来，如果要取50号的球，运气不好的话，那么最多要取50次。但是如果是二叉树的结构就不同了，只需要取5~6次（50介于2的5次方到6次方之间)
局限：
给二叉树添加节点的时候，一直比root节点大或者比root节点小，就会退化成链表，如下图所示。那么二叉树的意义将不再存在。所以这就衍生出了平衡二叉树。一个糟糕的二叉树如下所示，根本就失去了二叉树的优势。
2-3树：
2-3树 是一颗平衡树。它的每一个节点（node) ， 拥有一个data 或者2个data ， data可以表示成
data{
Key: key;
Value: value;
}
一个data 有一个key 和一个value。
一个data 的节点我们记为 2-节点，因为它下面的子树可以有2条，左边的key都小于它，右边的key都大于它。2个data的我们记为3-节点，因为它下面的子树有3条，一个小于data1，一个在data1和data2之间，最后一个大于data2。
所以2-3就是由2-节点和3-节点组成的树。示例如下图：
2-3树的的插入
插入也无非就2种情况，一个是向2-节点插入，一个是向3-节点插入。
1. 在2-节点插入,很简单,直接变成3-节点。
２．在3-节点插入。３节点变成４-节点。
我们先结合一个具体的例子来看一下：
比如向上图中插入25：
然后变成：
往3-节点中插入数据，是讲中间节点的数据网上提，而不是讲最小的数据往上提。理论上最小的数据也可以往上提，它往上提了，比如把22 往上提，也可以使右边的数据大于上面的数据。但是如果是最小的数据往上提，变化量就太大了，显示需要查找这颗子树的最小值是多少，然后填空缺的数又得查找最小值，变动太大了，中间的数据往上提变动就会小很多。
然后，会形成一个临时的4-节点，这时，子树会分拆出来变成下面这样。注意，这一步特别重要，其实红黑树所有的旋转，颜色的改变，都和下面这一步有关。
这个时候拆分成4-节点，原来的3-节点，也拆成了2个2-节点接入到4-节点上，因为有了4-节点，所以大家可能觉得拆分成2个2-节点是是理所当然的。但是，大家可以想一下，为什么不能不拆分呢，不如像下面这样：
其实25这个节点还会往上提，最终会变成如下所示：
22,28 这个3-节点如果不拆分，当25提到和16组成3-节点的时候，22,28如果作为一个整体的话，就不知道应该插入哪里，22比25小，28又比25大，所以它们作为一个整体就不知道插入那颗子树了，所以要拆分。
红黑树
红黑树，其实就是2-3树， 红黑树的节点是由红节点和黑节点组成的，我们把连接红节点的连接称为红连接，将红黑树的红链接放平，那么就和2,3树完全等价。如下图：
红链接将两个2-节点连接起来，构成3-节点，黑连接则是2-3树中普通的连接知道了红黑树就是2-3树，那么红黑树的这些规则现在看起来也就理所当然了。
1. 节点是红色或黑色。 (2-3树分为2-节点和3-节点）
2. 根是黑色。 （没有人连它）
3. 所有叶子都是黑色（叶子是NIL节点）。空节点
4. 从每个叶子到根的所有路径上不能有两个连续的红色节点。（如果有2个相同红色节点，那么它就不是3-节点了，而是4-节点了）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。（平衡性，其实就是叶子节点到根路径节点数相同）
我们规定节点左边的链接为红链接，每个节点有red 属性，表示红节点，还是黑节点，连接红节点的链接就是红链接，连接黑节点的链接就是黑链接。每当有新节点插入的时候，我们都默认插入的是红节点（如果默认是插入的黑节点，那么就没有红节点了）。
红黑树的插入
因为规定了红链接是左链接，而插入的时候，很可能会出现右连接，这个时候就需要用到左旋转了（左边是待旋转的，右边是旋转后的）。
左转图解：
左旋转的代码如下：
rolateLeft(Nodeh){
Nodex= h.right;
x.left = h;
h.right=x.left;
x.color = h.color;
h.color = Red;
x.N=h.N;
h.N=1+size(h.left)+size(h.right);
return x;
}
右旋，就是把上面的右图，变成左图的样子。
rolateRight(Node h){
Nodex= h.left;
x.right = h;
h.left =x.right;
h.color =x.color;
x.color = red;x.N = h.N;
h.N = 1+ size(h.left) + size(h.right);returnx;
}
这两个旋转，其实也就对应了2-3树的结点拆分。
当左右节点都是红节点的时候，需要讲它变色：
flipColor(Nodeh){
h.color = Red；
h.left = BLACK;
h.right=BLACK;
}
其实插入的时候，真正遇到的情况也就下面几种
2-节点的插入
1. 在左边插入，直接变成3-节点
2. 在右边插入，需要左旋转一下
3-节点的插入：
1. 插入的值比这2个key都大，在右边插入，只需要改变一下颜色就可以了
2. 插入的值比3-节点的2个key 都小，那么会形成2个相同的子链接，那么把他们右旋转一下就可以了：
3. 插入的值介于2-3节点的2个key之间，那么先旋转，再右旋转就可以了。
综上，红黑树的插入代码如下所示：
privateput (Key key,Valueval, Node h){
int cpm = compare(key,h.key);
if (cpm <0) {
//比它小就插入左子树
h.left = put(key,val,h.left);
}else if (cpm >0) {
h.right = put(key,val,h.right);//比它大插入右子树
} else {
h.val=val;//命中
}
if(!isRed(h.left) && isRed(h.right)){
//如果h的左节点是黑，右节点是红，那么左旋转
h = rolateLeft(h);
}if(isRed(h.left) && isRed(h.right.left)){
//如果h的两个左子树都是红，那么h右旋转。
h = rolateRight(h);
}if(isRed(h.left) && isRed(h.right)){
//如果h的左节点和右节点都是红，那么变色
flipColor(h);
}
h.N = size(h.left) + size(h.right) +1;
return h;
}
我们在来看一下，红黑树插入和其对应的2-3树插入的对比：
