上一篇写了关于红黑树基本性质的东西，这篇来说一说如何创建一棵红黑树吧。
红黑树是一种二叉查找树，那么我们可以使用插入的方法来创建一棵红黑树，为此，我们先来介绍关于红黑树的一些基本操作。
1. 旋转
旋转是一种能保持二叉查找树性质的查找树局部操作，包括左旋和右旋两种操作。
如下图所示，在x结点上做左旋时，我们假设它的右孩子不是nil[T]；x可以是树内任意右孩子不是nil[T]的结点。算法导论里面讲到“左旋以x到y之间的链为支轴进行。”我没太理解这句话，但是我是这么想象的，如下图中的曲线箭头所示，左旋就是x下移，y上移，箭头所示方向为左，右旋就是x上移，y下移，箭头所示方向为右。
值得注意的是，在旋转过程中，只会有指针结构的变化，不会有颜色的变化，因此在上面的图中，我没有画出结点的颜色。
旋转的伪代码，我就不写了，在算法导论里面都有，下面我把我写的旋转代码给贴过来吧，当然还是Java版的。
2. 插入
我们来分析一下，在插入过程中可能违反的性质有哪几个。为此，我把红黑树的性质再抄写一次。
一棵二叉查找树如果满足下面的红黑性质，则为一棵红黑树：
1) 每个结点是或是红的，或是黑的。
2) 根结点是黑的。
3) 每个叶结点（nil[T]）是黑的。
4) 如果一个结点是红的，那么它的两个儿子是黑的。
5) 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
首先，我们插入的结点是红色的，因此不会违反性质1)和性质5)，性质3)自然成立。唯一可能被破坏的是2)和4)。而且，2)和4)至多有一个性质被破坏。性质2)被破坏时的修复很简单，只需要将根结点重新着色为黑色即可。而性质4)被破坏的修复则要复杂一些，具体分为三种请况。
情况1)：z的叔叔y是红色的。
如下图所示，如果z的叔叔y是红色的，将z的父结点和y着色为黑色，然后将z的祖父结点着色为红色，最后将z的祖父结点作为新的z结点进行迭代检查，因为z的祖父结点原来是红色的，被着色为黑色的时候，有可能会引起红黑树性质的破坏。
情况2)：z的叔叔y是黑色的，而且z是右孩子。
情况3)：z的叔叔y是黑色的，而且z是左孩子。
如下图所示，如果是情况2)，我们可以立即使用一个左旋变成情况3)。情况3)中，首先交换了B和C的颜色，然后通过一个右旋来使整个树达到了满足性质4)。
从这三种情况来看，可以发现一个非常有趣的事情，那就是该过程所做的旋转从不超过两次，因为只有情况1)会继续将z上移进行红黑性质检查，而一旦进入了情况2)或者情况3)，就不会再进行检查了。
同样，伪代码就不写了，算法导论上都有，在此只写Java实现代码。
ps：写博客很累，转载的朋友请注明出处，谢谢。