红黑树通过颜色标记和旋转维持平衡，保证操作时间复杂度O(log n)。其性质包括：根黑、叶黑、红节点子节点为黑、黑高一致。插入后通过变色和左右旋修复，删除黑色节点后需调整兄弟子树恢复黑高，核心是五条性质的维护。
红黑树是一种自平衡的二叉查找树，通过颜色标记和旋转操作维持树的平衡，保证插入、删除、查找操作的时间复杂度为 O(log n)。C++ 实现红黑树需要理解其核心性质和调整逻辑。
红黑树的性质
每个节点具有以下特征：
- 节点是红色或黑色
- 根节点是黑色
- 所有叶子（NULL 节点）视为黑色
- 红色节点的子节点必须是黑色（不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点（黑高一致）
节点结构设计
定义一个树节点类，包含值、颜色、左右子节点和父指针：
enum Color { RED, BLACK };
struct Node {
int data;
Color color;
Node left, right, *parent;
Node(int value) : data(value), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};
立即学习“C++免费学习笔记（深入）”；
使用枚举表示颜色，初始化默认为红色（插入时临时设为红，再根据规则调整）。
基本操作：插入与修复
插入操作沿用 BST 插入方式，新节点初始为红色，然后根据红黑性质进行修复：
- 如果父节点是黑色，无需处理
- 如果父节点是红色，检查叔叔节点颜色
- 通过变色和旋转（左旋/右旋）恢复平衡
主要分三种情况处理：
void fixInsert(Node* node) {
while (node != root && node->parent->color == RED) {
if (node->parent == node->parent->parent->left) {
Node* uncle = node->parent->parent->right;
if (uncle && uncle->color == RED) {
// 情况1：叔叔为红，变色
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
// 情况2：叔叔为黑，LR 或 LL 型
if (node == node->parent->right) {
node = node->parent;
leftRotate(node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rightRotate(node->parent->parent);
}
} else {
// 对称处理右子树
...
}
}
root->color = BLACK; // 根始终为黑
}
旋转操作实现
旋转用于调整树形结构，保持 BST 性质同时恢复红黑约束：
- 左旋：以 x 为轴，x 的右孩子 y 上提，y 的左子树变为 x 的右子树
- 右旋：以 y 为轴，y 的左孩子 x 上提，x 的右子树变为 y 的左子树
void leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left) y->left->parent = x;
y->parent = x->parent;
if (!x->parent) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
}
删除操作与修复
删除比插入复杂。先按 BST 删除节点：
- 若被删节点是红色，直接删除不影响黑高
- 若是黑色，可能破坏黑高，需修复
- 修复过程考虑兄弟节点颜色及其子节点情况
通过变色、旋转逐步恢复性质，代码较长但逻辑清晰。
基本上就这些。实现红黑树关键是理解五条性质如何在每次修改后维护。虽然代码量大，但模块化设计（如分离旋转、修复函数）可提升可读性和正确性。调试时建议从小数据测试，配合打印树结构验证平衡性。
