红黑树插入后必须变色或旋转以恢复三条被破坏的性质：根为黑、无连续红节点、各路径黑高相同；变色用于处理“红-红-红”结构，旋转用于父红叔黑时的直线或折线情形，并需手动调色保黑高。
红黑树插入后为什么必须变色或旋转？
因为红黑树的 5 条性质中，root 必须是黑色、红色节点不能连续（red node's children must be black）、从任一节点到其所有叶子的路径上黑色节点数相同（black-height 不变），这三条在插入一个红色新节点后最容易被破坏。插入本身只违反「红色节点不能有红色子节点」和可能违反「根为黑」，所以修复逻辑全部围绕这两个点展开——不是为了“好看”，而是为了快速恢复性质。
插入后变色的触发条件与边界情况
变色（recolor）只发生在：当前节点 z、父节点 z->parent、叔节点 z->parent->parent->left/right 全为红色，且祖父节点非空。此时三者构成「红-红-红」局部结构，只需将父和叔改为黑、祖父改为红，就能暂时消除连续红链，同时保持子树黑高不变。
- 如果祖父是根节点，变色后需额外把根设为黑色（否则违反性质2）
- 如果祖父有父节点（即祖父非根），变色后需把祖父当作新插入的红色节点，向上递归检查——这是迭代修复的关键，不是递归调用函数，而是用
while循环重置z指针 - 叔节点为
nullptr时，不满足变色前提，直接进入旋转分支
左旋与右旋的判断依据和实现要点
旋转只在「变色不可行」时发生，核心判断是：父节点为红、叔节点为黑（或 nullptr），且当前节点与父节点、祖父节点形成「折线」或「直线」。具体：
-
直线型：比如
z是z->parent的左孩子，z->parent又是z->parent->parent的左孩子 → 触发right_rotate(z->parent->parent) -
折线型：比如
z是左孩子，但z->parent是右孩子 → 先对z->parent左旋，再对原祖父右旋（等价于把折线“拉直”） - 旋转操作本身不改变节点颜色，旋转后必须手动把原父节点染黑、原祖父染红——这是保证黑高不变的关键一步
void RBTree::left_rotate(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;
}
容易被忽略的细节：NULL 节点怎么处理？
标准红黑树实现中，叶子节点是「哨兵节点」（NIL），类型为 Node*，颜色固定为黑，且所有空指针（left/right == nullptr）都应视为指向同一个全局 NIL 节点。如果直接用 nullptr 判断颜色，会出错——因为 nullptr->color 非法。正确做法是：
立即学习“C++免费学习笔记（深入）”；
- 定义静态常量
static const Node* const NIL，初始化为 new Node{BLACK, nullptr, nullptr, nullptr} - 所有叶节点指针（
left/right）默认指向NIL，而非nullptr - 插入新节点时，其
left和right必须显式设为NIL，不能留空
漏掉这点，变色逻辑里对 uncle->color 的访问就会崩溃，或者导致黑高计算错误。
