红黑树通过颜色规则和旋转维持平衡，确保操作时间复杂度为O(log n)。其节点含颜色、值及指针，新节点默认红色。左旋右旋调整结构，插入后按叔叔颜色等分情况修复，最终根节点染黑以满足性质。
红黑树是一种自平衡的二叉查找树，它通过特定的颜色规则和旋转操作保证树的高度接近 log(n)，从而确保插入、删除和查找操作的时间复杂度为 O(log n)。在 C++ 中实现红黑树，需要理解其基本性质，并通过指针操作维护这些性质。
红黑树的五条基本性质
为了保持平衡，红黑树中的每个节点都带有颜色（红色或黑色），并满足以下条件：
- 每个节点是红色或黑色
- 根节点是黑色
- 所有叶子（NULL 节点）视为黑色
- 如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高一致）
节点结构设计
定义一个红黑树节点类，包含值、颜色、左右子节点和父节点指针。使用枚举表示颜色更清晰。
enum Color { RED, BLACK };
struct Node {
int data;
Color color;
Node left, right, *parent;
Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};
注意：新插入节点默认为红色，这样可以最小化对黑高性质的影响。
左旋与右旋操作
旋转是维持红黑树平衡的核心操作。左旋用于处理右倾情况，右旋处理左倾。
左旋示例：
void leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != nullptr)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == nullptr)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
右旋类似，交换 left 和 right 的角色即可。
插入操作与修复
插入过程分为两步：按二叉搜索树方式插入，然后根据红黑性质进行修复。
修复主要处理三种情况：
- 叔叔是红色：变色并上移问题节点
- 叔叔是黑色且当前节点是右孩子：左旋调整形态
- 叔叔是黑色且当前节点是左孩子：右旋并重新着色
修复函数大致如下：
void insertFix(Node* k) {
while (k != root && k->parent->color == RED) {
if (k->parent == k->parent->parent->left) {
Node* u = k->parent->parent->right;
if (u != nullptr && u->color == RED) {
k->parent->color = BLACK;
u->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->right) {
k = k->parent;
leftRotate(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rightRotate(k->parent->parent);
}
} else {
// 对称情况
}
}
root->color = BLACK;
}
完整实现要点
一个完整的红黑树类应包括：
- 私有成员：root 指针
- 公共方法：insert(int)、remove(int)、search(int)
- 辅助方法：rotateLeft、rotateRight、fixInsert、fixDelete
删除比插入更复杂，涉及更多情况判断，核心思路是将删除黑色节点引起的问题沿路径向上修复。
基本上就这些。实现红黑树的关键在于理解每种旋转和变色背后的逻辑——都是为了恢复那五条性质。虽然代码量较大，但只要分步处理，逐步调试，就能构建出稳定的结构。
