C++ 红黑树的实现：原理与底层解析

结论：红黑树的平衡性如何保障操作效率

红黑树通过严格的颜色规则和旋转操作，确保了树的路径长度差异有限。通过保证黑色节点数目相等和没有连续的红色节点，红黑树确保了每一条从根到叶子的路径上的黑色节点数量相同，同时限制了红色节点的数量。

具体来说，红黑树的平衡性源于以下几个因素：

1. 红色节点不能连续：这减少了极端情况下过多红色节点导致的树的不平衡。
2. 路径上的黑色节点数相同：这意味着所有路径的黑色节点数量一致，保证了从根到叶子的路径差距不会太大。
3. 旋转操作和变色：在插入或删除节点时，红黑树通过旋转和变色操作，动态维护这几个规则。

由于红黑树的这些规则，红黑树的最短路径和最长路径之间的长度差异不会超过 2 倍。也正是因为这一点，红黑树能够保证插入、删除和查找操作的时间复杂度为 O(log N)，即便在最坏的情况下，红黑树的效率仍然能够得到保证。

红黑树的实现

红黑树的节点结构

红黑树的每个节点包含一个键值对（key-value pair），并且除了普通二叉树的左子节点、右子节点外，还需要一个父节点指针来维护树的结构。此外，每个节点还需要一个颜色标记（红或黑），以便在插入和删除操作时维护平衡。

红黑树的结构与普通二叉搜索树类似，但它为每个节点额外引入了颜色属性。每个节点需要存储：

• 键值对（_kv）。
• 左右子节点（_left 和 _right）。
• 父节点（_parent），用于追踪节点的父亲，以便于修复平衡。
• 颜色（_col），表示节点是红色还是黑色。

template <class K, class V>
struct RBTreeNode {
    pair<K, V> _kv;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};

在红黑树的实现中，根节点初始化为黑色，其余新增节点在插入时先标记为红色。

红黑树的插入操作

插入基本步骤

红黑树的插入操作类似于二叉搜索树（BST）的插入，但在插入后需要通过一系列调整来维护红黑树的平衡性。插入的核心思想是：插入一个新节点后，如果不违反红黑树的规则，则插入结束；如果违反了某些规则（特别是红 - 红冲突），则通过颜色变换和旋转来修复。

按二叉搜索树规则进行插入，红黑树首先是一个二叉搜索树（BST），因此，插入一个新值的第一步就是根据 BST 的规则查找插入位置：如果插入的值小于当前节点的值，则向左子树移动。如果插入的值大于当前节点的值，则向右子树移动。 这一步的目的是在红黑树中找到合适的插入位置。此时仅仅是按照二叉搜索树的规则，不涉及颜色和平衡性问题。

新增节点颜色的选择 当我们找到插入位置后，分为两种情况：

1. 空树插入：如果红黑树是空树，则插入的节点是根节点，根据红黑树的第二条规则，根节点必须是黑色，因此将根节点设为黑色。插入结束，不需要进一步调整。
2. 非空树插入：如果树非空，则新插入的节点必须是红色。这是因为如果插入一个黑色节点，会违反红黑树的规则 4（从根到叶子的路径中黑色节点数必须相同）。红色节点的插入不会改变任何路径上的黑色节点数量，因此能减少违规的可能性。根据第二点情况说明，在非空子树插入黑节点会导致第四条规则很难维护，所以统一新加节点为红色节点，在插入到 root 位置的时候变为黑色即可。

插入后调整

情况 1：p为红，u为红，只着色

• c 是当前新插入的节点（红色），
• p 是 c 的父节点（红色），
• g 是 p 的父节点（黑色），即 p 的祖父节点（规则限制）
• u 是 p 的兄弟节点（即 g 的另一侧子节点，p 的叔叔节点）。

如果 p 和 u 都是红色，而 g 是黑色，这种情况下，我们需要通过重新着色来调整红黑树的平衡，而不是旋转。

红黑树的规则 3规定：不能有两个连续的红色节点，但新插入的节点 c 和它的父节点 p 都是红色，违反了这条规则。而 p 的叔叔节点 u 也是红色时，子树中的红色节点过多。此时，我们通过变色解决问题：

• 将 p 和 u 变成黑色：这会增加这条路径上黑色节点的数量，确保黑高的平衡。
• 将 g 变为红色：由于 p 和 u 都变为黑色，g 变红可以保持树的总平衡，即从 g 的根节点到叶子节点的黑色节点数量保持不变。
• 循环处理 g：由于 g 现在是红色，它可能会导致祖父节点进一步违反红黑树规则，因此我们需要将 g 当作新的 c，向上继续检查和修复，如果新的 p 为黑节点，即完成。

变色过程代码讲解

结合代码，具体分析：

// 如果父节点是红色，则修复红黑树属性
while (parent && parent->_col == RED) {
    Node* grandfather = parent->_parent; // 找到祖父节点
    if (parent == grandfather->_left) { // parent 在左 uncle 在右
        Node* uncle = grandfather->_right; // 找到叔叔节点 u
        // 情况 1: 叔叔节点是红色，需要重新着色
        if (uncle && uncle->_col == RED) { // u 为红色，进行变色
            parent->_col = uncle->_col = BLACK; // p 和 u 变为黑色
            grandfather->_col = RED; // g 变为红色
            cur = grandfather; // 继续向上修复，将 g 当作新的 cur
            parent = cur->_parent; // 更新父节点
        } else {
            // 情况 2: 叔叔节点是黑色或不存在，需要旋转
            // 此部分是旋转处理，当前情况为变色，不涉及此部分
        }
    } else { // parent 在右 uncle 在左
        Node* uncle = grandfather->_left; // 找到叔叔节点 u
        // 情况 1: 叔叔节点是红色，需要重新着色
        if (uncle && uncle->_col == RED) { // u 为红色，进行变色
            parent->_col = uncle->_col = BLACK; // p 和 u 变为黑色
            grandfather->_col = RED; // g 变为红色
            cur = grandfather; // 继续向上修复，将 g 当作新的 cur
            parent = cur->_parent; // 更新父节点
        } else {
            // 情况 2: 叔叔节点是黑色或不存在，需要旋转
            // 此部分是旋转处理，当前情况为变色，不涉及此部分
        }
    }
}
// 确保根节点始终为黑色
_root->_col = BLACK;

步骤 1：判断父节点 p 是否为红色 这段代码的前提是父节点 p 是红色。因为 c（当前插入的节点）也是红色，连续的红色节点 违反了红黑树的规则，因此需要进行调整。

步骤 2：找到祖父节点 g 和叔叔节点 u 我们首先通过 p 找到它的父节点 g，以及 g 的另一个子节点（p 的兄弟节点）u，即叔叔节点。根据 p 在 g 的左侧还是右侧，分别处理左叔叔和右叔叔的情况。

步骤 3：判断叔叔节点 u 是否为红色 如果 u 是红色，意味着子树中有过多的红色节点，此时我们需要进行变色：

1. p 和 u 变为黑色：通过变色，我们让这两个子树的黑色节点数量增加，这样所有从 g 到叶子的路径上的黑色节点数量保持一致。
2. g 变为红色：我们将 g 变为红色，保持整体黑色节点数平衡。

步骤 4：递归处理祖父节点 g 此时，g 被变为红色，可能会导致它与其父节点形成连续的红色节点。因此，我们将 g 作为新的 c，继续向上修复，重复这一过程。

步骤 5：确保根节点为黑色 无论经过了多少次变色和旋转调整，红黑树的根节点必须始终为黑色。因此在代码的最后，我们将根节点重新着色为黑色，确保红黑树的规则始终得以遵守。

抽象图

情况 2：p为红，u为空或不存在，单旋 + 变色

在红黑树的插入过程中，情况 2 涉及的是当新插入的节点 c 和它的父节点 p 都是红色，而 p 的兄弟节点 u（叔叔节点）不存在或是黑色的情况。此时，简单的变色操作不足以解决问题，必须进行旋转加变色来恢复平衡。

• c 是新插入的节点，颜色为红色；
• p 是 c 的父节点，颜色也是红色；
• g 是 p 的父节点，颜色为黑色（p 的祖父节点）；
• u 是 p 的兄弟节点，可能不存在，或者存在但颜色为黑色。

在这种情况下，红黑树的规则 3 规定，不能有两个连续的红色节点，而当前 c 和 p 都是红色，违反了这一规则。由于 u 不存在或是黑色，简单的颜色变换不足以恢复树的平衡，因此需要通过旋转加变色的方式来解决。

旋转和变色的分析： 为了消除连续的红色节点并恢复平衡，我们需要进行以下操作：

1. 旋转：根据 c 和 p 在 g 的相对位置，进行左旋或右旋。旋转的目的是让 p 上移，成为新子树的根，并将 g 下移。
2. 变色：将 p 变为黑色，将 g 变为红色。这样可以确保没有连续的红色节点，同时保证黑色节点数量保持不变。

旋转和变色的具体情况： 旋转的具体操作取决于 p 和 c 在 g 的位置关系，分为两种情况：

• p 是 g 的左子节点：
  • 如果 c 是 p 的左子节点（LL 失衡），进行右旋。
  • 如果 c 是 p 的右子节点（LR 失衡），先左旋 p，再右旋 g。
• p 是 g 的右子节点：
  • 如果 c 是 p 的右子节点（RR 失衡），进行左旋。
  • 如果 c 是 p 的左子节点（RL 失衡），先右旋 p，再左旋 g。

代码过程解讲解 以下是红黑树插入过程中处理情况 2：旋转 + 变色的代码段：

// 如果父节点是红色，则修复红黑树属性
while (parent && parent->_col == RED) {
    Node* grandfather = parent->_parent;
    if (parent == grandfather->_left) { // parent 在左 uncle 在右
        Node* uncle = grandfather->_right; // 情况 1: 叔叔节点是红色，需要重新着色
        if (uncle && uncle->_col == RED) {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather; // 继续向上修复
            parent = cur->_parent;
        } else {
            // 情况 2: 叔叔节点是黑色或不存在，需要旋转
            if (cur == parent->_left) {
                RotateR(grandfather); // 右旋转
                parent->_col = BLACK;
                grandfather->_col = RED;
            } else { // 情况 3
                RotateL(parent); // 先左旋父节点
                RotateR(grandfather); // 再右旋祖父节点
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            // 叔叔节点是黑色或不存在时，在旋转处理后当前最上面的是黑色节点，所以已经满足红黑树要求，可以直接 break
            break;
        }
    } else { // parent 在右 uncle 在左
        Node* uncle = grandfather->_left; // 情况 1: 叔叔节点是红色，需要重新着色
        if (uncle && uncle->_col == RED) {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather; // 继续向上修复
            parent = cur->_parent;
        } else {
            // 情况 2: 叔叔节点是黑色或不存在，需要旋转
            if (cur == parent->_right) {
                RotateL(grandfather); // 左旋转
                parent->_col = BLACK;
                grandfather->_col = RED;
            } else {
                RotateR(parent); // 先右旋父节点
                RotateL(grandfather); // 再左旋祖父节点
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            // 叔叔节点是黑色或不存在时，在旋转处理后当前最上面的是黑色节点，所以已经满足红黑树要求，可以直接 break
            break;
        }
    }
}
// 确保根节点始终为黑色
_root->_col = BLACK;
return true;
}

步骤 1：判断父节点 p 是否为红色 当 p 为红色时，由于 c 也是红色，因此违反了红黑树的规则 3，需要进行调整。

步骤 2：找到祖父节点 g 和叔叔节点 u 首先找到 p 的父节点 g（祖父节点）和 p 的兄弟节点 u（叔叔节点）。根据 p 在 g 的左侧还是右侧，分为两种处理情况。

步骤 3：判断叔叔节点 u 是否为黑色或不存在 如果 u 是黑色或不存在，表示我们不能通过简单的变色来修复树的平衡。此时需要进行旋转操作。

步骤 4：根据 c 和 p 的位置选择旋转方式

• LL 失衡：p 是 g 的左子节点，c 是 p 的左子节点。这种情况下需要对 g 进行右旋。
• LR 失衡：p 是 g 的左子节点，c 是 p 的右子节点。这种情况下先对 p 进行左旋，再对 g 进行右旋。
• RR 失衡：p 是 g 的右子节点，c 是 p 的右子节点。这种情况下需要对 g 进行左旋。
• RL 失衡：p 是 g 的右子节点，c 是 p 的左子节点。这种情况下先对 p 进行右旋，再对 g 进行左旋。

步骤 5：变色 无论是 LL、LR、RR 还是 RL 失衡，旋转完成后都需要进行变色操作。具体做法是：

1. 将 p 或 c 变为黑色，确保消除连续的红色节点。
2. 将 g 变为红色，保持子树的黑色节点数量不变。

步骤 6：确保根节点为黑 无论经过了多少次变色和旋转调整，红黑树的根节点必须始终为黑色。因此在代码的最后，我们将根节点重新着色为黑色，确保红黑树的规则始终得以遵守。

抽象图

情况 3：双旋 + 变色

在红黑树的插入过程中，当新插入的节点 c 和其父节点 p 都是红色，而 p 的兄弟节点 u（叔叔节点）不存在或是黑色时，若 c 和 p 处于特定位置关系，无法通过单次旋转解决平衡问题，就需要进行双旋 + 变色。这一过程的核心是通过两次旋转调整树的结构，并通过颜色变换来恢复红黑树的规则。

• c 是当前新插入的节点，颜色为红色。
• p 是 c 的父节点，颜色也是红色。
• g 是 p 的父节点，颜色为黑色（即 p 的祖父节点）。
• u 是 p 的兄弟节点（叔叔节点），可能不存在或是黑色。

此时，红黑树的规则 3 规定，不能有两个连续的红色节点，而 c 和 p 都是红色，违反了这一规则。由于 u 不存在或是黑色，变色不能解决问题，必须通过双旋 + 变色来调整树的平衡。

双旋和变色的分析： 在双旋中，我们首先会对 p 进行一次旋转，使 c 成为新的父节点；然后对 g 进行一次旋转，让 p 或 c 成为新的子树根节点。经过这两次旋转后，c 将上移，g 和 p 位置调整，确保没有连续的红色节点。

• LL 和 RR 失衡：直接通过一次旋转即可恢复平衡（属于单旋情况）。
• LR 和 RL 失衡：需要先对 p 进行一次旋转，使树局部结构转换为 LL 或 RR 失衡，接着对 g 进行第二次旋转来恢复平衡。这就是所谓的双旋。

p 是 g 的左子节点，c 是 p 的右子节点（LR 失衡）

在这种情况下，p 和 c 在 g 的左侧，但是 c 是 p 的右子节点：p 是 g 的右子节点，c 是 p 的左子节点（RL 失衡）

与 LR 失衡类似，只不过这次 p 和 c 在 g 的右侧，c 是 p 的左子节点：

根据红黑树的插入调整规则，以下代码展示了在双旋 + 变色情况下的处理：

// 如果父节点是红色，则修复红黑树属性
while (parent && parent->_col == RED) {
    Node* grandfather = parent->_parent;
    if (parent == grandfather->_left) { // parent 在左 uncle 在右
        Node* uncle = grandfather->_right; // 情况 1: 叔叔节点是红色，需要重新着色
        if (uncle && uncle->_col == RED) {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather; // 继续向上修复
            parent = cur->_parent;
        } else {
            // 情况 2: 叔叔节点是黑色或不存在，需要旋转
            if (cur == parent->_left) {
                RotateR(grandfather); // 右旋转
                parent->_col = BLACK;
                grandfather->_col = RED;
            } else { // 单旋无法解决问题
                RotateL(parent); // 先左旋父节点
                RotateR(grandfather); // 再右旋祖父节点
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            // 叔叔节点是黑色或不存在时，在旋转处理后当前最上面的是黑色节点，所以已经满足红黑树要求，可以直接 break
            break;
        }
    } else { // parent 在右 uncle 在左
        Node* uncle = grandfather->_left; // 情况 1: 叔叔节点是红色，需要重新着色
        if (uncle && uncle->_col == RED) {
            parent->_col = uncle->_col = BLACK;
            grandfather->_col = RED;
            cur = grandfather; // 继续向上修复
            parent = cur->_parent;
        } else {
            // 情况 2: 叔叔节点是黑色或不存在，需要旋转
            if (cur == parent->_right) {
                RotateL(grandfather); // 左旋转
                parent->_col = BLACK;
                grandfather->_col = RED;
            } else {
                RotateR(parent); // 先右旋父节点
                RotateL(grandfather); // 再左旋祖父节点
                cur->_col = BLACK;
                grandfather->_col = RED;
            }
            // 叔叔节点是黑色或不存在时，在旋转处理后当前最上面的是黑色节点，所以已经满足红黑树要求，可以直接 break
            break;
        }
    }
}
// 确保根节点始终为黑色
_root->_col = BLACK;
return true;
}

步骤 1：判断父节点 p 是否为红色 当 p 为红色时，且 u 为黑色或不存在，表示我们无法通过简单的变色来解决问题。此时必须通过旋转和变色来恢复平衡。

步骤 2：找到祖父节点 g 和叔叔节点 u 首先通过 p 找到其父节点 g，并找到 p 的兄弟节点 u，即 p 的叔叔节点。由于 u 为黑色或不存在，需要进行旋转和变色。

步骤 3：判断 p 和 c 的位置关系 根据 p 和 c 在 g 中的位置，可以确定是需要单旋还是双旋：

• 如果 c 是 p 的右子节点，而 p 是 g 的左子节点，则发生LR 失衡，需要进行双旋。
• 如果 c 是 p 的左子节点，而 p 是 g 的右子节点，则发生RL 失衡，也需要进行双旋。

步骤 4：执行双旋操作

• 对于 LR 失衡，先对 p 进行左旋，再对 g 进行右旋，让 c 成为新的根节点。
• 对于 RL 失衡，先对 p 进行右旋，再对 g 进行左旋，让 c 成为新的根节点。

步骤 5：变色 旋转完成后，通过变色来确保红黑树的平衡：

• 将 c 变为黑色，确保没有连续的红色节点。
• 将 g 变为红色，保持子树的黑色节点数量不变。

步骤 6：确保根节点为黑色 无论旋转多少次，红黑树的根节点必须始终保持为黑色。这是红黑树的第二条规则，确保红黑树的整体平衡性。

抽象图

红黑树的查找

红黑树的查找过程与二叉搜索树相同，时间复杂度为 O(log N)。通过比较节点的键值，沿着树的一条路径进行查找。

Node* Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) cur = cur->_right;
        else if (cur->_kv.first > key) cur = cur->_left;
        else return cur; // 找到目标节点
    }
    return nullptr; // 未找到
}

红黑树的验证

红黑树的验证是确保其平衡性和四条规则不被违反的关键步骤。红黑树插入或删除节点后，为了保持树的平衡性，必须通过递归检查整棵树，确保遵守红黑树的性质。这包括检查没有连续的红色节点、每条路径的黑色节点数量相同等。

Check 函数

Check 函数的主要任务是递归遍历整棵红黑树，检查以下几点：

1. 确保没有连续的红色节点（红色节点的子节点不能是红色，规则 3）。
2. 计算每条路径的黑色节点数量，并确保所有路径的黑色节点数量相同（规则 4）。

通过递归遍历树的左右子树，我们能够从根节点开始，验证每一个节点是否满足红黑树的规则。如果遇到违反红黑树规则的情况，Check 函数会返回 false。

Check 函数的实现

// 递归检查树是否满足红黑树的属性
bool Check(Node* root, int blackNum, const int refNum) {
    // 基本情况：如果到达叶子节点（空节点）
    if (root == nullptr) {
        // 到达空节点，说明这是一条从根到叶子的路径
        // 检查路径上黑色节点的数量是否与参考值相等
        if (refNum != blackNum) {
            cout << "路径中的黑色节点数量不相等" << endl;
            return false;
        }
        return true;
    }
    // 检查规则 3：确保没有连续的红色节点
    if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
        cout << root->_kv.first << "存在连续的红色节点" << endl;
        return false;
    }
    // 计算黑色节点数量：如果当前节点是黑色，增加计数
    if (root->_col == BLACK) {
        blackNum++;
    }
    // 递归检查左右子树
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

步骤 1：检查是否到达叶子节点（root == nullptr）

• 当遍历到叶子节点（空节点）时，说明这一条从根到叶子的路径走完了。
• 检查规则 4：红黑树的规则 4 要求每一条从根节点到叶子节点的路径上必须包含相同数量的黑色节点。因此，在到达空节点时，blackNum 记录了当前路径上的黑色节点数量。如果 blackNum 与参考路径的黑色节点数量 refNum 不相等，则违反了规则 4，返回 false。

步骤 2：检查红色节点是否连续

• 根据红黑树的规则 3，红色节点的子节点必须是黑色，即不能有连续的红色节点。如果当前节点 root 是红色，并且它的父节点也是红色，说明出现了连续的红色节点，违反规则 3。
• 在这种情况下，打印错误信息并返回 false，表示红黑树的结构被破坏了。

步骤 3：计算路径中的黑色节点数量

• 如果当前节点是黑色，则增加 blackNum 计数。因为每经过一个黑色节点，路径上的黑色节点数量会增加。
• 这个计数器会在递归遍历时传递给下一层的左右子树，确保能够统计每条路径上的黑色节点数量。

步骤 4：递归检查左右子树

• 使用递归的方式分别检查左子树和右子树，通过递归传递当前路径上的黑色节点计数器 blackNum。
• 如果左子树和右子树都满足红黑树的规则，递归返回 true；否则，返回 false，表示树的结构被破坏了。

IsBalance 函数的完整实现：

bool IsBalance() {
    // 如果树为空，认为是平衡的
    if (_root == nullptr) return true;
    // 检查根节点是否为红色（根节点必须是黑色，规则 2）
    if (_root->_col == RED) return false;
    // 计算参考的黑色节点数量（从根节点到最左侧的叶子节点）
    int refNum = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == BLACK) {
            ++refNum;
        }
        cur = cur->_left; // 走到最左侧，获取参考路径的黑色节点数量
    }
    // 递归检查整棵树，确保所有路径的黑色节点数量与参考值相同
    return Check(_root, 0, refNum);
}

1. 根节点检查：首先检查根节点的颜色，确保根节点是黑色。如果根节点为红色，则返回 false，因为违反了红黑树的规则 2。
2. 计算参考黑高：从根节点沿着左子树路径走到最左侧的叶子节点，统计路径上黑色节点的数量 refNum。这条路径的黑色节点数作为参考值，后续将与其他路径的黑色节点数进行比较。
3. 递归验证：使用辅助函数 Check，从根节点开始递归遍历整棵树，检查：
   • 每一条从根节点到叶子节点的路径上是否有相同数量的黑色节点；
   • 是否存在连续的红色节点。