红黑树通过颜色属性和旋转操作维持平衡，确保插入删除后仍满足二叉搜索树性质且黑高一致，最长路径不超过最短路径两倍，从而保证O(log n)时间复杂度。
红黑树是一种自平衡的二叉查找树，通过为每个节点添加颜色属性（红色或黑色）并遵循特定规则，保证树在插入和删除操作后依然大致保持平衡。C++中实现红黑树需要理解其结构定义、旋转操作、插入与删除的修复逻辑。
红黑树的性质
红黑树满足以下五条性质：
- 每个节点是红色或黑色
- 根节点是黑色
- 所有叶子节点（NULL指针）视为黑色
- 红色节点的子节点必须是黑色（不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高一致）
这些性质确保了最长路径不超过最短路径的两倍，从而维持O(log n)的操作复杂度。
节点结构定义
定义一个红黑树节点类，包含值、颜色、左右子节点和父节点指针：
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) {}};
注意新插入节点默认为红色，这样能最小化对黑高性质的影响。
旋转操作：维持平衡的基础
旋转是调整树结构而不破坏二叉搜索树性质的关键操作。红黑树需要左旋和右旋：
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;
}
void rightRotate(Node y) {
Node x = y->left;
y->left = x->right;
if (x->right != nullptr)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == nullptr)
root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
}
左旋将右孩子提升，右旋将左孩子提升，用于后续插入修复中调整结构。
插入操作与修复
插入按BST规则找到位置后插入红色节点，然后根据情况修复红黑性质：
void insert(int value) {
Node* node = new Node(value);
root = bstInsert(root, node); // 标准BST插入
fixInsert(node); // 修复红黑性质
}
修复分为几种情况：
- 父节点为黑色：无需处理
- 父节点为红色：检查叔节点颜色
- 叔节点为红色：变色并上移问题到祖父
- 叔节点为黑色：通过旋转+变色解决
具体修复代码会根据父节点是左孩子还是右孩子对称处理，核心是重新着色和旋转以恢复性质。
删除操作与修复
删除比插入更复杂。先执行标准BST删除，若删除的是黑色节点，可能导致黑高不一致，需修复。
修复从替代节点开始，分情况处理兄弟节点的颜色和结构，通过变色、旋转逐步向上修复。
由于篇幅较长，完整删除修复逻辑通常涉及多个case判断，建议参考经典算法教材如《算法导论》中的RB-DELETE-FIXUP过程实现。
基本操作接口设计
可封装成类提供清晰接口：
class RedBlackTree {
private:
Node* root;
void leftRotate(Node*);
void rightRotate(Node*);
void fixInsert(Node*);
void fixDelete(Node*);
Node* bstInsert(Node*, Node*);
public:
RedBlackTree() : root(nullptr) {}
void insert(int value);
void remove(int value);
Node* search(int value);
void inorder();
};
配合中序遍历可验证是否仍为有效BST，辅助调试。
基本上就这些。红黑树实现关键是理解各种插入/删除场景下的修复策略，结合旋转与着色操作逐步恢复平衡。虽然代码量较大，但逻辑清晰，适合深入学习自平衡树的设计思想。
