红黑树插入后必须变色或旋转以恢复三条被破坏的性质：根为黑、无连续红节点、各路径黑高相同；变色用于处理“红-红-红”结构，旋转用于父红叔黑时的直线或折线情形，并需手动调色保黑高。

红黑树插入后为什么必须变色或旋转？

因为红黑树的 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 的访问就会崩溃，或者导致黑高计算错误。