红黑树

红黑树的定义

红黑树不是严格的平衡二叉树。（即不会严格遵守左右子树高度差的绝对值不超过1的条件，与之相对的，用AVL算法实现的则是严格的平衡二叉树，但红黑树性能更优。）

红黑树在原有的排序二叉树上增加了以下几个要求：

1)每个节点要么是红色，要么是黑色

2)根节点永远是黑色的

3)每个红色节点的子节点都是黑色 （反之不一定）

4)从任一节点到其子树中每个叶节点的路径都包含相同数量的黑色节点（计算时含叶节点）

注意：所有的叶节点都是空节点(null)，并且是黑色的，被称为黑哨兵（跟其它场合的叶节点不是一回事）

相关定义参考：二叉树的基本性质

红黑树示例：

定义中关于叶节点的说法，有效的保证了平衡性，下面看一个反例：

上述例子不是红黑树。

红黑树操作：查询

和普通二叉搜索树一样，略。

红黑树操作：插入节点

先看下三个基本操作：

变色

改变颜色，没什么好说的

左旋

直接看图：

右旋

直接看图：

java 中处理插入操作时有如下规律：

在红黑树中插入的节点都是红色的，因为插入一个红色节点比插入一个黑色节点违背红黑规则的可能性更小。原因是：插入黑色节点总会改变黑色高度，但是插入红色节点只有一半的机会会违背规则3。另外违背规则3比违背规则4要更容易修正。当插入一个新的节点时，可能会破坏这种平衡性，那么红黑树是如何修正的呢？

1. 如果是第一次插入，由于原树为空，所以只会违反红黑树的规则2，所以只要把根节点涂黑即可；

2.如果插入节点的父节点是黑色的，那不会违背红黑树的规则，什么也不需要做；

3.插入节点的父节点和其叔叔节点均为红色的；

4. 插入节点的父节点是红色，叔叔节点是黑色；

值得一提的是，后面两种情况，都可以认为当前节点的祖父节点必然存在，且为黑色（根据红黑树的性质可以推导，这样就简化了判断逻辑）

先看一个例子，在原有红黑树的基础上插入节点(4)，首先对应情况3：

注意：这里只是为了说明情况，假设祖父节点的父节点仍然是红色的，所以需要进行下一步。实际情况，也有可能是黑色的，那么操作也就到此为止了，不必进行下一步。也就是说，情况3操作结束后，要不要进行下一步，要看目前具体属于哪种情况。

对于情况4：插入节点的父节点是红色，叔叔节点是黑色。以例子中的情况来看，我们要做的操作有：第一步：以节点(7)作为新的节点，以父亲节点(2)为支点做左旋操作，左旋结束后，当前节点变为原父亲节点(2)。第二步：节点(2)作为新的节点，将父节点(7)涂黑，将祖父节点(11)涂红，以祖父节点(11)为支点做右旋操作。最终结果如上图。

注意：在一次完整的插入操作中，可能通过不止一次旋转才完成目标。但是插入操作最多也只会有两次旋转。

那么情况4到底是按照什么逻辑来进行变色或旋转的呢？其实有多种理解方法：

第一种理解方法

A、n是p左子节点，p是g的左子节点。

B、n是p右子节点，p是g的右子节点。

C、n是p左子节点，p是g的右子节点。

D、n是p右子节点，p是g的左子节点。

情况A：n是p左子节点，p是g的左子节点。针对该情况可以通过一次右旋转操作，并将p设为黑色，g设为红色。

情况B则需要使用左旋操作来解决平衡问题，方法和情况A类似。

情况C：n是p左子节点，p是g的右子节点。针对该情况通过一次左旋，一次右旋操作，并将n设为黑色，g设为红色完成重新平衡。

情况D则需要使用一次右旋，一次左旋操作来解决平衡问题，方法和情况C类似。

备注：情况3和情况4的旋转支点标错了，不要被误导。

第二种理解方法

考虑当前节点是父亲节点的左节点还是右节点。

A、当前节点是左节点。

B、当前节点是右节点。

口诀就是：左节点右旋，右节点左旋，同侧变色旋，不同侧普通旋，如此递归至当前节点（当前节点会可能随着旋转操作改变）的父亲节点是黑色为止。

其中普通旋之后一定会再来一次变色旋，变色旋之后一定不需要再旋转了。（其实也就是把上一种理解方式归纳一下）

普通旋：以当前节点的父亲节点为支点，进行旋转操作（包括左旋右旋），然后把父亲节点作为当前节点，继续判断（当然，TreeMap中这种状态并没有判断，直接下一步，因为这时候肯定不符合红黑规则）；

变色旋：以当前节点的祖父节点为支点，进行旋转操作（包括左旋右旋），并把父节点变黑，祖父节点变红，这个情况下当前节点不需要再改变了。

当前节点跟父亲节点是不是同一侧还有一个专业的说法：同侧为外侧插入，不同侧为内侧插入。

可以这样理解（非官方）：对于内测插入，先要通过普通旋变成外侧插入的情况。

TreeMap代码如下（jdk6）：

    PRivate void fixAfterInsertion(Entry<K,V> x) {        x.color = RED;        while (x != null && x != root && x.parent.color == RED) {            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {                Entry<K,V> y = rightOf(parentOf(parentOf(x)));                if (colorOf(y) == RED) {                    setColor(parentOf(x), BLACK);                    setColor(y, BLACK);                    setColor(parentOf(parentOf(x)), RED);                    x = parentOf(parentOf(x));                } else {                    if (x == rightOf(parentOf(x))) {                        x = parentOf(x);                        rotateLeft(x);                    }                    setColor(parentOf(x), BLACK);                    setColor(parentOf(parentOf(x)), RED);                    rotateRight(parentOf(parentOf(x)));                }            } else {                Entry<K,V> y = leftOf(parentOf(parentOf(x)));                if (colorOf(y) == RED) {                    setColor(parentOf(x), BLACK);                    setColor(y, BLACK);                    setColor(parentOf(parentOf(x)), RED);                    x = parentOf(parentOf(x));                } else {                    if (x == leftOf(parentOf(x))) {                        x = parentOf(x);                        rotateRight(x);                    }                    setColor(parentOf(x), BLACK);                    setColor(parentOf(parentOf(x)), RED);                    rotateLeft(parentOf(parentOf(x)));                }            }        }        root.color = BLACK;    }红黑树操作：删除节点
java 中处理删除操作时有如下规律：
111
参考地址：http://blog.csdn.net/eson_15/article/details/51144079
参考地址：http://blog.csdn.net/very_2/article/details/5722682
参考地址：http://www.cnblogs.com/yydcdut/p/4009201.html