本文介绍了红黑树的概念、五条规则（实际四条核心）及其平衡性原理，详细阐述了基于 C++ 的红黑树节点结构设计与插入操作实现。内容涵盖插入后的三种调整情况（变色、单旋、双旋），以及通过递归验证树平衡性的方法，确保时间复杂度维持在 O(log N)。
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它通过在节点上附加额外的颜色属性（红色或黑色），并遵循一定的规则来确保树的高度尽可能小，确保没有一条路径会比其他路径长出 2 倍，从而在最坏的情况下保证 O(log N) 的操作效率。
红黑树的每个节点除了键值外，还存储一个颜色属性。要保持树的平衡性，必须满足以下规则：
bh）。这些规则确保了红黑树的近似平衡。通过规则 4，可以推导出红黑树的最长路径不会超过最短路径的两倍，这就意味着红黑树的高度维持在 O(log N)，从而保证了查找、插入和删除的效率。
红黑树的一个重要特性是保持相对平衡，从而使得查找、插入和删除操作的时间复杂度都能保持在 O(log N) 的范围内。具体而言，红黑树的设计确保了最长路径的长度不会超过最短路径的 2 倍。这是通过红黑树的四条规则，尤其是规则 2、3 和 4 来实现的。
为了更好地理解红黑树的平衡性，让我们复习一下红黑树的四条基本规则：
其中，规则 4 是红黑树平衡的核心，它直接限制了路径上的黑色节点数量，进而影响树的高度和路径长度。
根据规则 4，从根节点到每一个叶子节点的路径上，黑色节点的数量是相同的。因此，最短路径就是只有黑色节点的路径。这种路径上没有任何红色节点，只有黑色节点。
我们用 bh（Black Height，黑高）来表示从根节点到叶子节点的黑色节点数量（不包括红色节点）。因此，最短路径的长度等于 bh。
根据规则 3，红色节点的子节点必须是黑色，意味着不可能有连续的红色节点。因此，在极端情况下，最长的路径是红黑交替的路径。
如果路径上的黑色节点数量为 bh，那么在最坏的情况下，每个黑色节点下面都有一个红色节点。因此，最长的路径将是交替排列的红黑节点的路径，其长度为 2 * bh。
红黑树通过严格的颜色规则和旋转操作，确保了树的路径长度差异有限。通过保证黑色节点数目相等和没有连续的红色节点，红黑树确保了每一条从根到叶子的路径上的黑色节点数量相同，同时限制了红色节点的数量。
具体来说，红黑树的平衡性源于以下几个因素：
由于红黑树的这些规则，红黑树的最短路径和最长路径之间的长度差异不会超过 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 的规则查找插入位置：如果插入的值小于当前节点的值，则向左子树移动。如果插入的值大于当前节点的值，则向右子树移动。 这一步的目的是在红黑树中找到合适的插入位置。此时仅仅是按照二叉搜索树的规则，不涉及颜色和平衡性问题。
新增节点颜色的选择 当我们找到插入位置后，分为两种情况：
root 位置的时候变为黑色即可。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 是红色，意味着子树中有过多的红色节点，此时我们需要进行变色：
p 和 u 变为黑色：通过变色，我们让这两个子树的黑色节点数量增加，这样所有从 g 到叶子的路径上的黑色节点数量保持一致。g 变为红色：我们将 g 变为红色，保持整体黑色节点数平衡。步骤 4：递归处理祖父节点 g
此时，g 被变为红色，可能会导致它与其父节点形成连续的红色节点。因此，我们将 g 作为新的 c，继续向上修复，重复这一过程。
步骤 5：确保根节点为黑色 无论经过了多少次变色和旋转调整，红黑树的根节点必须始终为黑色。因此在代码的最后，我们将根节点重新着色为黑色，确保红黑树的规则始终得以遵守。
抽象图
p为红，u为空或不存在，单旋 + 变色在红黑树的插入过程中，情况 2 涉及的是当新插入的节点 c 和它的父节点 p 都是红色，而 p 的兄弟节点 u（叔叔节点）不存在或是黑色的情况。此时，简单的变色操作不足以解决问题，必须进行旋转加变色来恢复平衡。
c 是新插入的节点，颜色为红色；p 是 c 的父节点，颜色也是红色；g 是 p 的父节点，颜色为黑色（p 的祖父节点）；u 是 p 的兄弟节点，可能不存在，或者存在但颜色为黑色。在这种情况下，红黑树的规则 3 规定，不能有两个连续的红色节点，而当前 c 和 p 都是红色，违反了这一规则。由于 u 不存在或是黑色，简单的颜色变换不足以恢复树的平衡，因此需要通过旋转加变色的方式来解决。
旋转和变色的分析： 为了消除连续的红色节点并恢复平衡，我们需要进行以下操作：
c 和 p 在 g 的相对位置，进行左旋或右旋。旋转的目的是让 p 上移，成为新子树的根，并将 g 下移。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 的位置选择旋转方式
p 是 g 的左子节点，c 是 p 的左子节点。这种情况下需要对 g 进行右旋。p 是 g 的左子节点，c 是 p 的右子节点。这种情况下先对 p 进行左旋，再对 g 进行右旋。p 是 g 的右子节点，c 是 p 的右子节点。这种情况下需要对 g 进行左旋。p 是 g 的右子节点，c 是 p 的左子节点。这种情况下先对 p 进行右旋，再对 g 进行左旋。步骤 5：变色 无论是 LL、LR、RR 还是 RL 失衡，旋转完成后都需要进行变色操作。具体做法是：
p 或 c 变为黑色，确保消除连续的红色节点。g 变为红色，保持子树的黑色节点数量不变。步骤 6：确保根节点为黑 无论经过了多少次变色和旋转调整，红黑树的根节点必须始终为黑色。因此在代码的最后，我们将根节点重新着色为黑色，确保红黑树的规则始终得以遵守。
抽象图
在红黑树的插入过程中，当新插入的节点 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 位置调整，确保没有连续的红色节点。
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：执行双旋操作
p 进行左旋，再对 g 进行右旋，让 c 成为新的根节点。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 函数的主要任务是递归遍历整棵红黑树，检查以下几点：
通过递归遍历树的左右子树，我们能够从根节点开始，验证每一个节点是否满足红黑树的规则。如果遇到违反红黑树规则的情况，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）
blackNum 记录了当前路径上的黑色节点数量。如果 blackNum 与参考路径的黑色节点数量 refNum 不相等，则违反了规则 4，返回 false。步骤 2：检查红色节点是否连续
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);
}
false，因为违反了红黑树的规则 2。refNum。这条路径的黑色节点数作为参考值，后续将与其他路径的黑色节点数进行比较。Check，从根节点开始递归遍历整棵树，检查：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online