红黑树从概念到手撕实现：平衡树的折中智慧

前言

学完 AVL 树，很多人会有个疑问：既然 AVL 树是'严格平衡'的二叉搜索树，查询效率理论上更高，为什么 C++ STL 的 map/set、Linux 内核里的关键结构偏偏选红黑树？难道'更平衡'反而成了缺点？

其实答案藏在工程取舍里。红黑树的精髓，从来不是比 AVL 树更平衡，而是在'查询效率'和'写入开销'之间找最优解。它不像 AVL 树那样追求极致的矮，而是用'近似平衡'（最长路径不超过最短路径 2 倍）的规则，换来了插入删除时更少的旋转和更低的空间开销。这刚好适配了工程中读写频繁、追求均衡性能的大多数场景。

本文将直接切入核心，从红黑树的 5 条性质讲起，拆解新节点为何默认红色、插入时三种情况如何处理等经典难点，再对比 AVL 树说清选型逻辑，最后附上可运行的手撕代码和验证逻辑。不管是为了面试手撕，还是搞懂底层原理，这篇都能帮你把红黑树的本质嚼透。

红黑树的概念

红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位表示结点的颜色，可以是 Red 或 Black。

红黑树的性质

1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 任何路径没有连续的红节点。
4. 各路径黑节点的个数相同。
5. 每个叶子结点都是黑色的（此处的叶子结点指的是那个空结点）。

这些性质保证了红黑树的最长路径长度不超过最短路径长度的 2 倍。因为一红后面必会跟一黑，且各路径黑节点个数一致。

关于路径的定义：从根节点到空节点算一条路径（默认规则）。路径长度计算时，空节点不算，根节点要算上。

红黑树的增删查改时间复杂度也是 O(logN)，其中 N 是节点个数。空树也可以是红黑树。

AVL 树跟红黑树的比较

AVL 树和红黑树在查找时的性能处于同一量级。但 AVL 树在插入和删除时为了维持严格平衡，旋转次数较多。因此红黑树在各方面更加均衡，虽然不如 AVL 树在纯查找场景下极致，但综合性能更好。如果大量查找且写入极少，AVL 略优；否则红黑树更通用。

红黑树的模拟实现

节点定义与基础结构

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

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;
            if (parent == grandfather->_left) {
                Node* uncle = grandfather->_right;
                // 情况一：叔叔存在且为红
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    // 情况二/三：叔叔不存在或为黑
                    if (cur == parent->_left) {
                        // 直线型：右旋
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        // 折线型：先左旋父节点，再右旋祖父
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            } else {
                // parent == grandfather->_right
                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) {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    } else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK; // 防止变色把根节点也变色了
        return true;
    }
private:
    Node* _root = nullptr;
};

插入新节点的时候默认先设置成红色的。如果设为黑色，会违反第四点（每条路径黑节点数相同），调整难度比违反第三点（无连续红节点）更大。

插入新节点的处理细节

这个处理的前提是插入的节点要先设置成红色。新节点刚开始是 cur。

约定：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。 插入一个节点完成后，要把根节点重新改成黑色，怕处理插入问题时颜色被改了。

情况一：cur 为红，p 为红，g 为黑，u 存在且为红 解决方法：把 p, u 改为黑，g 改为红，然后把 g 当作 cur，继续向上调整。

情况二：cur 为红，p 为红，g 为黑，u 不存在/u 存在且为黑 (cur p g 直线)

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

情况三：cur 为红，p 为红，g 为黑，u 不存在/u 存在且为黑 (折线 p 在最左边)

• p 为 g 的左孩子，cur 为 p 的右孩子时，则做左旋。
• p 为 g 的右孩子，cur 为 p 的左孩子时，则做右旋。 这里的旋转是 c p g 进行，没有 u 参与。做完这一步就转换成情况 2 了。

红黑树的验证

也就是验证自己的红黑树写没写对。验证的话最主要是验证有没有连续红节点、每条路径的黑节点个数是不是一样多以及根节点是不是黑色的。不要去单独用最短路径和最长路径的关系来判断是不是红黑树，制约不够的。

验证有无连续红节点的时候，检查该节点的孩子颜色太麻烦了，不如检查父亲的颜色。

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 树和红黑树中序遍历都可以得到有序序列，因为它们都是二叉搜索树