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

引言

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

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

这篇内容不绕弯子，直接从红黑树的 5 条核心性质讲起，拆透'新节点为啥默认红色''插入时 3 种情况怎么处理'这些经典难点，再对比 AVL 树说清'什么时候该选谁'，最后附上可运行的手撕代码和验证逻辑。

红黑树的概念

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

红黑树的性质

为了保证平衡性，红黑树必须满足以下 5 条规则：

1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 任何路径没有连续的红节点（即红节点的子节点必须是黑色）。
4. 各路径黑节点的个数相同（即从任一节点到其所有叶子节点的路径上，黑色节点数量相等）。
5. 每个叶子结点都是黑色的（此处的叶子结点指的是那个空结点，通常称为 NIL 节点）。

关于路径：从根节点到空节点算一条路径。路径长度计算时，空节点不算，根节点要算。

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

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

AVL 树跟红黑树的比较

AVL 树和红黑树在查找时的性能是同一量级的，但两者的侧重点不同：

• AVL 树：平衡控制非常严格，插入和删除时的旋转次数很多。适合大量查找、少量修改的场景。
• 红黑树：平衡控制相对宽松，旋转次数少。虽然查找性能略逊于 AVL，但在各方面更加均衡，更适合频繁修改的场景。

红黑树的模拟实现

下面我们用 C++ 来实现一个红黑树。为了清晰起见，我们将结构体定义和核心逻辑分开展示。

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

2. 插入逻辑详解

插入新节点的时候，默认先设置成红色的。如果设置为黑色，会违反第 4 条性质（黑高一致），调整难度更大；而设置为红色只可能违反第 3 条性质（连续红节点），更容易通过变色或旋转修复。

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

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

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