但是，当插入的一组元素正好是有序的时候，排序二叉树就变成了下边这样了，就变成了普通的链表结构，如下图所示:

正常情况下的排序二叉树检索效率类似于二分查找，二分查找的时间复杂度为 O(log n)，但是如果排序二叉树退化成链表结构，那么检索效率就变成了线性的 O(n) 的，这样相对于 O(log n) 来说，检索效率肯定是要差不少的。

思考，二分查找和正常的排序二叉树的时间复杂度都是 O(log n)，那么为什么是O(log n) ？

关于 O(log n) 的分析下面这篇文章讲解的非常好，感兴趣的可以看下这篇文章 ，文章是拿二分查找来举例的，二分查找和平衡二叉树的时间复杂度是一样的，理解了二分查找的时间复杂度，再来理解平衡二叉树就不难了，这里就不赘述了。

继续回到我们的主题上，为了解决排序二叉树在特殊情况下会退化成链表的问题（链表的检索效率是 O(n) 相对正常二叉树来说要差不少），所以有人发明了平衡二叉树和红黑树类似的平衡树。

平衡二叉数又被称为 AVL 树，AVL 树的名字来源于它的发明作者 G.M. Adelson-Velsky 和 E.M. Landis，取自两人名字的首字母。

官方定义：它或者是一颗空树，或者具有以下性质的排序二叉树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

两个条件：

• 平衡二叉树必须是排序二叉树，也就是说平衡二叉树他的左子树所有节点的值必须小于根节点的值，它的右子树上所有节点的值必须大于它的根节点的值。
• 左子树和右子树的深度之差的绝对值不超过1。

讲了这么多概念，接下来主角红黑树终于要上场了。

为什么有红黑树？

其实红黑树和上面的平衡二叉树类似，本质上都是为了解决排序二叉树在极端情况下退化成链表导致检索效率大大降低的问题，红黑树最早是由 Rudolf Bayer 于 1972 年发明的。

红黑树首先肯定是一个排序二叉树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是 RED 或 BLACK 。

Java 中实现红黑树大概结构图如下所示：

红黑树的特性

• 性质1：每个节点要么是红色，要么是黑色。
• 性质2：根节点永远是黑色的。
• 性质3：所有的叶子节点都是空节点（即null），并且是黑色的。
• 性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点。）
• 性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

针对上面的 5 种性质，我们简单理解下，对于性质 1 和性质 2 ，相当于是对红黑树每个节点的约束，根节点是黑色，其他的节点要么是红色，要么是黑色。

对于性质 3 中指定红黑树的每个叶子节点都是空节点，而且叶子节点都是黑色，但 Java 实现的红黑树会使用 null 来代表空节点，因此我们在遍历 Java里的红黑树的时候会看不到叶子节点，而看到的是每个叶子节点都是红色的，这一点需要注意。

对于性质 5，这里我们需要注意的是，这里的描述是从任一节点，从任一节点到它的子树的每个叶子节点黑色节点的数量都是相同的，这个数量被称为这个节点的黑高。

如果我们从根节点出发到每个叶子节点的路径都包含相同数量的黑色节点，这个黑色节点的数量被称为树的黑色高度。树的黑色高度和节点的黑色高度是不一样的，这里要注意区分。

其实到这里有人可能会问了，红黑树的性质说了一大堆，那是不是说只要保证红黑树的节点是红黑交替就能保证树是平衡的呢？

其实不是这样的，我们可以看来看下面这张图：

左边的子树都是黑色节点，但是这个红黑树依然是平衡的，5 条性质它都满足。

这个树的黑色高度为 3，从根节点到叶子节点的最短路径长度是 2，该路径上全是黑色节点，包括叶子节点，从根节点到叶子节点最长路径为 4，每个黑色节点之间会插入红色节点。

通过上面的性质 4 和性质 5，其实上保证了没有任何一条路径会比其他路径长出两倍，所以这样的红黑树是平衡的。

其实这算是一个推论，红黑树在最差情况下，最长的路径都不会比最短的路径长出两倍。其实红黑树并不是真正的平衡二叉树，它只能保证大致是平衡的，因为红黑树的高度不会无限增高，在实际应用用，红黑树的统计性能要高于平衡二叉树，但极端性能略差。

红黑树的插入

想要彻底理解红黑树，除了上面说到的理解红黑树的性质以外，就是理解红黑树的插入操作了。

红黑树的插入和普通排序二叉树的插入基本一致，排序二叉树的要求是左子树上的所有节点都要比根节点小，右子树上的所有节点都要比跟节点大，当插入一个新的节点的时候，首先要找到当前要插入的节点适合放在排序二叉树哪个位置，然后插入当前节点即可。红黑树和排序二叉树不同的是，红黑树需要在插入节点调整树的结构来让树保持平衡。

一般情况下，红黑树中新插入的节点都是红色的，那么，为什么说新加入到红黑树中的节点要是红色的呢？

这个问题可以这样理解，我们从性质5中知道，当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的，此时假如新的黑色节点的话，必然破坏规则，但加入红色节点却不一定，除非其父节点就是红色节点，因此加入红色节点，破坏规则的可能性小一些。

接下来我们重点来讲红黑树插入新节点后是如何保持平衡的。

给定下面这样一颗红黑树：