Red-Black Tree

1.定义：

         红黑树一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

2.特性：

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

3.应用

          主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。

                   例如，Java集合中的TreeSet和TreeMap，C++ 中的set、map，以及Linux虚拟内存的管理，都是红黑树实现的。

4.基本操作

       4.1 左旋和右旋

左旋示意图

右旋示意图

4.2 添加

第一步: 将红黑树当作一颗二叉查找树，将节点插入。

       红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。

第二步：将插入的节点着色为"红色"。

               着色参照其特性即可。

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

伪代码

4.3 删除

第一步：将红黑树当作一颗二叉查找树，将节点删除。

       这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：

       ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。

       ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。

       ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。

       因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。