红黑树在插入节点后若父节点为红色，就会破坏性质出现双红冲突。修复依赖叔叔节点颜色与位置，通过变色和旋转让树重新满足红黑规则。下面用C++代码说明核心处理过程。
红黑树节点与基本定义
先给出节点结构与颜色枚举，方便后续算法描述。
enum Color { RED, BLACK };
struct RBNode {
int key;
Color color;
RBNode* left;
RBNode* right;
RBNode* parent;
RBNode(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
双红冲突修复逻辑
当插入节点为红且父节点也为红时，根据叔叔节点情况处理。叔叔红则变色，叔叔黑则旋转加变色。
叔叔为红时的变色
将父、叔叔变黑，祖父变红，再把祖父当作当前节点向上检查。
void fix_uncle_red(RBNode*& root, RBNode*& cur) {
RBNode* parent = cur->parent;
RBNode* grand = parent->parent;
RBNode* uncle = (grand->left == parent) ? grand->right : grand->left;
parent->color = BLACK;
uncle->color = BLACK;
grand->color = RED;
cur = grand;
}
叔叔为黑时的旋转与变色
若当前节点与父节点不在同一侧，先对父节点旋转使其同侧，再对祖父旋转并变色。
void left_rotate(RBNode*& root, RBNode* x) {
RBNode* 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->parent->left == x) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
}
void right_rotate(RBNode*& root, RBNode* x) {
RBNode* y = x->left;
x->left = y->right;
if (y->right) y->right->parent = x;
y->parent = x->parent;
if (!x->parent) root = y;
else if (x->parent->right == x) x->parent->right = y;
else x->parent->left = y;
y->right = x;
x->parent = y;
}
void fix_uncle_black(RBNode*& root, RBNode*& cur) {
RBNode* parent = cur->parent;
RBNode* grand = parent->parent;
if (grand->left == parent && parent->right == cur) {
left_rotate(root, parent);
cur = parent;
} else if (grand->right == parent && parent->left == cur) {
right_rotate(root, parent);
cur = parent;
}
parent = cur->parent;
grand = parent->parent;
parent->color = BLACK;
grand->color = RED;
if (grand->left == parent) right_rotate(root, grand);
else left_rotate(root, grand);
}
修复入口函数
插入后循环判断双红，分情况调用上述函数直到根或父为黑。
void fix_insert(RBNode*& root, RBNode* cur) {
while (cur->parent && cur->parent->color == RED) {
RBNode* parent = cur->parent;
RBNode* grand = parent->parent;
RBNode* uncle = (grand->left == parent) ? grand->right : grand->left;
if (uncle && uncle->color == RED) {
fix_uncle_red(root, cur);
} else {
fix_uncle_black(root, cur);
}
}
root->color = BLACK;
}
以上代码完整展示了C++中红黑树双红冲突修复的核心变色与旋转算法，实际使用时可结合插入查找逻辑构建完整容器。