71、实战：红黑树模拟（插入+旋转+颜色调整）

红黑树，说实话，是很多C++工程师的噩梦。我记得刚入行那会儿，面试官让我手写红黑树插入，我直接懵了。后来在项目中真的遇到了——一个高频交易系统需要稳定的O(log n)插入和查找，STL的map底层就是红黑树，但你要自己定制节点行为时，就必须自己撸一个。

今天我们就来手撕红黑树的插入操作，包括左旋、右旋和颜色调整。我会把我在项目中踩过的坑一并告诉你。

红黑树的五大规则

先过一遍规则，不然代码你根本看不懂。

1. 每个节点要么红，要么黑。
2. 根节点是黑的。
3. 叶子节点（NIL）是黑的。
4. 红色节点的子节点必须是黑的。（不能有两个连续红节点）
5. 从任一节点到其每个叶子的所有路径，包含相同数量的黑节点。

嗯，第4条和第5条是调整的核心。你想想看，插入一个红色节点，最多只破坏第4条。如果插入黑色节点，第5条就全乱了，所以新节点一律先涂红。

插入操作的核心流程

插入分三步走：

1. 像普通BST一样插入节点，颜色设为红色。
2. 检查是否违反红黑树规则。
3. 如果违反，通过旋转和变色来修复。

修复过程有6种情况（对称的算两种），我习惯把它们分成三组：

情况	描述	处理方式
情况1	叔叔节点是红色	变色：父、叔变黑，祖父变红，向上递归
情况2	叔叔是黑色，且当前节点是内侧插入	先旋转父节点，变成情况3
情况3	叔叔是黑色，且当前节点是外侧插入	旋转祖父节点，变色

说白了，情况1靠变色解决，情况2和3靠旋转解决。旋转分左旋和右旋，是对称操作。

左旋和右旋的实现

旋转不改变BST的性质，只改变树的结构。我项目中遇到过最坑的事——旋转时忘了更新父节点的指针，导致整棵树断链。调试了一下午才发现。

// 左旋：以x为轴，将x的右子节点y旋转上来
void leftRotate(Node* x) {
    Node* y = x->right;   // y是x的右孩子
    x->right = y->left;   // y的左孩子过继给x的右子树
    
    if (y->left != nullptr)
        y->left->parent = x;
    
    y->parent = x->parent; // y的父指针指向x的父
    
    if (x->parent == nullptr)
        root = y;          // x是根，y成为新根
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    
    y->left = x;           // x成为y的左孩子
    x->parent = y;
}

右旋就是对称的，把left和right互换就行。我建议你写的时候直接复制左旋，然后全局替换left和right，不容易出错。

插入修复的完整代码

这是最核心的部分。我曾经在修复循环里忘了更新当前节点指针，导致死循环，CPU直接飙到100%。

void insertFixup(Node* z) {
    while (z->parent != nullptr && z->parent->color == RED) {
        // 父节点是祖父的左孩子
        if (z->parent == z->parent->parent->left) {
            Node* y = z->parent->parent->right; // 叔叔节点
            
            // 情况1：叔叔是红色
            if (y != nullptr && y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent; // 向上递归
            } else {
                // 情况2：叔叔是黑色，且z是右孩子（内侧）
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(z); // 左旋变成情况3
                }
                // 情况3：叔叔是黑色，且z是左孩子（外侧）
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(z->parent->parent);
            }
        } else {
            // 对称情况：父节点是祖父的右孩子
            // 把上面的left和right互换，叔叔变成左孩子
            // 代码结构完全对称，这里省略
        }
    }
    root->color = BLACK; // 确保根是黑色
}

红黑树插入的完整流程

下面这张图展示了插入一个新节点后，整个修复流程的决策路径。我画图时特意把对称情况合并了，方便你理解。

实战中的避坑指南

我曾经在一个项目里，红黑树插入后颜色调整写错了，导致树的高度退化成链表。查找操作从O(log n)变成了O(n)，线上服务直接超时。排查了整整两天才发现是叔叔节点判断时忘了处理nullptr。

另外，我建议你写一个验证函数，检查红黑树的五条规则是否都满足。每次插入后调用一下，能帮你快速定位问题。

bool validateRBTree(Node* node, int blackCount, int& pathBlackCount) {
    if (node == nullptr) {
        // 叶子节点，检查黑色节点数量
        if (pathBlackCount == -1) {
            pathBlackCount = blackCount;
        } else if (pathBlackCount != blackCount) {
            return false; // 违反规则5
        }
        return true;
    }
    
    // 检查规则4：红色节点的子节点不能是红色
    if (node->color == RED) {
        if (node->left != nullptr && node->left->color == RED)
            return false;
        if (node->right != nullptr && node->right->color == RED)
            return false;
    }
    
    // 统计黑色节点
    int add = (node->color == BLACK) ? 1 : 0;
    return validateRBTree(node->left, blackCount + add, pathBlackCount) &&
           validateRBTree(node->right, blackCount + add, pathBlackCount);
}

嗯，这个验证函数我每次写完红黑树都会跑一遍。说白了，红黑树的难点不在旋转，而在边界条件的处理。你想想看，根节点、叶子节点、叔叔节点为nullptr的情况，每个都要单独处理。

最后说一句，红黑树的删除比插入复杂得多，但掌握了插入，删除就是同样的套路——先BST删除，再修复颜色。我建议你先把这个插入练熟，再挑战删除。