第13章 红黑树

二叉搜索树，在一些基本动态集合操作中，如SEARCH、PREDECESSOR、SUCCESSOR、MINIMUM、MAXIMUM、INSERT、DELETE等，这些的时间复杂度均为O(h)。
如果树的高度h较低时，这些操作执行的很快，但是，树的高度较高时，这些操作并不比在链表上执行的快。
红黑树是“”平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度为O(lg h)。

13.1、红黑树的性质

红黑树，一棵二叉搜索树，在每个节点上增加了一个表示节点颜色的存储位，可以是RED或BLACK。
通过对任何一条从根到叶子的简单路径上的节点颜色的约束，确保没有一条路径比其他路径长出2倍，因此，近似平衡。
红黑树每个节点包含5个属性：color、key、left、right、p。
红黑树是满足下列红黑性质的二叉搜索树：

1. 每个节点要么是红色的，要么是黑色的；
2. 根节点是黑色的；
3. 每个叶节点（都为nil）是黑色的；
4. 如果一个节点是红色的，则它的两个子节点都是黑色的【其红色节点的父节点是黑色节点，因此不会出现红红的连续节点，都是红黑相间的，或者连续黑色节点的】
5. 对每个节点，从该节点到其所有后代叶节点的简单路径（没有重复节点的意思）上，均包含相同数目的黑色节点。

为了便于代码中处理边界条件，红黑树使用哨兵nil来表示。
哨兵，是一个与树中普通节点有相同属性的对象。color为BLACK，其他属性可设为任意值。
所有nil孩子使用一个哨兵T.nil来代表所有的NIL孩子，也就是所有的叶节点、根节点的父节点。如下图：

1.png

通常，我们只关心红黑树的内部节点（因为内部节点有关键值）。后面部分的所有红黑树都会忽略叶节点。

黑高：从节点x出发，到达一个叶节点的任意一条简单路径上的黑色节点个数，称为该节点的黑高。（计算黑高时，不计算节点x本身，即使节点x也是黑色的。）
红黑树的黑高就是其根节点的黑高。

**引理 13.1 一棵有n个内部节点的红黑树的高度至多为2lg(n+1)。
和书中不同的证明方法：
1、将每个红色结点，向上合并到其父结点（黑色的结点）。
2、合并转换后，可以发现原来的树变成了一个2-3-4树，并且每个叶节点的高度都是一样的。

2-3-4树
1、每个内部节点都有2~4个子节点；
2、每个叶节点的高度一致，等于根节点的黑高。意味着，树很平衡。

原树的高度为h，合并后的2-3-4树高度，也就是黑高为h'。
一棵平衡树每个内部节点分支数为2，其叶节点个数等于内部节点个数n+1。（该结论来自于二叉树中，度为0的结点个数，等于度为2的结点个数+1。推导方式可以看收藏的链接。）
2-3-4树中， 2^h' <= 叶节点数 <= 4^h'。因为每个内部节点都至少有2个分支。
因此，2^h' <= n+1 <= 4^h'
h' <=lg(n+1)
又由于性质4，所有的红色节点，其父节点和子节点都必须是黑色的结点，而上面合并的2-3-4树是一个浓缩的黑树，原树的实际高度，就是在合并浓缩的黑树的任意路径上加上最多一倍高的红色的结点，因此，原红黑树树的高度h等于：
h <= 2* lg(n+1)

因此，由13.1引理可知，红黑树的动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR，这些查询操作的执行时间为O(lg n)。
因为任何包含n个结点的红黑树，都是提个高度为O(lg n)的二叉搜索树。

13.2、旋转

插入和删除操作，其运行时间为O(lg n)，但是这两个操作对树的修改，可能会违反红黑树的性质，为此，必须改变树中某些节点的颜色以及指针结构。
指针结构的修改，通过旋转来完成。

13.3、插入

调用RB-INSERT(T，z)在红黑树T内插入结点z，再调用RB-INSERT-FIXUP来对结点重新着色并旋转。

RB-INSERT(T,z)
y = T.nil;
x = T.root;
while x != T.nil
    y = x;
    if z.key < x.key
        x = x.left;
    else
        x = x.right;
z.p = y;
if y == T.nil
    T.root = z;
elseif z.key < y.key
    y.left = z;
else
    y.right = z;
z.left = T.nil;
z.right = T.nil;
z.color = RED;
RB-INSERT-FIXUP(T,z)


RB-INSERT-FIXUP(T,z)
while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right;
        if y.color == RED
            z.p.color == BLACK              //case1
            y.color = BLACK                 //case1
            z.p.p.color = RED               //case1
            z = z.p.p                       //case1
        else if z == z.p.right
            z = z.p;                      //case2
            LEFT_ROTATE(T,z)              //case2
        else
            z.p.color = BLACK              //case3
            z.p.p.color = RED              //case3
            RIGHT_ROTATE(T,z.p.p)          //case3
    else
        (same as then clause with "right" and "left" exchanged)
        和z.p == z.p.p.left的三种情况对称
T.root.color = BLACK

首先将z按照二叉搜索树的插入方法插入到树中，如图。

2.png

下面使用RB-INSERT-FIXUP对某些子树进行重新着色和旋转。
RB-INSERT-FIXUP中分为两大类情况，每一大类又分三种情况；
首先，z本身为红色节点。
第一种情况：z的叔节点为红色
如图13-4（a）

1. 将z的父节点设为黑色；
2. 将z的叔节点设为黑色；
3. 将z的祖父节点设为红色；
4. 将z赋值为z的祖父节点；
   说明：针对情况1，只是将相关节点的颜色设置了，对于树本身的结构没有变化；

第二种情况：z的叔节点为黑色，且z是一个右孩子
如图13-4（b）

1. 设置z为z的父节点；
2. 然后将树左旋到以z代替其父节点的位置，此时情况2就转换为情况3；

第三种情况：z的叔节点为黑色，且z是一个左孩子
如图13-4（c）

1. 将z的父节点设为黑色；
2. 将z的祖父节点设为红色；
3. 将z的祖父节点右旋；

13.4、删除

删除节点z的几种情况:

1. z的子节点少于2个时，z从树中直接删除，用z的孩子节点x来替换z。
2. z有两个子节点时；在z的右子树中，找到z的后继y。
   2.1. 后继y是z的右孩子节点；直接右孩子节点x（也是后继y）直接补位。
   2.2. 后继y不是z的孩子节点：用y的右孩子x替换y，并且将y替换z的位置，将z的左右孩子赋给y的左右孩子，用y替换z的位置，使用z原来的颜色。这里其实最后实际上删除的y，需要去调整后继y的右孩子x。
3. 在节点z被移除之前，要先记住y的颜色，去调整补位的节点x及其相关节点的颜色。

调整补位节点x的几种情况：

1. x的兄弟节点w是红色的
2. x的兄弟结点w是黑色的，并且w的两个子节点都是黑色的；
3. x的兄弟结点w是黑色的，并且w的左孩子是红色，右孩子是黑色；
4. x的兄弟结点w是黑色的，且w的右孩子是红色的。