二叉查找树(BST)

要学习红黑树，首先我们得理解二叉查找树(Binary Search Tree)。

二叉查找树(BST)特性：
1、左子树上所有节点值均小于或等于它的根节点值
2、右子树上所有节点值均大于或等于它的根节点值
3、左右子树叶分别为二叉排序树

从上述树中查找值为10的节点的过程如下：
1、10>9，查看右子节点13
2、10<13，查看左子节点11
3、10<11，查看左子节点，找到10

这种方式正是二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。

插入节点时，也是利用类似的方法，通过一层一层比较大小，找到新节点适合的插入位置。这种插入方式带来了BST的缺陷：

向上面示例的树中依次插入：7、6、5、4、3五个节点，结果如下：

上图所示结果大大降低了树的查找性能，几乎变成了线性查找。

本人实现的BST代码可见如下地址:
https://github.com/yzy199391/javaSE/tree/master/Data-structure

红黑树(Red Black Tree)

为了解决上述BST多次插入新节点导致不平衡的问题，红黑树应运而生。

红黑树是一种自平衡的二叉查找树，除了符合BST的基本特征之外，它还有下列特征：
1、节点非红即黑
2、根节点为黑
3、叶子节点都为黑色空节点(NIL节点)
4、红色节点的两个子节点都为黑色（一条根到叶子的路径中不能出现连续两个红色节点）
5、任一节点到其每个叶子节点的路径包含的黑色节点的数目相同

ps：红黑树最长路径不会超过最短路径的两倍。

当插入或删除节点的时候，红黑树的规则可能打破，这时需要做出调整，继续维持规则。

ps:新插入的节点都为红色。

向上面样例红黑树中插入一个值为21的新节点：

这种插入操作打破了红黑树的平衡，红黑树将进行一系列调整，使之重新符合规则。

红黑树调整规则

一、 变色

红色节点变为黑色节点，黑色节点变为红色节点。

下图中，左边红黑树连续出现22、21两个红色节点，故需要变色变换：

通过此次变换，25到其下所有叶子节点路径上的黑色节点数目不一致，所以需要再次变换：

此时，25、27又是连续两个红色节点，继续变换：

至此，红黑树符合规则。

二、 旋转

左旋转

逆时针旋转红黑树的两个节点，使父节点被右孩子取代，自己成为此时父节点的左孩子

右旋转

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为此时父节点的右孩子

下例中，需要用到旋转来保持红黑树规则：

1、变色

此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。
2、左旋转操作
变色已无法解决问题，我们把节点13看做X，把节点17看做Y，像刚才的示意图那样进行左旋转：


3、变色操作
由于根节点必须是黑色节点，所以需要变色，变色结果如下：

4、右旋转操作
这样就结束了吗？并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。
这时候我们需要把节点13看做X，节点8看做Y，像刚才的示意图那样进行右旋转：


5、变色操作

如此一来，我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂，经历了如下步骤：

变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色

参考文章：
红黑树原理和算法详细介绍: http://www.cnblogs.com/skywang12345/p/3245399.html