红黑树通过颜色属性和旋转操作维持平衡，确保插入删除后仍满足二叉搜索树性质且黑高一致，最长路径不超过最短路径两倍，从而保证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，辅助调试。
基本上就这些。红黑树实现关键是理解各种插入/删除场景下的修复策略，结合旋转与着色操作逐步恢复平衡。虽然代码量较大，但逻辑清晰，适合深入学习自平衡树的设计思想。