红黑树插入后必须变色或旋转以修复被破坏的性质：新节点涂红可能导致双红冲突，需通过变色（不改变树高）或旋转（调整结构）解决，具体分四种case处理，依赖叔节点颜色与节点位置关系。
红黑树插入后为什么必须变色或旋转
因为直接插入新节点会破坏红黑树的 5 条性质，尤其是「任意路径上黑节点数相同」和「不能有两个连续的红节点」这两条。新节点默认涂红，若父节点也是红的，就触发了「双红冲突」，必须通过 rotate_left、rotate_right 或重新着色来修复。
关键点在于：变色不改变树高，开销小；旋转会改变局部结构，但能打破双红链。两者常组合使用（比如先变色再旋转），具体走哪条路径，取决于叔节点颜色和新节点在父节点中的左右位置。
四种插入修复 case 怎么对应操作
假设当前插入节点为 z，其父节点为 z->parent，祖父为 z->parent->parent，叔节点为 uncle（即祖父另一子节点）。所有修复都基于这三者颜色和相对位置判断：
- case 1：叔节点
uncle是红色 → 只需变色：uncle和z->parent涂黑，z->parent->parent涂红；然后把z上移到祖父，继续向上检查 - case 2：叔节点是黑色，且
z是父节点的右孩子，父节点是祖父的左孩子 → 先rotate_left(z->parent)，把问题转成 case 3 - case 3：叔节点是黑色，且
z是父节点的左孩子，父节点是祖父的左孩子 →rotate_right(z->parent->parent)，再交换父与祖父颜色 - case 4：和 case 2/3 对称（父为右、z 为左 → 先
rotate_right；父为右、z 为右 → 直接rotate_left）
注意：case 2 和 case 4 是「内侧插入」，必须先转成「外侧插入」（case 3 / case 4 对称形式）才能单次旋转修复。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
rotate_left 和 rotate_right 的核心指针操作
旋转本身不涉及颜色修改，只重连三个节点的父子关系。以 rotate_left(x) 为例（x 为旋转支点，x->right 必须非空）：
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;同理，rotate_right(y) 是镜像操作。漏掉 parent 指针更新、或忘记处理 root 变更，会导致树断裂或遍历时崩溃。
实际编码中最容易忽略的细节
不是所有实现都显式维护 parent 指针，但红黑树修复必须知道祖父和叔节点，所以必须带父指针；另外几个高频坑：
- 没检查
z->parent是否为空（即 z 是根）就访问z->parent->parent，导致段错误 - 变色时把
nullptr当作节点去读写color字段（应确保指针非空再操作） - 旋转后忘记更新被旋转节点的
parent，后续变色或继续修复时用错上下文 - case 1 中上移
z后未重算uncle，导致判断逻辑错乱
真正的难点不在旋转公式，而在于边界条件全覆盖 —— 每次指针解引用前，都要想清楚它是否可能为 nullptr。
