在二叉树中已经探讨过。假设依照随机顺序插入树节点，绝大多数都会出现不平衡的情况。最坏的情况。插入的数据时有序的，二叉树将会变成链表，插入、删除的效率将会严重地减少
下图就是依照数据升序的顺序插入二叉树的情况：
红黑树就是一种解决非平衡树的方法，它是添加了某些特点的二叉搜索树
为了能较快的时间来搜索一颗树，须要保证树总是平衡的（或者至少大部分是平衡的），就是说对树中的每个节点，它左边的后代数量和它右边的后代数量应该大致相等
红黑规则
当插入（或者删除）一个节点时。必须遵循一定的规则，它们被称为红黑规则。
假设遵循这些规则。树就是平衡的
1、每个节点不是黑色就是红色
2、根总是黑色的
3、假设节点是红色的。则它的子节点必须是黑色的，反之则不一定成立
4、从根到叶节点或空子节点的每条路径，必须包括同样数目的黑色节点
规则4中的空子节点是指非叶节点能够接子节点的位置。换句话说。就是一个有右子节点的可能接左子节点的位置，或者是有左子节点的节点可能接右子节点的位置。
从根节点到叶节点路径上的黑色节点的数目被称为黑色高度
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
结果是这个树大致上是平衡的。
由于操作比方插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例。这个在高度上的理论上限同意红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到规则4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。由于依据规则4全部最长的路径都有同样数目的黑色节点，这就表明了没有路径能多于不论什么其它路径的两倍长。
算法分析
首先。当插入第一个节点时。这个节点就是根节点，所以必须是黑色的
在添加新的节点的时候，我们先默认新节点都是红色的。为什么呢？由于插入一个红色节点违背红黑规则的可能性比插入一个黑色节点的要小。插入一个红色节点，肯定不会改变树的黑色高度；另外，假设插入节点的父节点是黑色节点。不会违背父子节点同一时候为红色的规则，假设插入节点的父节点是红色节点才会违背这一规则，这个时候就须要对树进行变换来适应规则。
还有一点就是，违背规则3（父子节点都是红色）比违背规则4（黑色高度不同）要easy修正
以下我们来进行一些实验。依次插入50，25。75，就得到了以下这可二叉树
这棵树符合上面所列出的红黑规则，它是一颗平衡树
颜色变换
接下来，我们再添加一个值为12的新节点。
依照二叉搜索树的规则，12应该插入25的左子节点，可是，由于我们默认新节点都是红色的，而25也是红色的，父子节点不能同一时候都为红色。这时就须要对25的父节点和其父节点的右子节点进行颜色变换，为什么还要对其父节点的右子节点也进行变换呢？试想，假设我们仅仅将25变换成黑色而75保持红色不变。那么插入新节点之后。根节点的左子树的黑色高度势必会比右子树大1，这就违背了红黑规则
实际上，这样的情况下，一般也须要将25的父节点变换颜色，由于此时25的父节点是根节点。所以保持黑色不变
插入12之后，生成以下的红黑树：
这时二叉树显得有一点不平衡。可是仍然符合红黑规则
接下来，我们再插入一个值为6的新节点。
问题出现了，6的父节点为12。红色，而新节点也是红色，违背了红黑原则。
假设将6变换成黑色，则6到跟的黑色高度为3，而75到跟的高度为2，同样违背了红黑规则
依照上面的经验。假设我们将12和25的颜色都变换掉呢？
可见。仍然违背了红黑规则
就是说。一棵树假设超过了两层不平衡（一边的子树比还有一边的子树高两层以上）。是不可能满足红黑规则的，由于假设一条路径上的节点数比还有一条路径上的节点数多一个以上，那它或者有很多其它的黑色节点。或者有两个相邻的红色节点，都会违背红黑规则。
我们陷入了一个困境。看来仅靠颜色变换是无法走出这个死胡同的。这时候就须要通过另外的途径来对红黑树进行变换了。
旋转
为了平衡一棵树，须要又一次手动地排列节点。假设大部分节点都在某个參照点左側，就须要把一些节点移到右側，成为右旋。假设大部分节点都在某个參照点右側，就须要把一些节点移到左側，成为左旋。
这里所说的左旋与右旋是相对于參照点而言的
来看一个实例：
以根为中心。进行一次右旋之后的结果例如以下：
右旋的时候，以50为中心，周围的节点进行了顺时针旋转
假设我们已上图中的25为中心，进行一次逆向操作——左旋，将25周围的节点进行逆时针旋转，就又回到了旋转之前的样子
须要注意的时。旋转的时候仍然要遵循搜索二叉树的规则。
比方在对第一幅图中的树进行右旋的时候，节点25以50为中心顺时针旋转，仅仅能旋转到50的左上方，由于25比50小；而75比50大，不能再沿着顺时针方向转动了。所以它仍然在50的右下方保持相对位置不变。
不管是左旋还是右旋，比该节点小的值仅仅能在该节点则左下方或者左上方；比该节点大的值仅仅能在该节点的右下方或者右上方。这样才符合搜索二叉树的规则。
事实上，旋转远比上面的简单样例要复杂，再来看一个样例：
我们对一个两层、五个节点的树进行右旋，75比50大，仍然在50的右下方，而25比50小，从50的左下方移到了50的左上方，12作为25的左子节点没有变，可是所在层数有第三层变成了第二层。
能够发现，以50为中心右旋之后。50右側的节点都下降了一个层级（包括50本身），而50左側的节点都上升了一个层级。
可是，当中发生了一件奇怪的事，就是37从直观上来看。放生了横向移动，从左子树移动到了右子树。
让我们分析一下出现这样的情况的原因：左子树集体升高了一个层级，37作为25的右子节点，本来也应该水涨船高，随着50上升一个层级。可是，此时25的右子节点已经被50先入为主的占领了，如此一来，37仅仅好沿着右子树又一次找家，最后就仅仅能委屈地在50的左下方扎根。
在上例中中，37就被称为50节点右旋操作的内側子孙，而12就是外側子孙。
事实上，整棵子树也会发生集体的移动。比方：
