红黑树通过五个核心性质维持平衡，插入新节点后若违反性质，需要通过变色和旋转修复。插入的新节点默认设为红色，避免破坏黑色节点数量平衡的性质，仅在父节点为红色时才需要调整。
红黑树插入调整的核心规则
当插入节点的父节点是红色时，会违反红黑树性质，此时需要根据叔叔节点的颜色分情况处理：
- 若叔叔节点为红色，通过变色处理，将父节点和叔叔节点变黑，祖父节点变红，再将祖父节点作为新的插入节点向上递归调整
- 若叔叔节点为黑色或不存在，需要通过旋转结合变色处理，旋转分为左旋和右旋两种操作
旋转操作的C++实现
旋转操作是调整树结构的基础，左旋是将当前节点的右子节点提升为父节点，右旋是将当前节点的左子节点提升为父节点，具体实现如下：
// 红黑树节点定义
template <typename T>
struct RBNode {
T val;
RBNode* left;
RBNode* right;
RBNode* parent;
bool isRed; // true表示红色，false表示黑色
RBNode(T v) : val(v), left(nullptr), right(nullptr), parent(nullptr), isRed(true) {}
};
// 左旋操作
template <typename T>
void leftRotate(RBNode<T>* &root, RBNode<T>* x) {
RBNode<T>* 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;
}
// 右旋操作
template <typename T>
void rightRotate(RBNode<T>* &root, RBNode<T>* y) {
RBNode<T>* 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;
}
插入后的调整逻辑实现
插入新节点后，从新节点向上遍历，遇到父节点为红色的情况就执行调整，直到父节点为黑色或到达根节点，调整完成后将根节点设为黑色：
// 插入后调整平衡
template <typename T>
void fixInsert(RBNode<T>* &root, RBNode<T>* node) {
while (node->parent != nullptr && node->parent->isRed) {
// 父节点是祖父节点的左子节点
if (node->parent == node->parent->parent->left) {
RBNode<T>* uncle = node->parent->parent->right;
// 情况1：叔叔节点为红色，变色处理
if (uncle != nullptr && uncle->isRed) {
node->parent->isRed = false;
uncle->isRed = false;
node->parent->parent->isRed = true;
node = node->parent->parent;
} else {
// 情况2：当前节点是父节点的右子节点，先左旋
if (node == node->parent->right) {
node = node->parent;
leftRotate(root, node);
}
// 情况3：变色后右旋
node->parent->isRed = false;
node->parent->parent->isRed = true;
rightRotate(root, node->parent->parent);
}
} else { // 父节点是祖父节点的右子节点，对称处理
RBNode<T>* uncle = node->parent->parent->left;
if (uncle != nullptr && uncle->isRed) {
node->parent->isRed = false;
uncle->isRed = false;
node->parent->parent->isRed = true;
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
rightRotate(root, node);
}
node->parent->isRed = false;
node->parent->parent->isRed = true;
leftRotate(root, node->parent->parent);
}
}
}
// 根节点始终为黑色
root->isRed = false;
}
完整插入逻辑封装
结合节点插入和调整逻辑，完整的红黑树插入函数实现如下：
// 红黑树插入函数
template <typename T>
void rbInsert(RBNode<T>* &root, T val) {
RBNode<T>* newNode = new RBNode<T>(val);
RBNode<T>* curr = root;
RBNode<T>* parent = nullptr;
// 找到插入位置
while (curr != nullptr) {
parent = curr;
if (val < curr->val) {
curr = curr->left;
} else {
curr = curr->right;
}
}
newNode->parent = parent;
if (parent == nullptr) {
root = newNode;
} else if (val < parent->val) {
parent->left = newNode;
} else {
parent->right = newNode;
}
// 调整平衡
fixInsert(root, newNode);
}
常见场景验证
以插入序列10、20、30为例，插入10后根节点为10红色，插入20后20为10的右子红色，插入30时父节点20为红色，叔叔节点不存在（黑色），触发左旋+变色：先对20左旋，再将10变黑、20变红、30变黑，最终根节点为20黑色，左右子为10和30红色，符合红黑树性质。