上一章我们介绍了二叉搜索树，文末说了二叉搜索树的不足，如果搜索树的高度较低时，这些集合操作会执行的较快，然而，如果树的高度较高时，这些集合操作可能并不比在链表上执行的快，红黑树（red-black tree）是许多"平衡"搜索树的一种，可以保证在最坏的情况下基本动态集合操作的时间复杂度为O(lgn)。
性质
红黑树是一颗二叉搜索树，它在每个节点上增加一个存储位来表示节点颜色（red或black），通过对任何一条从根到叶子节点的简单路径上各个节点的颜色来进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因为是近似平衡的。
树中每个节点包含5个属性：color、key、left、right、和p。
性质1：节点是红色或黑色。
性质2：根节点是黑色。
性质3：所有叶子都是黑色（叶子是NIL节点）。
性质4：每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图就是一颗简单的红黑树。其中Nil为叶子结点，并且它是黑色的。(值得提醒注意的是，在Java中，叶子结点是为null的结点。)
为了后面讲解不至于混淆，我们还需要来约定下红黑树一些结点的叫法，如下图所示。
旋转
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。
-
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图。
-
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图。
变色：结点的颜色由红变黑或由黑变红。
可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。
所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。
但要保持红黑树的性质，结点不能乱挪，还得靠变色了。怎么变？具体情景又不同变法，后面会具体讲到，现在只需要记住红黑树总是通过旋转和变色达到自平衡。
红黑树查找
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
1、从根结点开始查找，把根结点设置为当前结点；
2、若当前结点为空，返回null；
3、若当前结点不为空，用当前结点的key跟查找key作比较；
4、若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
5、若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
6、若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；
如下图所示：
红黑树插入
插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。
我们首先以二叉查找树的方法增加节点并标记为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。）下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。
情形1： 红黑树为空树
最简单的一种情景，直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。
情形2： 插入结点的父结点为黑色结点
由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
情形3： 插入结点的父结点为红色结点
这种情况的子情况比较多，下面用脑图进行分类展示，方便有一个宏观的印象。
3.1：叔叔结点存在并且为红结点
从红黑树性质4可以，祖父结点肯定为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。
3.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点,插入结点是其父结点的左子结点
3.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点,插入结点是其父结点的右子结点
这种情景显然可以转换为情景3.2
3.4：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点,插入结点是其父结点的右子结点
3.5：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点,插入结点是其父结点的左子结点
综合练习
请画出下图的插入自平衡处理过程。
