红黑树

红黑树

阅读 “《算法导论》第3版第13章红黑树” 的笔记。
红黑树理解的提示：

红黑树的5条性质。
插入新的红色节点 z 后，不断上移红色标记 ，保证 z 的子树红黑树性质成立；除非 z 成为了根节点。
移除黑色节点 y 后，需要不断的上移黑色标记，或者从右边（左边）的子树借一个节点过来放置黑色标记，来满足红黑树的性质。

13.1 红黑树的性质

红黑树是一种二叉查找树，但是每个节点上增加一个存储位表示节点的颜色，可以说 RED 或 BLACK 。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
书中的每个节点包含五个域：color, key, left, right, p 。如果某节点没有一个字节点或父节点，则该节点相应的指针(p)域包含值 NIL 。我们将把这些 NIL 视为指向二叉树查找树的外节点（叶子）的指针，而把带关键字的节点视为树的内节点。

一颗二叉查找树如果满足下面的红黑性质，则为一颗红黑树(5点)：

1) 每个节点或是红色的，或是黑色的。(节点非红即黑)
2) 根节点是黑色的。 (根是黑的)
3) 每个叶节点(NIL)是黑色的。(叶子NIL是黑色的，叶子不存key)
4) 如果一个节点是红色的，则它的两个儿子都是黑色的。(红父黑子)
5) 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。(父节点到子孙节点的黑节点数量一样)

为了便于处理红黑树代码中的边界条件，我们采用一个哨兵来代表 NIL。对于一个红黑树 T 来说，哨兵 T.nil 是一个与树内普通节点有相同属性的对象。它的 color 属性为 BLACK ，其它属性 p, left, right, key 可以设置为任意值。所有指向 NIL 的指针都被替换成指向哨兵 T.nil 的指针。红黑树的根的父节点和叶子节点都是 NIL 哨兵节点。
从某个节点 x 出发（不包括该节点）到达一个叶子节点的任意一条简单路径上的黑色节点个数称为该节点 x 的黑高度(black-height)，记为 bh(x) 表示。由性质 5 可知，红黑树的黑高度定义为其根节点的黑高度。

证明红黑树是一种好的查找树

引理 13.1 一棵有 n 个内部节点的红黑树的高度至多为 2lg(n+1) 。
证明流程简单概括：

由性质5(父节点到子孙节点的黑节点数量一样)可以归纳证明以某一节点 x 为根的子树中至少包含 2^bh(x) - 1 的内节点。

设 h 为树的高度。根据性质 4)，从根到叶节点（不包括根）的任意一条简单路径上至少有一半的节点必是黑色的。 从而，根的黑高度至少是 h/2；所以 n >= 2^(h/2) - 1 ，把 1 移到不等号左边，再对两边取对数，得 lg(n+1) >= h/2 ，或 h <= 2lg(n+1) 。

由这个引理可知，动态几何操作 SEARCH、MINIMUM、MAXIMUM、SUCCESSOR 和 PREDECESSOR 可用红黑树在 O(lgn) 时间复杂度内实现，因为这些操作在一个高度为 h 的二叉查找树上运行时间为 O(h) ，而包含 n 个节点的红黑树又是高度为 O(lgn) 的查找树。

13.2 旋转

当在包含 n 个关键字的红黑树上运行时，查找操作 TREE-INSERT 和 TREE-DELETE 的时间为 O(lgn) 。这两个操作会修改树结构，结果可能无法保持树的性质，为了保持这些性质，就要改变书中某些节点的颜色和指针结构。
指针结构修改是通过旋转来完成的，分别为：左旋、右旋。

左旋：

// 左旋，类似 Python 的代码
LEFT-ROTATE(T, x) :
    y = x.right
    x.right = y.left
    if y.left != T.nil :
        y.left.p  = x
    y.p = x.p
    if x.p == T.nil :
        T.root = y
    elif x.p.left ==  x : // 如果 x 是 x.p 的左节点
        x.p.left = y
    else :              // 否则，x 是 x.p 的右节点
        x.p.right = y
    y.left = x
    x.p = y

右旋：

// 右旋，类似 Python 的代码
RIGHT-ROTATE(T, y) :
    x = y.left
    y.left = x.right
    if x.right != T.nil :
        x.right.p = y
    x.p = y.p
    if y.p == T.nil :
        T.root = x
    elif y.p.left== y :
        y.p.left = x
    else :
        y.p.right = x
    x.right = y
    y.p = x

13.3 插入

向一棵含 n 个节点的红黑树中插入一个新节点的操作可在 O(lgn) 时间内完成。
像插入一棵普通二叉查找树一样，将节点 z 插入树 T 内，然后将 z 着为红色。调用 RB-INSERT(T, z) 插入红黑树 T 内，假设 z 的 key 已经赋值。
插入新节点并调整红黑树的黑高度的精髓在：保证红黑树的性质是成立的。（同理删除节点也是这样）。

RB-INSERT(T, z) : // 插入，类型 Python 代码
    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
    elif 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) // 调整树结构，保持红黑性质

将 z 着色为红色可能会违反某一条红黑性质，所以调用 RB-INSERT-FIXUP(T, z) 调整树结构保持红黑性质。

插入调整，要保证红黑树的性质不变，然后针对性对6种情况做调整，下面只列出了3种，剩下3种是对称的。
while 条件：新的红色节点 z 的父节点 z.p 是红色，违反性质4，需要调整；如果 z.p 是黑色的，满足红黑树性质的，退出调整。
调整要点：当红色节点 z 的父节点是红色时，要不断的将红色标记往上移动，或者把红色标记移到右边(或左边)，来保证以 z.p 为根的子树的红黑树性质成立。根据红黑树的性质，可以简化归纳出6种情况，下面的 Case 1,2,3 是 z.p 是 z.p.p 的左孩子，z.p 是 z.p.p 的右孩子时，情况相反。 Case 1 的目的是上移红色标记， Case 2&3 的目的是移动红色到 z.p.p 右边。
Case 1: z.p.p 的孩子节点都是红色的。z.p.p 是黑色节点，z.p(也是z.p.p.left) 和 z.p.p.right 是红色节点，把 z 的红色标记上移到 z.p.p 上， z.p.p 变成红色节点, 此时以 z.p.p 为根的子树黑色节点数减少 1，所以要把 z.p.p 的黑色下移到 z.p.p 的子节点，变成黑色。然后 z = z.p.p，进入下一个循环。
Case 2 & Case 3: 因为 z.p.p 的孩子节点不全是红色的，不能直接上移 z 的红色到 z.p.p ; 这时可以把 z.p.p 左子树中的一个红色标记移动到 z.p.p 右边。为了保证有序性，通过旋转来调整树结构，然后着色。Case 3 的情况，可以直接通过 RIGHT-ROTATE(T, z.p.p) 和简单地着色(红色移动到 z.p.p 右边)，保证红黑树性质不变。 Case 2 不能右旋和简单地着色保证红黑树性质(会导致)，但是可以通过 LEFT-ROTATE(T, z.p) 转换成 Case 3。Case 2 不能直接右旋的原因是：右旋后，红色的 z 节点会变成 z.p.p 的左节点，但是着色后 z.p.p 是红色的，不合符性质4。

RB-INSERT-FIXUP(T, z) :
    while z.p.color == RED : // z.p 也是红色的，违反性质4
        if z.p == z.p.p.left : // z 父节点的父节点的左节点是 z 的父节点
            y = z.p.p.right
            if y.color == RED : 
                z.p.color = BLACK      // Case 1: 红色节点上移到 z.p.p 
                y.color = BLACK        // Case 1
                z.p.p.color = RED      // Case 1
                z = z.p.p;             // Case 1    
            else :
                if z == z.p.right : 
                    z = z.p            // Case 2: 转成 Case 3； z 的叔节点 y 是黑色的，且 z 是一个右孩子
                    LEFT-ROTATE(T, z)  // Case 2
                z.p.color = BLACK      // Case 3: 转移左边的红色节点到 z.p.p 的右边；z 的叔节点 y(z.p.p.right) 是黑色的，且 z 是一个左孩子
                z.p.p.color = RED      // Case 3
                RIGHT-ROTATE(T, z.p.p) // Case 3
        else : // z.p == z.p.p.right
            // (same as then clause with "right" and "left" exchanged)
            y = z.p.p.left
            if y.color == RED :
                z.p.color = BLACK      // Case 1' 
                y.color = BLACK        // Case 1'
                z.p.p.color = RED      // Case 1'
                z = z.p.p              // Case 1'
            else :
                if z == z.p.left :
                    z = z.p            // Case 2'
                    RIGHT-ROTATE(T, z) // Case 2'
                z.p.color = BLACK      // Case 3'  
                z.p.p.color = RED      // Case 3'
                LEFT-ROTATE(T, z.p.p)  // Case 3'
    // END - while z.p.color == RED
    T.root.color = BLACK // 最后修正根的颜色

分析：当 Case 1 发生时，z 上升 2 层，while 循环可能被执行的总次数为 O(lgn)。当程序执行到 Case 2&3 ，调整结束后会就会满足红黑树性质，while 循环就结束了。所以插入的调整时间复杂度为 O(lgn) 。

13.4 删除

与 n 个节点的红黑树上其他基本操作一样，删除一个节点要花费 O(lgn) 时间。

将 u 替换为 v

RB-TRANSPLANT(T, u, v) : // 将 u 替换为 v
    if u.p == T.nil :
        T.root = v
    elif u == u.p.left :
        u.p.left = v
    else :
        u.p.right = v
    v.p = u.p

删除节点 z :

RB-DELETE(T, z) :
    y = z
    y_original_color = y.color
    if z.left == T.nil :
        x = z.right
        RB-TRANSPLANT(T, z, z.right)
    elif z.right == T.nil :
        x = z.left
        RB-TRANSPLANT(T, z, z.left)
    else :
        y = TREE-MINIMUM(z.right) // z有两个节点时，y 为 z 的 后继
        y_original_color = y.color
        x = y.right
        if y.p == z :
            x.p = y // 用于记录 x 的踪迹，因为 x 可能是 T.nil 节点
        else :
            RB-TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        RB-TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color // 继承被删除节点 z 的颜色
    if y_original_color == BLACK : // y 原来在的位置是黑色的，x 霸占后，可能会引起红黑树性质的破坏
        RB-DELETE-FIXUP(T, x) // 调整红黑树结构

调整删除节点后的红黑树结构:
while 条件：因为移除的 y 节点是黑色的，如果 x 节点不是根，并且也是黑色的，那么经过 x 节点的简单路径就少了一个黑色节点，违反红黑树性质5，此时是需要调整的。（注意移除任意节点，是不会违反性质4的）
调整要点：我们假设 x 节点上多加了一重黑色，这样就不违反性质5了，但是一个节点上不能有两重颜色的，所以要把这个多余的黑色往上移动，或者增加该路径上节点个数，然后放置多余的黑色标记（从另一边子树上借节点过来用）。为了便于理解，黑色取值1，红色取值0， count(x.color) == 2 时，有两重黑色，需要调整， count(x.color) == 1 时，有一红一黑，或者就一黑，为满足红黑树性质的情况。
根据红黑树的性质，可以简化为有8种情况，再根据 x 为 x.p 的左孩子还是右孩子，分为左边4种情况和右边4种情况。这里的 Case 1,2,3,4 都是已经分析好的，按代码顺序标出了1,2,3,4，理解时不要受限于代码顺序。
Case 1&2&3&4 都是把多余的黑色标记往上移动，区别是移动的方式。 Case 1 是从右边借一个红色节点放到左边，转成 Case 2 的操作(放置多余的黑色标记)；Case 2 是上移黑色标记；Case 3&4 是上移红色标记，从右边借一个红色节点放到左边，标记为黑色，用于放置 x 多一重的黑色标记；把右边的红色标记往上移动到子树的根，因为上移的是红色标记，不会违反红黑树的性质，调整完成。
Case 1： x.p.right 是红色的，通过着色和 LEFT-ROTATE(T, x.p) ，再 Case 2 的调整后，x.p 是红色的，再经过 Case 2 的操作(放置多余的黑色标记)，就满足红黑树的性质了，下次循环就会退出调整。
Case 2：此时 w 是黑色的，w 的孩子也是黑色的，可以在不违反性质的情况下将 w 标记为红色，同时 x.p(也是 w.p) 就多加一重黑色，这样 x 节点上多余的黑色就移动到 x.p 了，下一个要调整的就是 x.p 。
Case 3：可以转成 Case 4 ，因为 w.left 是红色的，为了 LEFT-ROTATE(T, x.p) 让左边多一个节点，右边红色标记上移，就先要重新着色和 RIGHT-ROTATE(T, w) ，变成 Case 4 。
Case 4：这种情况 x.p 的右边有一个红色标记可以往上移动，可以 LEFT-ROTATE(T, x.p) ，将 x.p 往左转，让经过 x 的节点多一个节点，然后放置黑色标记， x 上多余的黑色就释放了，，然后把原来 x.p 的右边的红色标记转移的根，也就是原 x.p 的位置，因为转移的是红色标记，如果原 x.p 是红色的，那么转移后还是红色的（两重红色取红色），如果元 x.p 是黑色的，转移后取黑色（一红一黑取黑色），即 count(x.color) == 1 ，这样着色都不会违反红黑树的性质，可以结束调整了。

RB-DELETE-FIXUP(T, x) :
    while x != T.root and x.color == BLACK :
        if x == x.p.left :
            w = x.p.right
            if w.color == RED :                     // x 的兄弟 w 是红色的    
                w.color = BLACK                     // Case 1 --------
                x.p.color = RED                     // Case 1
                LEFT-ROTATE(T, x.p)                 // Case 1
                w = x.p.right                       // Case 1
            if w.left.color == BLACK and w.right.color == BLACK : // w 是黑色的，w 的两个孩子也是黑色的
                w.color = RED                       // Case 2 --------
                x = x.p                             // Case 2
            else :
                if w.right.color == BLACK :         // w 的孩子有红色的， 其中 w.right 是黑色的， w.left 是红色的
                    w.left.color = BLACK            // Case 3 --------
                    w.color = RED                   // Case 3
                    RIGHT-ROTATE(T, w)              // Case 3
                    w = x.p.right                   // Case 3
                w.color = x.p.color                 // Case 4 --------
                x.p.color = BLACK                   // Case 4
                w.right.color = BLACK               // Case 4
                LEFT-ROTATE(T, x.p)                 // Case 4
                x = T.root                          // Case 4 满足所有性质，可以退出了
        // END - if x == x.p.left :
        else : // x == x.p.right 
            // (same as then clause with "right" and "left" exchanged)
            w = x.p.left
            if w.color == RED:                      // 
                w.color = BLACK                     // Case 1' --------
                x.p.color = RED                     // Case 1'
                RIGHT-ROTATE(T, x.p)                // Case 1'
                w = x.p.left                        // Case 1'
            if w.left.color == BLACK and w.right.color == BLACK :
                w.color = RED                       // Case 2' --------
                x = x.p                             // Case 2'
            else :
                if w.left.color == BLACK :
                    w.right.color = BLACK           // Case 3' --------
                    w.color = RED                   // Case 3'
                    LEFT-ROTATE(T, w)               // Case 3'
                    w = x.p.left                    // Case 3'
                w.color = x.p.color                 // Case 4' --------
                x.p.color = BLACK                   // Case 4'
                w.left.color = BLACK                // Case 4'
                RIGHT-ROTATE(T, x.p)                // Case 4'
                x = T.root                          // Case 4' 满足所有性质，可以退出了
        // END else - x == x.p.left :
    x.color = BLACK

分析： Case 1&3&4 执行执行常数次操作后，整个循环就结束了。 Case 2 每次调整，x 节点就上层一层，最多上升 O(lgn)次。所以删除的调整操作时间复杂度为 O(lgn)。

学习笔记

红黑树《算法导论》第3版第13章

红黑树

13.1 红黑树的性质

证明红黑树是一种好的查找树

13.2 旋转

13.3 插入

13.4 删除

红黑树 《算法导论》第3版 第13章

红黑树

13.1 红黑树的性质

证明红黑树是一种好的查找树

13.2 旋转

13.3 插入

13.4 删除

红黑树《算法导论》第3版第13章