从零开始的 STL 实现记录：Container-6.3

前言

红黑树性质：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是 NIL 节点）。
4. 每个红色节点必须有两个黑色的子节点。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

对于红黑树而言，最重要的算法就是如何插入与删除一个节点，而这两个操作又需要大量用到树的左旋与右旋。因此本节主要分析这些算法的实现。这部分建议结合 红黑树寄录 中的内容一起看，会有助于理解。

红黑树算法

常用的辅助函数

以下列出红黑树算法中经常要使用的一些简单函数。

/// @brief 查找最小节点
template <class NodePtr>
NodePtr rb_tree_min(NodePtr x) noexcept {
    while (x->left != nullptr) x = x->left;
    return x;
}

/// @brief 查找最大节点
template <class NodePtr>
NodePtr rb_tree_max(NodePtr x) noexcept {
    while (x->right != nullptr) x = x->right;
    return x;
}

/// @brief 判断该节点是否为左儿子
template <class NodePtr>
bool rb_tree_is_lchild(NodePtr x) noexcept {
    return x == x->parent->left;
}

/// @brief 判断该节点的颜色是否为红色
template <class NodePtr>
bool rb_tree_is_red(NodePtr x) noexcept {
    return x->color == rb_tree_red;
}

/// @brief 将节点染成黑色
template <class NodePtr>
void rb_tree_set_black(NodePtr x) noexcept {
    x->color = rb_tree_black;
}

/// @brief 将节点染成红色
template <class NodePtr>
void rb_tree_set_red(NodePtr x) noexcept {
    x->color = rb_tree_red;
}

/// @brief 获得 rb-tree 的下一个节点
template <class NodePtr>
NodePtr rb_tree_next(NodePtr x) noexcept {
    if (x->right != nullptr) return rb_tree_min(x->right);
    while (!rb_tree_is_lchild(x)) x = x->parent;
    return x->parent;
}

其中，rb_tree_next() 主要用于删除有两个子节点的节点的情况，这时需要找到该节点的前继或后继节点替代该节点被删除；不难看出，STL 使用的策略是后者，即找到该节点的后继。

树的旋转

// ============== rb-tree rotate ============== //
// 根节点为引用传参！！！根节点为引用传参！！！根节点为引用传参！！！
// 要修改根节点的值，必须传引用！！！

/*---------------------------------------*\
|       p                         p       |
|      / \                       / \      |
|     x   d    rotate left      y   d     |
|    / \       ===========>    / \        |
|   a   y                     x   c       |
|      / \                   / \          |
|     b   c                 a   b         |
\*---------------------------------------*/
// 左旋，参数一为左旋点，参数二为根节点
template <class NodePtr>
void rb_tree_rotate_left(NodePtr x, NodePtr& root) noexcept {
    auto y = x->right;
    x->right = y->left;
    if (y->left != nullptr) y->left->parent = x;
    y->parent = x->parent;

    // 如果 x 为根节点，让 y 顶替 x 成为根节点
    if (x == root) root = y;
    else if (rb_tree_is_lchild(x)) x->parent->left = y;
    else x->parent->right = y;

    // 调整 x 与 y 的关系
    y->left = x;
    x->parent = y;
}

/*----------------------------------------*\
|     p                         p          |
|    / \                       / \         |
|   d   x      rotate right   d   y        |
|      / \     ===========>      / \       |
|     y   a                     b   x      |
|    / \                           / \     |
|   b   c                         c   a    |
\*----------------------------------------*/
// 右旋，参数一为右旋点，参数二为根节点
template <class NodePtr>
void rb_tree_rotate_right(NodePtr x, NodePtr& root) noexcept {
    auto y = x->left;
    x->left = y->right;
    if (y->right != nullptr) y->right->parent = x;
    y->parent = x->parent;

    // 如果 x 为根节点，让 y 顶替 x 成为根节点
    if (x == root) root = y;
    else if (rb_tree_is_lchild(x)) x->parent->left = y;
    else x->parent->right = y;

    // 调整 x 与 y 的关系
    y->right = x;
    x->parent = y;
}

左旋与右旋的逻辑比较直观，但要注意 由于旋转操作可能会改变根节点，因此这里一定要传引用。

插入节点

插入节点分为五种情况：

1. 插入节点为根节点，直接将节点颜色置为黑色。
2. 插入节点的父节点为黑色，不需要做任何操作。
3. 插入节点的父节点为红色，需要进行调整。
   1. 插入节点的叔叔节点为红色，将父节点和叔叔节点置为黑色，祖父节点置为红色，将祖父节点作为新的插入节点，继续调整（因为此时祖父节点可能也不满足性质 4）。
   2. 插入节点的叔叔节点为黑色，且插入节点与父节点同侧（LL/RR），以祖父节点为支点进行反向旋转（R/L），将父节点置为黑色，祖父节点置为红色。
   3. 插入节点的叔叔节点为黑色，且插入节点与父节点异侧（LR/RL），以父节点为支点进行反向旋转（L/R），转化为 3.2。

// ================== rb-tree insert ================== //
template <class NodePtr>
void rb_tree_insert_rebalance(NodePtr x, NodePtr& root) noexcept {
    rb_tree_set_red(x);  // 新增节点为红色
    // 父节点为黑色不用处理，case2
    while (x != root && rb_tree_is_red(x->parent)) {
        // 如果父节点为左子节点
        if (rb_tree_is_lchild(x->parent)) {
            auto uncle = x->parent->parent->right;  // 叔叔节点
            // uncle 红色，case3.1
            if (uncle != nullptr && rb_tree_is_red(uncle)) {
                rb_tree_set_black(x->parent);  // 父节点变为黑色
                rb_tree_set_black(uncle);      // 叔叔节点变为黑色
                rb_tree_set_red(x);            // 祖父节点变为红色
                x = x->parent->parent;         // 祖父节点变为当前节点
            }
            // 无叔叔节点或叔叔节点为黑
            else {
                // LR, case3.3 转化为 case3.2
                if (!rb_tree_is_lchild(x)) {
                    x = x->parent;                 // 父节点变为当前节点
                    rb_tree_rotate_left(x, root);  // 左旋
                }
                // case 3.2
                rb_tree_set_black(x->parent);        // 父节点变为黑色
                rb_tree_set_red(x->parent->parent);  // 祖父节点变为红色
                rb_tree_rotate_right(x->parent->parent, root);  // 右旋
                break;
            }
        }
        // 对称处理
        else {
            auto uncle = x->parent->parent->left;    // 叔叔节点
            // uncle 红色，case3.1
            if (uncle != nullptr && rb_tree_is_red(uncle)) {
                rb_tree_set_black(x->parent);  // 父节点变为黑色
                rb_tree_set_black(uncle);      // 叔叔节点变为黑色
                x = x->parent->parent;         // 祖父节点变为当前节点
                rb_tree_set_red(x);            // 祖父节点变为红色
            }
            // 无叔叔节点或叔叔节点为黑
            else {
                // RL, case3.3 转化为 case3.2
                if (rb_tree_is_lchild(x)) {
                    x = x->parent;                  // 父节点变为当前节点
                    rb_tree_rotate_right(x, root);  // 右旋
                }
                // case 3.2
                rb_tree_set_black(x->parent);        // 父节点变为黑色
                rb_tree_set_red(x->parent->parent);  // 祖父节点变为红色
                rb_tree_rotate_left(x->parent->parent, root);  // 左旋
                break;
            }
        }
    }
    rb_tree_set_black(root);  // 根节点为黑色
}

删除节点

红黑树的节点删除从逻辑上来说可以分为两步：找到需要删除的节点（可能会转变为删除后继节点）；删除节点后调整树。但 STL 中并没有将这两个函数分开实现，而是直接用一个 __rb_tree_rebalance_for_erase() 一起完成了。

需要注意的点已经在注释中写得很详细了，并且这里的删除与调整的逻辑与 红黑树寄录 中相同，结合看的话应该不会有理解障碍。

// ================== rb-tree erase ================== //
// 删除节点后使 rb tree 重新平衡，参数一为要删除的节点，参数二为根节点，参数三为最小节点，参数四为最大节点
template <class NodePtr>
NodePtr rb_tree_erase_rebalance(NodePtr z, NodePtr& root, NodePtr& leftmost, NodePtr& rightmost) {
    
    // =============================== 1. 找到要删除的节点 =============================== //
    // 1. 删除只有一个子树的节点：删除原节点，用单独的子节点代替被删除节点。
    // 2. 删除没有子树的节点：直接删除原节点，相当于用一个空节点 (NIL) 代替了被删除节点。
    // 3. 删除有两个子树的节点：寻找后继或前继节点（这里选择后继），将待删除节点的值变为后继节点的值，
    // 再删除后继节点，删除后继节点一定会变成 1 或 2 的情况。

    // y 是可能的替换节点，指向最终要删除的节点
    auto y = (z->left == nullptr || z->right == nullptr) ? z : rb_tree_next(z);
    // x 是 y 的一个独子节点或 NIL 节点
    auto x = y->left != nullptr ? y->left : y->right;
    // xp 是 x 的父节点
    NodePtr xp = nullptr;

    // case3
    // y != z 说明 z 有两个非空子节点，此时 y 是 z 的后继节点，x 指向 y 的非空子节点。
    // 用 y 顶替 z 的位置，用 x 顶替 y 的位置，最后用 y 指向 z
    if (y != z) {
        z->left->parent = y;
        y->left = z->left;

        // 如果 y 不是 z 的右子节点，那么 z 的右子节点一定有左孩子
        // x 替换 y 的位置
        if (y != z->right) {
            xp = y->parent;
            if (x != nullptr) x->parent = y->parent;
            y->parent->left = x;
            y->right = z->right;
            z->right->parent = y;
        }
        else xp = y;

        // 连接 y 与 z 的父节点
        if (root == z) root = y;
        else if (z->parent->left == z) z->parent->left = y;
        else z->parent->right = y;

        y->parent = z->parent;
        tinystl::swap(y->color, z->color);
        y = z;
    }

    // case1、case2
    // y == z 说明 z 至多只有一个孩子
    else {
        xp = y->parent;
        if (x) x->parent = y->parent;

        // 连接 x 与 z 的父节点
        if (root == z) root = x;
        else if (z->parent->left == z) z->parent->left = x;
        else z->parent->right = x;

        // 此时 z 有可能是最左节点或最右节点，更新数据
        if (leftmost == z) leftmost = x == nullptr ? xp : rb_tree_min(x);
        if (rightmost == z) rightmost = x == nullptr ? xp : rb_tree_max(x);
    }

    // =============================== 2. 调整红黑树 =============================== //
    // 此时，y 指向要删除的节点，x 为替代节点，从 x 节点开始调整。
    // 如果删除的节点为红色，树的性质没有被破坏，否则按照以下情况调整（x 为左子节点为例）：
    // 1. x 为新的根节点，直接将 x 染成黑色，调整结束。
    // 2. 兄弟节点为红色，令父节点为红，兄弟节点为黑，进行左（右）旋，继续处理。
    // 3. 父节点为黑色，兄弟节点为黑色，且两个子节点都为黑色或 NIL，令兄弟节点为红，父节点成为当前节点，继续处理。
    // 4. 父节点为红色，兄弟节点为黑色，且两个子节点都为黑色或 NIL，令兄弟节点为红，算法结束。
    // 5. 兄弟节点为黑色，右子节点为红色，令兄弟节点为父节点的颜色，父节点为黑色，兄弟节点的右子节点
    //    为黑色，以父节点为支点左（右）旋，树的性质调整完成，算法结束。
    // 6. 兄弟节点为黑色，左子节点为红色或 NIL，右子节点为黑色或 NIL，
    //    令兄弟节点为红，兄弟节点的左子节点为黑，以兄弟节点为支点右（左）旋，继续处理。

    // 仅在删除黑色节点时需要调整
    if (!rb_tree_is_red(y)) {
        // 注意这里的循环条件: !rb_tree_is_red(x)，当遇到 case3 的情况时会转而处理 P 节点
        // 此时 p == x，会再进行一次条件判断，当 p 为红色时，便为 case4 的情况
        // 直接跳出循环，最后将 x 设为黑色，结束调整。
        while (x != root && (x == nullptr || !rb_tree_is_red(x))) {
            if (x == xp->left) {
                auto brother = xp->right;
                // case2：兄弟节点为红色节点，旋转父节点
                if (rb_tree_is_red(brother)) {
                    rb_tree_set_red(xp);               // 父节点变为红色
                    rb_tree_set_black(brother);        // 兄弟节点变为黑色
                    rb_tree_rotate_left(xp, root);     // 左旋
                    brother = xp->right;               // 更新兄弟节点
                }
                // case3: 兄弟节点及两个子节点均为黑色
                if ((brother->left == nullptr || !rb_tree_is_red(brother->left)) &&
                    (brother->right == nullptr || !rb_tree_is_red(brother->right))) {
                    rb_tree_set_red(brother);          // 兄弟节点变为红色
                    x = xp;                            // 父节点成为当前节点
                    xp = xp->parent;                   // 父节点的父节点成为父节点
                    // 此时如果 p 为红色会直接跳出循环
                }
                else {
                    // case5: 兄弟节点同侧的节点为黑色
                    if (brother->right == nullptr || !rb_tree_is_red(brother->right)) {
                        if (brother->left != nullptr) 
                            rb_tree_set_black(brother->left);  // 兄弟节点的左子节点变为黑色
                        rb_tree_set_red(brother);              // 兄弟节点变为红色
                        rb_tree_rotate_right(brother, root);   // 右旋
                        brother = xp->right;                   // 更新兄弟节点 
                    }
                    // 处理之后变为 case6
                    // case6: 兄弟节点的同侧节点为红色
                    brother->color = xp->color;                // 兄弟节点变为父节点的颜色
                    rb_tree_set_black(xp);                     // 父节点变为黑色
                    if (brother->right != nullptr) 
                        rb_tree_set_black(brother->right);     // 兄弟节点的右子节点变为黑色
                    rb_tree_rotate_left(xp, root);             // 左旋
                    break;
                }
            }
            // x 为右子节点，对称处理
            else {
                auto brother = xp->left;
                // case 1
                if (rb_tree_is_red(brother)) {
                    rb_tree_set_black(brother);
                    rb_tree_set_red(xp);
                    rb_tree_rotate_right(xp, root);
                    brother = xp->left;
                }
                // case 2
                if ((brother->left == nullptr || !rb_tree_is_red(brother->left)) &&
                    (brother->right == nullptr || !rb_tree_is_red(brother->right))) {
                    rb_tree_set_red(brother);
                    x = xp;
                    xp = xp->parent;
                }
                else {
                    // case 3
                    if (brother->left == nullptr || !rb_tree_is_red(brother->left)) {
                        if (brother->right != nullptr) 
                            rb_tree_set_black(brother->right);
                        rb_tree_set_red(brother);
                        rb_tree_rotate_left(brother, root);
                        brother = xp->left;
                    }
                    // 转为 case 4
                    brother->color = xp->color;
                    rb_tree_set_black(xp);
                    if (brother->left != nullptr) 
                        rb_tree_set_black(brother->left);
                    rb_tree_rotate_right(xp, root);
                    break;
                }
            }
        }
        // 将 x 的颜色改为黑色，有可能是 root 节点也有可能是 case4 跳出了循环
        if (x != nullptr) rb_tree_set_black(x);
    }
    return y;  // 这里返回的值实际上没有用到
    // 注意：执行完 rb_tree_erase_rebalance 保证了传入的 z，及要被删除的节点，此时一定不在树的结构中了
    // 这意味着对其进行析构是安全的，不会破坏树的性质。
}

此外需要注意的是上一小节中提到的 stl_tree 中的注释：

// (2) when a node being deleted has two children its successor node
// is relinked into its place, rather than copied, so that the only
// iterators invalidated are those referring to the deleted node.

当要删除的节点有两个子节点时，其后继节点将被重新链接到其位置，而不是复制，因此只会使与已删除节点相关的迭代器无效。

总结

红黑树中最难的两个操作以及配套的算法已经被我们分析完毕了，接下来就是一些红黑树自身的构造与内存管理，以及对外接口的一些函数了，会比这部分简单得多。