红黑树是一种应用非常广泛的数据结构，虽然实现起来挺麻烦，不过其效率很高。Java8之后HashMap的底层使用了哈希表+红黑树来进行实现。

红黑树

红黑树属于二叉平衡树的一种，常用于二叉查找树。

红黑树定义如下：

1. 每个节点非黑即红
2. root节点必须为黑色
3. 所有叶子节点为黑色(这里说的叶子节点指的是NULL)
4. 红色节点的两个子节点必须为黑(换句话说，红色节点不能连续存在)
5. 从root到叶子节点每条路径上的黑色节点数量一样多

特性：

1. 所有的叶子节点都为NULL
2. 最长路径/最短路径<2 (因为每条路径黑色节点一样多，而红色节点不能连续，所以单条路径上面的黑色节点必定多于红色节点)
3. 插入的新节点都为红色

操作：

增删改查

修改和查询过程和二叉查找树一致，主要是增删过程，因为红黑树就是为了解决二叉查找树不平衡问题而诞生的，所以在每次增删过后，都要对树的结构进行检查和调整。确保符合红黑树的定义，保证树的平衡性。

红黑树的调整手段有变色和旋转，变色分为红变黑或者黑边红，旋转分为左旋和右旋。

效率：
红黑树最差情况下也能达到O(logn),而普通二叉查找树最差情况下会退化为链表，时间复杂度为O(n)

应用：
java中的TreeMap,TreeSet,HashMap(java8之后也是红黑树)

完美二叉树可以理解为二进制，111111代表了6层的二叉树，或者说二进制本身就是一棵完美二叉树

具体操作：

查找:

二叉查找树基本操作

插入:

这里只讨论左边的情况,右边的也一样,只不过要对称一下.

插入的新节点总是红的.

如果树为空,则将其置为根节点涂黑即可.若父节点为黑色,则不用管,不影响平衡性.若父节点为红,则需要考虑以下情况:

1.若当前节点的父节点为红,父节点的兄弟节点为红—–>将父节点和父节点的兄弟节点都改为黑色,将其祖父节点改为红色,将祖父节点设为当前节点,开始新一轮的平衡调整.

2.若当前节点的父节点为红,父节点的兄弟节点为黑,且插入的是父节点的右子节点.—–>将父节点设为当前节点,以父节点为轴心,左旋

3.若当前节点的父节点为红,父节点的兄弟节点为黑,且插入的是父节点的左子节点.—–>将父节点置黑,将祖父节点置红,以祖父节点为轴心,右旋

至此,调整结束.

如果是从情况1开始发生的，必然会走完情况13或者123，如果从情况2开始发生，那再走个情况3即可完成调整，如果从3开始，那么前两种情况均不走。故变色和旋转之间的先后关系可以表示为：变色->左旋->右旋。

删除：

关于删除的操作,是和普通二叉搜索树是一致的,只不过红黑树要考虑删除之后的平衡问题.

如果被删除节点没有子节点,则不影响平衡性.

如果被删除节点只有单子节点,则用单子节点填充,然后检查平衡性,若被删除节点为红,则不用管,若为黑,则要进行平衡操作.这里的平衡操作可以当做双子节点情况下后继节点原位置的平衡处理.

如果被删除节点有双子节点,则要寻找后继节点.

后继节点会被用来填充被删节点的位置，而且后继节点会被改为和被删除节点一致的颜色。所以被删节点的位置的平衡性不用考虑。

如果后继节点没有子节点，则不用考虑后继节点原来位置的平衡性。

如果后继节点为红色，则不影响原来位置的平衡性。这里解释一下，因为后继节点必然不是双子节点，所以从后继节点往下的路径最多为1条,如果为红色，删掉并不影响平衡性。

只有后继节点为黑色的时候才需要考虑平衡性这一点.这个时候要看后继节点原来的子节点的情况:

define 后继节点的子节点 当前节点

0.如果当前节点为红色.—–>直接涂黑就ok

假设当前节点是左子节点:

1.如果当前节点为黑色,其兄弟节点为红色.—–>这个时候将父节点涂红,将兄弟节点涂黑,然后以其父节点为轴心左旋(这时会出现3,4,5的情况).

2.如果当前节点为黑色,其兄弟节点也为黑色,兄弟节点的子节点均为黑色.—–>这个时候将兄弟节点涂为红色.将当前节点指向其父节点,或者说将其父节点设为当前节点,将祖父节点设为父节点,以新的当前节点为开始,继续算法.

3.当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色，右子节点时黑色的.—–>将兄弟节点涂红,兄弟节点的左子节点涂黑,以兄弟节点为轴心,右旋.

4.当前节点是黑色的,且兄弟节点是黑色的,且兄弟的右子节点是红色,左子节点任意色.—–>将兄弟结点涂为和父节点一样的颜色,父节点涂黑,兄弟节点的右节点涂黑,以当前节点的父节点为轴心,左旋.(如果旋转后的兄弟节点变成了根节点,若为红色,就要改为黑色).至此,修复完成.

如果是从情况1开始发生的，可能情况2，3，4中的一种：如果是情况2，就不可能再出现3和4；如果是情况3，必然会导致情况4的出现；如果2和3都不是，那必然是4。当然咯，实际中可能不一定会从情况1发生，这要看具体情况了。

归根结底,我们做了这么多的操作就是为了保证红黑树的平衡性,例如左边少了一个黑色节点,而左边自己又补不上,就要右边通过变色旋转往左边补,右边补不上,那就右边也少一个,保持左右平衡,然后问题抛给上一级,让它们头疼去吧,哈哈.

学习这里的难点在于,自己老是想一些不可能存在的状况来测试,走了很多弯路,须知,删除之前,红黑树已经是红黑树了,肯定是相当平衡的.

相比插入,删除是真滴难.

参考链接:http://blog.csdn.net/eson_15/article/details/51144079