红黑树从概念到手撕实现：平衡树的工程取舍与核心逻辑

插入完成后，要把根节点重新改成黑色，防止处理插入问题时颜色被改了导致根节点变红。

核心代码如下，我会在注释中解释三种主要情况的处理策略：

template<class K, class V>
struct RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    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;
            
            // 情况 A: 叔叔节点存在且为红
            if (parent == grandfather->_left) {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED) {
                    // 变色：p 和 u 变黑，g 变红
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续向上处理，cur 变为 g
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    // 情况 B/C: 叔叔不存在或为黑，需旋转
                    if (cur == parent->_left) {
                        // 左左型：右旋 g，变色
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        // 左右型：先左旋 p，再右旋 g
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            } else {
                // 对称情况：parent 是 grandfather 的右孩子
                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) {
                        // 右右型：左旋 g，变色
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    } else {
                        // 右左型：先右旋 p，再左旋 g
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK; // 确保根节点始终为黑色
        return true;
    }

private:
    Node* _root = nullptr;
    // 此处省略 RotateL/RotateR 的具体实现，逻辑同 AVL 树
};

插入新节点的处理逻辑

这个处理的前提是插入的节点要先设置成红色的。我们约定：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。

• 情况一：cur 为红，p 为红，g 为黑，u 存在且为红。

  • 解决方法：把 p, u 改为黑，g 改为红，然后把 g 当作 cur，继续向上调整。这相当于把冲突向上传递。

• 情况二：cur 为红，p 为红，g 为黑，u 不存在或 u 存在且为黑（直线型）。

  • 若 p 为 g 的左孩子，cur 为 p 的左孩子时，进行右旋，然后让 p 变黑，g 变红。
  • 若 p 为 g 的右孩子，cur 为 p 的右孩子时，则进行左旋，然后让 p 变黑，g 变红。
  • 这里的旋转是 c p g 进行，没有 u 参与，怎么旋转可以参考 AVL 树，一模一样。

• 情况三：cur 为红，p 为红，g 为黑，u 不存在或 u 存在且为黑（折线型）。

  • 若 p 为 g 的左孩子，cur 为 p 的右孩子时，则做左旋。
  • 若 p 为 g 的右孩子，cur 为 p 的左孩子时，则做右旋。
  • 这里的旋转是 c p g 进行，做完后就转换成情况二了。

红黑树的验证

写完后怎么验证自己的红黑树没写错？最主要是验证有没有连续红节点、每条路径的黑节点个数是不是一样多，以及根节点是不是黑色的。

不要去单独用最短路径和最长路径的关系来判断是不是红黑树，制约不够的。检查有无连续红节点的时候，检查该节点的孩子颜色太麻烦了，不如检查父亲的颜色。

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(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);
}

知识自测

关于 AVL 树和红黑树的区别说法不正确的是（C）

A. AVL 树和红黑树保证平衡性的方式不同 B. AVL 树和红黑树都是平衡树，因此查找的时间复杂度都是 O(logN) C. AVL 树和红黑树的性质遭到破坏时，都需要进行旋转 // 红黑树有时不需要旋转（如变色即可） D. AVL 树和红黑树中序遍历都可以得到有序序列，因为它们都是二叉搜索树