红黑树通过颜色规则和旋转维持平衡，确保操作时间复杂度为O(log n)。1. 节点分红黑，根和叶为黑，红节点子必黑，任一路径黑节点数相同。2. 插入默认红色，通过变色和旋转修复冲突。3. 删除若破坏黑高则需修复，涉及兄弟节点状态判断。4. 左旋右旋调整结构，保持BST性质同时恢复平衡。5. C++中用模板类封装，含插入、删除、查找及修复函数，配合智能指针管理内存。核心在于维护黑高一致与无连续红节点，实现复杂但高效。
红黑树是一种自平衡的二叉查找树，它通过特定的颜色规则和旋转操作来保证树的高度接近 log(n)，从而确保插入、删除和查找操作的时间复杂度稳定在 O(log n)。C++ 中标准库的 std::map 和 std::set 通常就是基于红黑树实现的。
红黑树的基本性质
每个节点带有颜色（红色或黑色），满足以下五条性质：
- 节点是红色或黑色
- 根节点是黑色
- 所有叶子节点（NULL 节点）视为黑色
- 红色节点的子节点必须是黑色（不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高一致）
这些性质共同作用，使得最长路径不超过最短路径的两倍，从而保持近似平衡。
节点结构设计
定义一个红黑树节点类，包含值、颜色、左右子节点和父节点指针：
立即学习“C++免费学习笔记（深入）”；
enum Color { RED, BLACK };
template
struct RBNode {
T data;
Color color;
RBNode left;
RBNode right;
RBNode* parent;
RBNode(T val) : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};
注意：新插入节点默认为红色，这样可以最小化对黑高性质的影响。
插入操作与修复
插入流程类似二叉搜索树，插入后根据红黑性质进行调整：
- 如果树为空，创建根节点并设为黑色
- 否则按 BST 规则插入新节点（红色）
- 调用修复函数 insertFix 处理可能的颜色冲突
修复主要处理“父节点为红色”的情况，分为几种情形：
- 叔叔节点为红色：变色并上移祖父
- 叔叔为黑色且当前节点是右孩子：左旋
- 叔叔为黑色且当前是左孩子：右旋并重新着色
核心思想是通过变色和最多两次旋转恢复平衡。
删除操作与修复
删除比插入更复杂。先执行普通 BST 删除：
- 无子节点：直接删除
- 仅一个子节点：用子节点替代
- 有两个子节点：找中序后继替换并删除后继
若被删的是黑色节点，可能导致黑高不一致，需调用 deleteFix 修复。修复过程考虑兄弟节点颜色和结构，通过旋转和变色重新平衡。
左旋与右旋操作
旋转是维持平衡的核心手段：
- 左旋：以 x 为支点，x 的右孩子 y 上提，y 的左子树变为 x 的右子树
- 右旋：以 y 为支点，y 的左孩子 x 上提，x 的右子树变为 y 的左子树
旋转不破坏 BST 性质，但能改变树形结构，配合颜色调整可恢复红黑性质。
C++ 实现要点
完整实现需封装成模板类，管理根节点和 NIL 叶子（可用静态空节点表示）。关键成员函数包括：
- insert(T val)
- remove(T val)
- search(T val)
- 辅助函数：leftRotate, rightRotate, insertFix, deleteFix
内存管理建议使用智能指针或手动 new/delete 配合析构函数释放资源。
基本上就这些。红黑树难点在于插入删除后的修复逻辑分支较多，需要仔细处理每种情形。理解旋转和颜色变化的本质是为了维持黑高和父子颜色约束。一旦掌握模式，代码实现是顺理成章的。
