C++ 红黑树：插入与平衡修复的直观理解

红黑树是自平衡二叉查找树的一种，通过节点颜色和旋转维持近似平衡。实际用起来比 AVL 树省旋转，插入删除更轻量。

概念与性质

一棵合格的红黑树需要同时满足：

• 每个节点要么红要么黑。
• 根节点是黑色。
• 红色节点的两个子节点必须黑色（没有连续红）。
• 从任意节点到其后代所有叶子节点的简单路径上，黑色节点数量相同。
• 叶子节点（空节点）视为黑色。

这些规则共同保证了树的高度不会超过 2log(n+1)，也就是最长路径不会超过最短路径的两倍。直观理解：最短路径全黑，最长路径红黑交替。由于黑色节点数相等，红节点最多和黑节点一样多，所以最长路径最多是黑节点数的两倍，也就是最短路径的两倍。

节点结构及默认红色

enum Colour { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {}
};

新节点默认染成红色，主要是为了减少对黑色路径计数的影响。如果插个黑节点，必然破坏'同路径黑节点数相等'的性质，修复起来很麻烦。红色节点只可能造成'连续红'冲突，处理起来大多只需变色或加少量旋转，调整成本更低。

插入过程

插入操作分为标准的 BST 插入和随后的红黑性质修复。

typedef RBTreeNode<K, V> Node;

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }

    cur = new Node(kv);
    cur->_col = RED;
    if (parent->_kv.first < kv.first) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    cur->_parent = parent;

    // 修复红黑树性质
    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        
        if (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            
            if (uncle && uncle->_col == RED) {
                // 情况1：叔叔红色 -> 变色上推
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况2/3：叔叔黑或无
                if (cur == parent->_left) {
                    // LL型，右旋祖父
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    // LR型，先左旋父再右旋祖父
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            
            if (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                if (cur == parent->_right) {
                    // RR型
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                } else {
                    // RL型
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

插入后的修复循环围绕 parent 节点展开，只要父节点是红色就继续。核心在于区分叔叔节点的颜色：叔叔为红时，变色并把问题上移；叔叔为黑或不存在时，需要通过旋转调整父子祖三代的相对位置，并重新染色，调整后即可跳出循环。旋转的左右选择取决于从祖父到父再到当前节点的路径形状，画一下图会更直观——这也是实现红黑树时最需要细心的地方。

删除简述

红黑树的删除比插入复杂得多，这里不展开。如果真要用到，建议直接参考《算法导论》或成熟的库实现。

与 AVL 树的取舍

红黑树和 AVL 树都是自平衡二叉搜索树，但设计目标有差别。AVL 追求严格的平衡，每次插入删除后的旋转次数可能很多，适合读多写少的场景。红黑树允许稍微倾斜，换来更少的旋转开销，写入效率更高。实际工程中（比如 C++ STL 的 map、set）普遍使用红黑树，因为通用场景下写操作并不罕见。

验证代码

调试时自己写两个检查很管用：一个查有没有连续红节点，一个查每条路径的黑色节点数是否相等。

bool CheckColour(Node* root, int blacknum, int benchmark) {
    if (root == nullptr) {
        if (blacknum != benchmark)
            return false;
        return true;
    }
    if (root->_col == BLACK) {
        ++blacknum;
    }
    if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
        cout << root->_kv.first << "出现连续红色节点" << endl;
        return false;
    }
    return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark);
}

bool IsBalance() {
    return IsBalance(_root);
}

bool IsBalance(Node* root) {
    if (root == nullptr)
        return true;
    if (root->_col != BLACK) {
        return false;
    }
    int benchmark = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == BLACK)
            ++benchmark;
        cur = cur->_left;
    }
    return CheckColour(root, 0, benchmark);
}

这两个函数组合使用就能快速定位插入/删除逻辑中的错误。个人经验是先把插入代码写完，然后用随机数据跑一遍，再调用 IsBalance() 检查，能省不少 debug 时间。

文章到这里主要讲了插入和验证，删除部分确实复杂，但理解插入的修复模式后，再去看删除会有帮助。

![图示：红黑树结构示意]