【C++】：STL详解 —— 红黑树

目录

平衡二叉查找树

红黑树的概念

红黑树的五大性质

红黑树的效率

红黑树和AVL树的比较

 插入与删除操作

内存与实现复杂度

 经典性能数据对比

总结

对旋转的基本理解 

旋转的作用

左旋（Left Rotation）

右旋（Right Rotation）

红黑树的插入操作

一、插入步骤概述

二、详细插入流程

三、插入后的修复（Fix-Up）

Case 1

Case 2

Case 3

代码实现

红黑树的删除操作

一、删除操作总体步骤

二、详细删除流程

代码实现

红黑树源代码

---

平衡二叉查找树

平衡二叉查找树（Balanced Binary Search Tree） 是一类通过特定规则维持树结构相对平衡的二叉查找树，旨在解决普通二叉查找树（BST）在动态操作（插入、删除）中可能退化成链表的极端情况，从而保证最坏情况下的时间复杂度为 O(log n)。

常见平衡二叉查找树类型

类型	核心规则	适用场景
AVL树	严格平衡：任意节点的左右子树高度差≤1	读操作多，写操作少的场景
红黑树	宽松平衡：通过颜色和黑高约束路径长度，最长路径≤2倍最短路径	写操作频繁（如数据库、内存管理）
Splay树	局部性原理：最近访问的节点通过旋转移动到根，无需全局平衡	缓存、热点数据访问
Treap	结合BST和堆：节点同时有键值和随机优先级，通过优先级维护近似平衡	简单实现的概率平衡结构
B树/B+树	多路平衡树：每个节点可包含多个键，减少磁盘I/O（常用于数据库和文件系统）	大规模数据存储

平衡代价与性能权衡 

类型	插入/删除代价	查找代价	平衡严格性	适用场景
AVL树	高（频繁旋转）	最优（O(log n))	严格	静态数据、频繁查询
红黑树	较低（颜色调整为主）	接近AVL树	宽松	动态数据、频繁更新
Splay树	均摊O(log n)	均摊O(log n)	无全局规则	局部性强的数据访问
Treap	概率平衡（O(log n)）	O(log n)	概率性	简单实现、中等规模数据

为什么需要多种平衡树？

不同平衡树在平衡严格性、维护成本、适用场景上各有优劣：

• AVL树：适合读多写少的场景（如字典、静态索引）。

• 红黑树：工程实践中广泛使用（如C++ STL的std::map），平衡维护成本较低。

• B树/B+树：专为磁盘或数据库设计，减少I/O次数。

• Splay树：利用数据访问的局部性，无需显式平衡操作。

注意：红黑树和AVL树是理论结合实践的经典设计，而B树家族则在大规模数据存储中占据核心地位

红黑树的概念

红黑树（Red-Black Tree）的核心理念源于对平衡二叉查找树的探索，其历史可追溯至20世纪70年代计算机科学的快速发展期。以下是其关键发展节点：

• 1972年：德国计算机科学家鲁道夫·拜尔（Rudolf Bayer）提出对称二叉B树（Symmetric Binary B-Tree），这是红黑树的前身，旨在将B树的特性（多路平衡）引入二叉结构。

• 1978年：美国计算机科学家罗伯特·塞奇威克（Robert Sedgewick）和莱昂尼达斯·J·吉巴斯（Leonidas J. Guibas）在论文《A Dichromatic Framework for Balanced Trees》中首次明确使用红黑颜色标记来简化对称二叉B树的平衡规则，并将其命名为“红黑树”。

• 1980年代后：红黑树因其高效的动态操作性能，逐渐成为工程实践中的主流平衡树，被纳入多种编程语言标准库和操作系统核心模块。

• 红黑树虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目

红黑树的五大性质

红黑树通过以下规则确保平衡性：

1. 颜色属性：每个节点非红即黑。

2. 根节点为黑：根节点必须为黑色。

3. 叶子节点为黑：所有叶子节点（NIL节点，即空指针）视为黑色。

4. 红色不相邻：红色节点的子节点必须为黑色（禁止连续红色节点）。

5. 黑高一致：从任意节点到其所有叶子节点的路径中，黑色节点的数量相同（称为黑高）。

1、颜色属性

• 规则：每个节点必须是红色或黑色。

• 作用：颜色标记用于编码平衡规则，简化旋转和调整逻辑。

2、根节点为黑色

• 规则：树的根节点必须为黑色。

• 意义：避免根节点为红色时可能违反“红色不相邻”规则，确保树顶层的稳定性。

---

3、叶子节点为黑色

• 规则：所有叶子节点（即NIL节点，空指针或空节点）视为黑色。

• 注意：这里的“叶子节点”指实际数据节点的空子节点，而非存储数据的末端节点。

• 作用：统一路径终点的颜色，简化黑高计算。这样可以确保每个路径上的黑色节点数量相等，即使是经过了空节点的路径。

---

4、红色节点不相邻

• 规则：红色节点的父节点和子节点必须为黑色（即不能有连续的红色节点）。

• 意义：限制最长路径的长度，防止路径过长。

  • 最长路径示例：红黑交替（如黑→红→黑→红→黑）。

  • 最短路径：全黑节点。

---

5、黑高一致（Black Height Consistency）

• 规则：从任意节点到其所有叶子节点（NIL）的路径中，经过的黑色节点数量必须相同（称为黑高）。

•     黑节点A（黑高=2）/     \红B    黑C（黑高=1）/  \    /  \
  NIL NIL NIL NIL（黑高=1）

  从A到叶子：路径A→B→NIL的黑色节点数为2（A和NIL）；路径A→C→NIL的黑色节点数也为2（A、C、NIL中的C和NIL算作黑色）。

• 关键作用：黑高一致性确保树的高度最多为最短路径的2倍，维持平衡。

我们需要注意的是空节点（NIL节点）被认为是黑色的，从任意节点出发，到达其每个叶子节点的路径上的黑色节点数量必须相同

红黑树的效率

红黑树通过自平衡机制确保插入、删除、查找等操作的时间复杂度稳定在 O(log n)，其效率优势体现在以下方面：

 时间复杂度保障

操作	时间复杂度	原因
插入	O(log n)	通过颜色调整和至多2次旋转修复平衡，树高度被限制为O(log n)。
删除	O(log n)	删除后可能需3次旋转和颜色调整，但整体路径长度仍为对数级。
查找	O(log n)	树高度近似平衡，避免退化为链表。
遍历/范围查询	O(n)	中序遍历有序数据，与普通二叉搜索树一致。

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)

红黑树和AVL树的比较

 插入与删除操作

操作	红黑树	AVL 树
插入	最多需要 2 次旋转 + 颜色调整	可能触发多次旋转（单旋或双旋），最多 O(1) 次旋转
删除	最多需要 3 次旋转 + 颜色调整	可能从删除点回溯到根节点调整，最多 O(log n) 次旋转
维护成本	调整以颜色标记为主，旋转次数少	严格维护平衡因子，旋转频率高
动态性能	更适合频繁插入/删除的场景（如数据库事务日志）	频繁更新时性能下降明显

内存与实现复杂度

维度	红黑树	AVL 树
额外存储	每个节点仅需 1 bit 存储颜色（红/黑）	每个节点需存储 平衡因子（2~3 bit） 或 子树高度（4~8 bit）
实现复杂度	中等（需处理颜色调整和多种修复情况）	较高（需处理更多旋转类型和高度更新）
代码维护	规则明确，修复逻辑模块化（如插入分 3 种 Case）	需要处理复杂的平衡因子更新和旋转组合

 经典性能数据对比

• 插入 100 万随机数据：

  • 红黑树：耗时 ≈ 120 ms（旋转约 50 万次）

  • AVL 树：耗时 ≈ 180 ms（旋转约 80 万次）

• 插入 100 万有序数据：

  • 红黑树：耗时 ≈ 150 ms（旋转次数稳定）

  • AVL 树：耗时 ≈ 220 ms（频繁触发双旋）

• 查找 100 万次随机键：

  • 红黑树：耗时 ≈ 90 ms

  • AVL 树：耗时 ≈ 70 ms

总结

维度	红黑树	AVL 树	胜出场景
动态操作	✅ 更高效	❌ 高维护成本	高频插入/删除
查询速度	❌ 稍慢	✅ 更快	静态数据/低频更新
内存占用	✅ 更低	❌ 更高	内存敏感型系统
实现复杂度	✅ 更简单	❌ 复杂	快速开发/维护

最终建议：

• 选择 红黑树：若需在动态数据操作中平衡效率与成本（90% 的工程场景）。

• 选择 AVL 树：若数据稳定且追求极致查找性能（如科学计算、静态索引）。

对旋转的基本理解 

旋转（Rotation）是平衡二叉查找树（如红黑树、AVL树）中用于调整树结构的核心操作，目的是在不破坏二叉查找树性质的前提下，通过局部子树的重构来恢复平衡。以下是旋转的核心要点：

旋转的作用

• 降低树高：通过改变节点父子关系，减少树的高度差。

• 恢复平衡：解决因插入或删除导致的树结构失衡问题。

• 保持有序性：旋转后，二叉查找树的键值顺序（左小右大）依然成立。

左旋（Left Rotation）

当某个节点的右子树高度较高时，通过左旋提升右子节点为父节点。

关键注释说明：

1. 节点角色定义

   • subR：原父节点的右子节点，旋转后将成为新父节点

   • subRL：subR的左子节点，需要重新挂接到原父节点右侧

   • parentParent：原父节点的父节点，用于将subR接入原树结构

   • parent：原父节点，旋转后subR的左子节点

2. 连接关系调整

   • 将subRL从subR剥离并挂接到parent右侧

   • 将parent降级为subR的左子节点

   • 更新所有涉及的父指针（核心难点）

3. 根节点特殊处理

   • 当旋转节点是根节点时，需要更新整棵树的根指针

   • 非根节点时，通过parentParent将subR接入原树

// 左旋前结构：
//      parent
//     /      \
//    A       subR
//           /    \
//        subRL    C// 左旋后结构：
//        subR
//       /    \
//   parent    C
//    /   \
//   A  subRL

代码示例： 

template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)  // 左旋操作（以parent为旋转中心）
{// 步骤1：获取相关节点指针Node* subR = parent->_right;   // subR是parent的右子节点（将上升为新父节点）Node* subRL = subR->_left;     // subRL是subR的左子节点（可能为空）Node* parentParent = parent->_parent;  // 保存原父节点的父节点（即subR的新父节点）// 步骤2：重构子树连接关系// --------------------------------------------------------------parent->_right = subRL;        // 将subRL挂接到parent的右侧if (subRL)                     // 如果subRL存在，更新其父指针指向parent{subRL->_parent = parent;}subR->_left = parent;          // 将parent挂接为subR的左子节点parent->_parent = subR;        // 更新parent的父指针指向subR// 步骤3：将subR连接到原树结构中// --------------------------------------------------------------if (_root == parent)           // 如果parent是根节点{         _root = subR;              // 更新根节点为subRsubR->_parent = nullptr;   // 新根节点的父指针置空} else                           // 如果parent不是根节点{                       // 判断原父节点是左子还是右子，并将subR挂接到正确位置if (parentParent->_left == parent) {parentParent->_left = subR;} else {parentParent->_right = subR;}subR->_parent = parentParent;  // 更新subR的父指针}
}

右旋（Right Rotation）

当某个节点的左子树高度较高时，通过右旋提升左子节点为父节点。

关键注释说明

1. 节点角色定义

   • subL：parent的左子节点，旋转后成为新父节点

   • subLR：subL的右子节点，需要挂接到parent左侧

   • parentParent：原父节点的父节点，用于将subL接入原树

   • parent：原父节点，旋转后成为subL的右子节点

2. 连接关系调整
   • 剥离subLR：将subL的右子树挂接到parent左侧
   • 降级parent：将parent变为subL的右子节点
   • 父指针更新：确保所有涉及节点正确关联
3. 根节点特殊处理
   • 若parent是根节点，需更新_root指针
   • 非根节点时通过parentParent将subL接入原树

// 右旋前结构：
//        parent
//       /      \
//    subL       C
//    /   \
//   A   subLR// 右旋后结构：
//        subL
//       /    \
//      A    parent
//           /    \
//        subLR    C

• 

 代码示例：

template<class K, class V>
void AVLTree<K, V>::RotateR(Node* parent)  // 右旋操作（以parent节点为旋转中心）
{// 步骤1：获取相关节点指针// ----------------------------------------------------------Node* subL = parent->_left;    // subL是parent的左子节点（将上升为新父节点）Node* subLR = subL->_right;    // subLR是subL的右子节点（可能为空）// 步骤2：重构子树连接关系// ----------------------------------------------------------// 将subLR从subL剥离，挂接到parent左侧parent->_left = subLR;         // parent的左子树指向subLRif (subLR)                     // 若subLR存在，更新其父指针指向parent{subLR->_parent = parent;}// 将parent降级为subL的右子节点subL->_right = parent;         // subL的右子树接管parentparent->_parent = subL;        // 更新parent的父指针指向subL// 步骤3：将subL连接到原树结构中// ----------------------------------------------------------Node* parentParent = parent->_parent;  // 保存原父节点的父节点if (_root == parent)           // Case1：parent是根节点{_root = subL;              // 更新根节点为subLsubL->_parent = nullptr;   // 新根节点的父指针置空} else                         // Case2：parent非根节点{// 判断原父节点是左子还是右子，将subL挂接到正确位置if (parentParent->_left == parent) {parentParent->_left = subL;} else {parentParent->_right = subL;}subL->_parent = parentParent;  // 更新subL的父指针}
}

红黑树的插入操作

红黑树的插入操作分为两个阶段：二叉查找树插入 和 颜色调整与旋转修复。

一、插入步骤概述

1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏

二、详细插入流程

1. 按BST规则插入

• 从根节点开始，递归比较键值大小，找到插入位置。

• 创建新节点，颜色设为 红色（保证不破坏黑高，但可能引发双红冲突）。

• 将新节点挂载到父节点的左/右子节点。

三、插入后的修复（Fix-Up）

修复操作的目标是消除双红冲突（父子节点均为红色），确保满足红黑树的五大性质。修复逻辑分为 3种情况：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

• Case 1: 叔叔节点为红色

• Case 2: 叔叔节点为黑，且新节点与父节点方向一致

• Case 3: 叔叔节点为黑，且新节点与父节点方向不一致

Case 1

叔叔节点为红色

• 条件：父节点和叔叔节点均为红色。

• 操作：

  1. 将父节点和叔叔节点变黑。

  2. 祖父节点变红。

  3. 递归检查祖父节点（可能引发新的双红冲突）。

注意：

1. 如果g是根节点，调整完后要将g变为黑色
2. 如果g不是根节点，继续向上调整

原结构：        黑祖父                    修复后：       红祖父/     \                              /     \红父     红叔                       黑父     黑叔/                                  /红新节点                           红新节点

Case 2

叔叔节点为黑，且新节点与父节点方向一致

• 条件：

  • 父节点是祖父节点的左子，新节点是父节点的左子（LL型）。
    或

  • 父节点是祖父节点的右子，新节点是父节点的右子（RR型）。

• 操作：

  1. 将父节点变黑，祖父节点变红。

  2. 对祖父节点进行 右旋（LL型）或 左旋（RR型）。

Case 3

叔叔节点为黑，且新节点与父节点方向不一致

• 条件：

  • 父节点是祖父节点的左子，新节点是父节点的右子（LR型）。
    或

  • 父节点是祖父节点的右子，新节点是父节点的左子（RL型）。

• 操作：

  1. 对父节点进行 左旋（LR型）或 右旋（RL型），转化为Case 3。

  2. 继续按Case 3处理。

     1. 将父节点变黑，祖父节点变红。

     2. 对祖父节点进行 右旋（LL型）或 左旋（RR型）。

代码实现

// 红黑树插入函数，返回插入节点指针和是否插入成功的布尔值
pair<Node*, bool> Insert(const pair<K, V>& kv)
{// ---------------------- 空树情况处理 ----------------------if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;  // 根节点必须为黑色return make_pair(_root, true); // 返回新根节点和成功状态}// ---------------------- BST标准插入流程 ----------------------Node* cur = _root;Node* parent = nullptr;// 查找插入位置while (cur) {if (kv.first < cur->_kv.first)    // 向左子树查找{parent = cur;cur = cur->_left;} else if (kv.first > cur->_kv.first)  // 向右子树查找{parent = cur;cur = cur->_right;} else   // 键值已存在{return make_pair(cur, false); // 返回已存在节点和失败状态}}// 创建新节点（默认红色）cur = new Node(kv);Node* newnode = cur;  // 记录新节点用于返回// 挂载到父节点下if (kv.first < parent->_kv.first) {parent->_left = cur;} else {parent->_right = cur;}cur->_parent = parent;  // 维护父指针// ---------------------- 红黑树平衡调整 ----------------------while (parent && parent->_col == RED)     // 仅处理双红冲突{Node* grandfather = parent->_parent;  // 祖父节点必存在if (parent == grandfather->_left)     // 父节点是左子树情况{// Case 1：叔叔存在且为红（颜色扩散）//        g(B)               --> g(R)//       /   \               /   \//     p(R)   u(R)  ==>    p(B)   u(B)//    ///  c(R) Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 向上递归处理cur = grandfather;parent = cur->_parent;} // Case 2/3：叔叔为黑或不存在（需要旋转）else {if (cur == parent->_left)   // LL型{// 右旋祖父节点//        g(B)                 p(B)//       /                   /     \//     p(R)       ==>      c(R)    g(R)//    ///  c(R)RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;} else   // LR型（先左旋父节点转为LL型）{//        g(B)                g(B)               c(B)//       /                   /                 /     \//     p(R)       ==>      c(R)     ==>     p(R)    g(R)//       \                 ///       c(R)           p(R)RotateLR(grandfather);  // 组合旋转：先左旋parent，再右旋grandfathergrandfather->_col = RED;cur->_col = BLACK;  // cur成为局部根}break;  // 旋转后子树平衡，无需继续处理}} // 对称处理父节点是右子树的情况else {  Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)   // Case 1{uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;} else {if (cur == parent->_left)   // RL型{//        g(B)                g(B)               c(B)//           \                   \             /     \//           p(R)    ==>         c(R)  ==>  g(R)    p(R)//          /                     \//        c(R)                   p(R)RotateRL(grandfather);  // 组合旋转：先右旋parent，再左旋grandfathergrandfather->_col = RED;cur->_col = BLACK;} else   // RR型{RotateL(grandfather);  // 左单旋grandfather->_col = RED;parent->_col = BLACK;}break;}}}// ---------------------- 强制根节点为黑 ----------------------_root->_col = BLACK;  // 防止case1向上传播导致根变红return make_pair(newnode, true);  // 返回新节点和成功状态
}

红黑树的删除操作

红黑树的删除操作比插入更复杂，因为它可能破坏红黑树的平衡性质（尤其是黑高）。删除的核心步骤包括 二叉查找树删除 和 颜色/结构调整。

一、删除操作总体步骤

1. 标准BST删除：找到待删除节点，按BST规则删除。

2. 记录关键信息：

   • 被删除节点颜色（黑色需修复，红色无需处理）。

   • 确定替代节点（实际被移除的节点或其后继）。

3. 修复红黑树性质：若删除的是黑色节点，需调整颜色和旋转。

二、详细删除流程

步骤1：执行BST删除

根据被删除节点的子节点数量，分为三种情况：

• 无子节点：直接删除，用NIL节点替代。

• 一个子节点：用子节点替代被删除节点。

• 两个子节点：找到后继节点，复制键值后删除后继节点。

步骤2：确定替代节点

• 被删除节点为叶子节点：替代节点为NIL。

• 被删除节点有一个子节点：替代节点为子节点。

• 被删除节点有两个子节点：替代节点为后继节点。

步骤3：修复双黑问题

若被删除节点是黑色，替代节点（或NIL）视为“双黑”，需根据兄弟节点颜色和子节点情况修复。修复分为 4种情况：

情况1：兄弟节点为红色

• 操作：

  1. 将兄弟节点 B 变黑，父节点 P 变红。

  2. 对 P 进行左旋（若替代节点 N 是左子）或右旋（若 N 是右子）。

  3. 更新兄弟节点 B 为旋转后的新兄弟（此时必为黑色），进入情况2、3或4。

情况2：兄弟节点为黑，且兄弟的两个子节点均为黑

• 操作：

  1. 将兄弟节点 B 变红。

  2. 将双黑问题上移至父节点 P。

  3. 若 P 原为红色，则将其变黑，修复完成；否则，以 P 为新的双黑节点继续处理。

原结构：         P(B)              → 修复后：    P(B)/   \                           /   \N(DB) S(B)                     N(B)   S(R)/   \                           /   \SL(B) SR(B)                    SL(B) SR(B)

情况3：兄弟节点为黑，兄弟的近侄子为红，远侄子为黑

• 操作：

  1. 将兄弟的近侄子变黑，兄弟变红。

  2. 对兄弟节点 S 进行右旋（若 N 是左子）或左旋（若 N 是右子）。

  3. 更新兄弟节点为原近侄子，进入情况4。

原结构：         P(B)              → 旋转后：    P(B)/   \                           /   \N(DB) S(B)                     N(DB) SL(B)/   \                             \SL(R) SR(B)                         S(R)\SR(B)

情况4：兄弟节点为黑，兄弟的远侄子为红

• 操作：

  1. 将兄弟节点 S 的颜色设为父节点 P 的颜色。

  2. 将父节点 P 和兄弟的远侄子变黑。

  3. 对父节点 P 进行左旋（若 N 是左子）或右旋（若 N 是右子）。

  4. 双黑问题消除，修复完成。

原结构：         P(?)              → 旋转后：    S(?)/   \                           /   \N(DB) S(B)                     P(B)  SR(B)/   \                     /   \SL(?) SR(R)              N(B) SL(?)

代码实现

// 红黑树删除函数，返回删除是否成功
bool Erase(const K& key)
{// ---------------------- 查找待删除节点 ----------------------Node* parent = nullptr;Node* cur = _root;Node* delParentPos = nullptr; // 实际删除节点的父节点Node* delPos = nullptr;       // 实际删除的节点while (cur) {if (key < cur->_kv.first) // 向左子树查找{    parent = cur;cur = cur->_left;} else if (key > cur->_kv.first)  // 向右子树查找{parent = cur;cur = cur->_right;} else   // 找到目标节点，根据子节点情况处理{if (cur->_left == nullptr)    // 左子树为空{if (cur == _root)        // 删除的是根节点{_root = _root->_right; // 右子树成为新根if (_root) {_root->_parent = nullptr;_root->_col = BLACK; // 根必须为黑}delete cur;return true;} else {delParentPos = parent; // 记录实际删除节点及其父节点delPos = cur;}break; // 进入红黑树调整阶段} else if (cur->_right == nullptr)  // 右子树为空{if (cur == _root)  // 处理根节点{_root = _root->_left;if (_root) {_root->_parent = nullptr;_root->_col = BLACK;}delete cur;return true;} else {delParentPos = parent;delPos = cur;}break;} else  // 左右子树均不为空（替换法删除）{// 找到右子树最小节点作为替代节点Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left) {minParent = minRight;minRight = minRight->_left;}// 将替代节点的值复制到当前节点cur->_kv = minRight->_kv; delParentPos = minParent; // 实际删除节点变为minRightdelPos = minRight;break; // 进入调整阶段}}}if (!delPos) return false; // 未找到待删除节点// ---------------------- 红黑树平衡调整 ----------------------Node* del = delPos;       // 记录实际删除节点Node* delP = delParentPos;if (del->_col == BLACK)  // 只有删除黑色节点需要调整{if (del->_left)      // Case 0：存在红色左子节点{del->_left->_col = BLACK; // 直接变黑补偿黑高} else if (del->_right)  // Case 0：存在红色右子节点{del->_right->_col = BLACK;} else               // 双黑情况，需要复杂调整{while (del != _root)  // 可能调整到根节点{// 分为左右子树两种情况处理（镜像对称）if (del == delP->_left)  // 删除的是左子节点{Node* brother = delP->_right; // 兄弟节点// 情况1：兄弟为红色 --> 转为兄弟为黑的情况if (brother->_col == RED) {delP->_col = RED;brother->_col = BLACK;RotateL(delP);       // 左旋父节点brother = delP->_right; // 更新兄弟节点}// 情况2：兄弟为黑且子节点全黑if ((!brother->_left || brother->_left->_col == BLACK) &&(!brother->_right || brother->_right->_col == BLACK)) {brother->_col = RED;  // 兄弟变红if (delP->_col == RED)  // 父节点红变黑终止{delP->_col = BLACK;break;}// 向上递归处理del = delP; delP = del->_parent;} else {// 情况3：兄弟左子红，右子黑 --> 转为情况4if (!brother->_right || brother->_right->_col == BLACK) {brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother); // 右旋兄弟节点brother = delP->_right; // 更新兄弟}// 情况4：兄弟右子红（最终调整）brother->_col = delP->_col;delP->_col = BLACK;brother->_right->_col = BLACK;RotateL(delP); // 左旋父节点break; // 调整完成}} }}}// ---------------------- 实际节点删除操作 ----------------------if (del->_left == nullptr) { // 实际删除节点的左子树为空if (del == delP->_left) {delP->_left = del->_right; // 用右子树替代if (del->_right)del->_right->_parent = delP;} else {delP->_right = del->_right;if (del->_right)del->_right->_parent = delP;}} delete del; // 释放节点内存return true;
}

红黑树源代码

//枚举定义结点的颜色
enum Colour
{RED,BLACK
};//红黑树结点的定义
template<class K, class V>
struct RBTreeNode
{//三叉链RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;//存储的键值对pair<K, V> _kv;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};//红黑树的实现
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://构造函数RBTree():_root(nullptr){}//拷贝构造RBTree(const RBTree<K, V>& t){_root = _Copy(t._root, nullptr);}//赋值运算符重载（现代写法）RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root);return *this;}//析构函数~RBTree(){_Destroy(_root);_root = nullptr;}//查找函数Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_kv.first) //key值小于该结点的值{cur = cur->_left; //在该结点的左子树当中查找}else if (key > cur->_kv.first) //key值大于该结点的值{cur = cur->_right; //在该结点的右子树当中查找}else //找到了目标结点{return cur; //返回该结点}}return nullptr; //查找失败}//插入函数pair<Node*, bool> Insert(const pair<K, V>& kv){if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点{_root = new Node(kv);_root->_col = BLACK; //根结点必须是黑色return make_pair(_root, true); //插入成功}//1、按二叉搜索树的插入方法，找到待插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //待插入结点的key值等于当前结点的key值{return make_pair(cur, false); //插入失败}}//2、将待插入结点插入到树中cur = new Node(kv); //根据所给值构造一个结点Node* newnode = cur; //记录新插入的结点（便于后序返回）if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent->_left = cur;cur->_parent = parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent->_right = cur;cur->_parent = parent;}//3、若插入结点的父结点是红色的，则需要对红黑树进行调整while (parent&&parent->_col == RED){Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在if (parent == grandfather->_left) //parent是grandfather的左孩子{Node* uncle = grandfather->_right; //uncle是grandfather的右孩子if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateR(grandfather); //右单旋//颜色调整grandfather->_col = RED;parent->_col = BLACK;}else //cur == parent->_right{RotateLR(grandfather); //左右双旋//颜色调整grandfather->_col = RED;cur->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}else //parent是grandfather的右孩子{Node* uncle = grandfather->_left; //uncle是grandfather的左孩子if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateRL(grandfather); //右左双旋//颜色调整cur->_col = BLACK;grandfather->_col = RED;}else //cur == parent->_right{RotateL(grandfather); //左单旋//颜色调整grandfather->_col = RED;parent->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}}_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）return make_pair(newnode, true); //插入成功}//删除函数bool Erase(const K& key){//用于遍历二叉树Node* parent = nullptr;Node* cur = _root;//用于标记实际的待删除结点及其父结点Node* delParentPos = nullptr;Node* delPos = nullptr;while (cur){if (key < cur->_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (key > cur->_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //找到了待删除结点{if (cur->_left == nullptr) //待删除结点的左子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_right; //让根结点的右子树作为新的根结点if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos = parent; //标记实际删除结点的父结点delPos = cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else if (cur->_right == nullptr) //待删除结点的右子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_left; //让根结点的左子树作为新的根结点if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos = parent; //标记实际删除结点的父结点delPos = cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的keycur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的valuedelParentPos = minParent; //标记实际删除结点的父结点delPos = minRight; //标记实际删除的结点break; //进行红黑树的调整以及结点的实际删除}}}if (delPos == nullptr) //delPos没有被修改过，说明没有找到待删除结点{return false;}//记录待删除结点及其父结点（用于后续实际删除）Node* del = delPos;Node* delP = delParentPos;//调整红黑树if (delPos->_col == BLACK) //删除的是黑色结点{if (delPos->_left) //待删除结点有一个红色的左孩子（不可能是黑色）{delPos->_left->_col = BLACK; //将这个红色的左孩子变黑即可}else if (delPos->_right) //待删除结点有一个红色的右孩子（不可能是黑色）{delPos->_right->_col = BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delPos != _root) //可能一直调整到根结点{if (delPos == delParentPos->_left) //待删除结点是其父结点的左孩子{Node* brother = delParentPos->_right; //兄弟结点是其父结点的右孩子//情况一：brother为红色if (brother->_col == RED){delParentPos->_col = RED;brother->_col = BLACK;RotateL(delParentPos);//需要继续处理brother = delParentPos->_right; //更新brother（否则在本循环中执行其他情况的代码会出错）}//情况二：brother为黑色，且其左右孩子都是黑色结点或为空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParentPos->_col == RED){delParentPos->_col = BLACK;break;}//需要继续处理delPos = delParentPos;delParentPos = delPos->_parent;}else{//情况三：brother为黑色，且其左孩子是红色结点，右孩子是黑色结点或为空if ((brother->_right == nullptr) || (brother->_right->_col == BLACK)){brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother);//需要继续处理brother = delParentPos->_right; //更新brother（否则执行下面情况四的代码会出错）}//情况四：brother为黑色，且其右孩子是红色结点brother->_col = delParentPos->_col;delParentPos->_col = BLACK;brother->_right->_col = BLACK;RotateL(delParentPos);break; //情况四执行完毕后调整一定结束}}else //delPos == delParentPos->_right //待删除结点是其父结点的左孩子{Node* brother = delParentPos->_left; //兄弟结点是其父结点的左孩子//情况一：brother为红色if (brother->_col == RED) //brother为红色{delParentPos->_col = RED;brother->_col = BLACK;RotateR(delParentPos);//需要继续处理brother = delParentPos->_left; //更新brother（否则在本循环中执行其他情况的代码会出错）}//情况二：brother为黑色，且其左右孩子都是黑色结点或为空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParentPos->_col == RED){delParentPos->_col = BLACK;break;}//需要继续处理delPos = delParentPos;delParentPos = delPos->_parent;}else{//情况三：brother为黑色，且其右孩子是红色结点，左孩子是黑色结点或为空if ((brother->_left == nullptr) || (brother->_left->_col == BLACK)){brother->_right->_col = BLACK;brother->_col = RED;RotateL(brother);//需要继续处理brother = delParentPos->_left; //更新brother（否则执行下面情况四的代码会出错）}//情况四：brother为黑色，且其左孩子是红色结点brother->_col = delParentPos->_col;delParentPos->_col = BLACK;brother->_left->_col = BLACK;RotateR(delParentPos);break; //情况四执行完毕后调整一定结束}}}}}//进行实际删除if (del->_left == nullptr) //实际删除结点的左子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_right;if (del->_right)del->_right->_parent = delP;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = delP;}}else //实际删除结点的右子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = delP;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = delP;}}delete del; //实际删除结点return true;}private://拷贝树Node* _Copy(Node* root, Node* parent){if (root == nullptr){return nullptr;}Node* copyNode = new Node(root->_data);copyNode->_parent = parent;copyNode->_left = _Copy(root->_left, copyNode);copyNode->_right = _Copy(root->_right, copyNode);return copyNode;}//析构函数子函数void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;//建立subRL与parent之间的联系parent->_right = subRL;if (subRL)subRL->_parent = parent;//建立parent与subR之间的联系subR->_left = parent;parent->_parent = subR;//建立subR与parentParent之间的联系if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;//建立subLR与parent之间的联系parent->_left = subLR;if (subLR)subLR->_parent = parent;//建立parent与subL之间的联系subL->_right = parent;parent->_parent = subL;//建立subL与parentParent之间的联系if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}//左右双旋void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}//右左双旋void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}Node* _root; //红黑树的根结点
};