红黑树是一种自平衡二叉查找树，它通过给每个节点标记红色或黑色，并配合一组严格的性质，在插入和删除操作后使用变色与旋转来恢复平衡。与AVL树追求严格高度平衡不同，红黑树只保证从根到叶子的最长路径不超过最短路径的两倍，因此旋转次数更少，适合频繁写操作的场景。要真正理解它的平衡机制，必须弄清楚节点颜色变化和左右旋转分别在什么条件下触发，以及它们如何协作修复被破坏的性质。
红黑树的五条核心性质
红黑树之所以能保持近似平衡，依赖以下五条性质：每个节点要么是红色，要么是黑色；根节点永远是黑色；所有叶子节点（空节点NIL）视为黑色；红色节点的两个子节点都必须为黑色，也就是不能出现连续的红色节点；从任一节点出发到其所有后代叶子节点的路径上，包含的黑色节点数量相同，这个数量称为黑高。
这五条性质中，第四条和第五条是插入修复的重点。当我们插入一个红色节点时，可能不会破坏黑高，但容易破坏红色不连续规则；而当我们为了修复红色连续去做旋转并重新染色时，又必须小心不要改变黑高。理解这一点，就能明白为什么红黑树的平衡过程看起来比AVL树更绕，却更高效。
插入场景下的节点变色原理
新插入的节点通常先染成红色，因为插入红节点不会增加黑高，只可能违反红色不连续性质。假设父节点也是红色，这时就需要看叔叔节点（父节点的兄弟）的颜色。如果叔叔是红色，说明祖父的两个子子树黑高一致且都带红，此时最简单的做法是把父和叔叔都变黑，祖父变红，这样局部黑高不变，红色不连续也修复了，但祖父变红可能向上传递冲突，所以要继续向上检查。
下面的代码展示了简化版的叔叔为红时的变色逻辑：
// 假设 node 为新插入的红节点，parent 为父，uncle 为叔，grand 为祖父
if (parent.color == RED && uncle != null && uncle.color == RED) {
parent.color = BLACK; // 父变黑
uncle.color = BLACK; // 叔变黑
grand.color = RED; // 祖父变红
node = grand; // 继续向上检查祖父是否违反规则
}
这种纯变色操作没有改动树的结构，因此效率极高。但它的前提是叔叔为红，也就是祖父的另一侧子树同样有冗余的红色，可以通过对称染色吸收冲突。如果叔叔是黑色或不存在，变色就无法在不破坏黑高的前提下解决问题，此时必须引入旋转。
旋转操作如何重构局部结构
旋转分为左旋和右旋，本质是把某个节点下沉、其子节点上升，从而改变子树高度分布。以左旋为例，当节点X的右子Y替代X的位置，Y的左子变成X的右子，X成为Y的左子。右旋则完全对称。旋转之后通常会配合重新染色，使红色不连续且黑高维持。
当叔叔为黑且父为红时，若新节点与父、祖父形成直线（例如父是祖父左子，新节点是父左子），只需以祖父为轴做一次右旋，并把原父变黑、原祖父变红即可。若形成折线（父左子，新节点右子），则先对父左旋转为直线，再对祖父右旋。下面给出左旋的基础实现：
// 对节点x进行左旋，y为x的右孩子
void leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
旋转的价值在于它能把偏斜的路径拉平。变色解决的是颜色冲突，旋转解决的是结构偏斜。两者结合，使红黑树在最多两次旋转内完成插入修复。实际工程中如TreeMap的put方法，就是按上述叔叔颜色与折线直线关系来决定调用rotateLeft还是rotateRight。
删除场景中的平衡修复差异
删除比插入更复杂，因为删除黑节点会直接减少黑高。若删去的是红节点，直接移除不影响性质；若删去黑节点，则需要通过变色、旋转，甚至从兄弟子树借调黑色来补全黑高。常见策略是当兄弟为红时先对父旋转使兄弟变黑，再按兄弟子节点颜色决定后续操作。
例如兄弟为黑且远侄红，则通过父旋转加染色一次性修复；兄弟为黑且近侄红，则先兄弟旋转转化场景。下面用伪代码说明删除后兄弟为黑且两侄皆黑的情形：
// node为双黑上浮的当前节点，sibling为其兄弟
if (sibling.color == BLACK && s_left.color == BLACK && s_right.color == BLACK) {
sibling.color = RED; // 兄弟变红以吸收黑高差
node = node.parent; // 向上传递双黑
} else {
// 其他情况结合旋转处理
}
可以看出，删除修复同样遵循先尝试变色、不行再旋转的思路，但由于黑高受损，向上传递的概率更高。理解插入的变色与旋转逻辑，是看懂删除修复的基础，因为二者使用的工具和性质约束完全一致。
为什么红黑树选择变色优先于旋转
从性能角度看，变色只是修改几个标志位，时间复杂度是常量且不会触碰内存布局；旋转则要修改多个指针并可能影响缓存局部性。红黑树设计哲学是能用颜色解决的平衡问题就绝不旋转，只有在结构确实倾斜时才旋转。这也是它相比AVL树在数据库索引、语言标准库有序映射中更受欢迎的原因。
当我们阅读JDK或Linux源码时，经常看到fixAfterInsertion、rb_erase这类函数，其内部就是按照叔叔颜色、父子方位的有限状态机来执行recolor或rotate。掌握了变量节点变色与旋转的触发条件，就能在调试时快速判断某次树重整是否符合预期，而不是被层层递归绕晕。
red_black_treenode_recoloringtree_rotation修改时间：2026-08-09 11:57:39