红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，在许多编程语言的底层库中都能看到它的身影，比如 C++ STL 的 std::map、std::set，Java 的 TreeMap、TreeSet。与 AVL 树相比，红黑树对平衡的要求不那么严格，但依然能保证最坏情况下的操作时间复杂度为 O(log⁡N)O(logN)。本文将从零开始，详细讲解红黑树的设计思想、规则、插入操作以及代码实现，帮助读者彻底理解这一经典数据结构。

一、红黑树的概念与规则

红黑树本质上是一棵二叉搜索树，每个结点额外存储一个颜色位（红色或黑色）。通过对颜色进行约束，红黑树保证任何一条从根到叶子（NULL）的路径不会比其他路径长出两倍，从而维持了近似平衡。

1.1 红黑树的四条规则

  1. 每个结点不是红色就是黑色。

  2. 根结点是黑色的。

  3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的（即不存在两个连续的红色结点）。

  4. 对于任意一个结点，从该结点到其所有后代 NULL 结点的简单路径上，均包含相同数量的黑色结点（这条规则也称为“黑色高度一致”）。

注：一些教材（如《算法导论》）会补充一条“每个叶子结点（NIL）都是黑色的”。这里的叶子结点指的是空结点（外部结点），引入 NIL 是为了统一路径的终点。在具体实现中，我们通常直接用 nullptr 表示空，只要逻辑上遵守规则即可。

1.2 为什么红黑树能保证“最长路径不超过最短路径的2倍”？

利用规则 4：每条路径上的黑色结点数相同，记这个数目为 bh（black height）。
利用规则 3：红色结点不能连续，所以一条路径上红色结点最多和黑色结点一样多（最坏情况就是一黑一红交替）。
因此，最短路径 = 全为黑色，长度为 bh；最长路径 = 黑红交替，长度为 2*bh。
于是最长路径 ≤ 2 × 最短路径。虽然实际存在的树不一定同时出现这两种极端路径，但这个上界保证了红黑树的高度始终在 O(log⁡N)O(logN) 级别。

1.3 红黑树的效率

设红黑树结点数为 N，黑色高度为 h，则有

2h−1≤N≤22h−12h−1≤N≤22h−1

因此 h≈log⁡Nh≈logN，树的高度约为 O(log⁡N)O(logN)。最坏情况下查找次数不超过 2log⁡N2logN，时间复杂度依然是 O(log⁡N)O(logN)。

与 AVL 树相比，红黑树的旋转次数更少，因为 AVL 树要求高度差严格 ≤1，而红黑树只要求近似平衡，所以插入和删除时平衡调整的频率较低。因此红黑树在插入删除频繁的场景下性能更优，这也是 STL 选择红黑树的原因之一。

二、红黑树的结点定义

我们采用 key-value 模型，并引入父指针（方便向上调整）和颜色枚举。

enum Colour
{
    RED,
    BLACK
};

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

    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(RED)      // 新结点默认为红色，原因见后文
    {}
};

树的结构体只包含根结点指针：

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    // 插入、查找等接口
private:
    Node* _root = nullptr;
};

三、插入操作详解

插入是红黑树最复杂的操作，分为几个阶段：BST 插入、颜色调整、旋转。
我们约定以下记号：

  • c（cur）：当前新插入的结点

  • p（parent）：c 的父结点

  • g（grandfather）：p 的父结点

  • u（uncle）：p 的兄弟结点

3.1 插入流程概览

  1. 按照二叉搜索树的规则找到插入位置，建立新结点并将其颜色设为红色。

  2. 若插入前树为空，则将根结点改为黑色（满足规则 2），结束。

  3. 若 p 是黑色，则插入一个红色结点不会破坏任何规则，结束。

  4. 若 p 是红色（此时 g 必为黑色），则出现连续红色结点，需要根据 u 的情况进行变色和旋转调整。

3.2 为什么新结点必须是红色？

  • 如果插入黑色结点，一定会破坏规则 4（因为新结点所在的那条路径多了一个黑色结点，其他路径没有），而修复规则 4 非常麻烦。

  • 插入红色结点只可能破坏规则 3（当 p 也是红色时），而规则 3 可以通过局部变色和旋转修复，代价较小。
    所以新结点一律红色。

3.3 情况一：叔叔结点存在且为红色（只变色）

条件：p 为红，g 为黑，u 存在且为红。
处理：将 p 和 u 变为黑色，g 变为红色。然后以 g 为新的 c，继续向上检查（因为 g 变红后可能与其父结点再次形成连续红色）。

为什么可行？

  • 将 p 和 u 变黑，使得这两条路径各增加一个黑色，但 g 变红又抵消了 g 所在路径黑色数的变化，整体黑色数量不变。

  • 连续红色结点 c 和 p 被消灭。

  • 如果 g 是根，最后会强制变回黑色。

抽象表示：
下图中的 a/b/c/d/e 表示具有相同黑色高度的子树（具体形态不限），只要 u 为红色，无论 c 是 p 的左还是右，处理方式都一样：变色 + 继续向上。

https://your-image-host.com/rbt_case1.png

3.4 情况二：叔叔结点不存在或为黑色 + 单旋

条件：p 为红，g 为黑，（u 不存在或为黑），并且 c 和 p 在同一侧（即 p 是 g 的左且 c 是 p 的左；或者 p 是 g 的右且 c 是 p 的右）。

处理：

  • 若 p 是 g 的左孩子，对 g 进行右单旋，然后 p 变黑，g 变红。

  • 若 p 是 g 的右孩子，对 g 进行左单旋，然后 p 变黑，g 变红。

为什么这样可行？

  • 旋转后 p 成为新子树的根，并且是黑色，其左右孩子的颜色（c 和 g）一个红一个黑，不再有连续红色。

  • 子树黑色数量不变，且由于新的根 p 是黑色，不会与上层产生冲突，因此调整结束。

3.5 情况三：叔叔结点不存在或为黑色 + 双旋

条件：p 为红，g 为黑，（u 不存在或为黑），但 c 和 p 不在同一侧（即 p 是 g 的左且 c 是 p 的右；或者 p 是 g 的右且 c 是 p 的左）。

处理：

  • 若 p 是 g 的左，c 是 p 的右：先以 p 为轴左单旋，再以 g 为轴右单旋，最后将 c 变黑，g 变红。

  • 若 p 是 g 的右，c 是 p 的左：先以 p 为轴右单旋，再以 g 为轴左单旋，最后将 c 变黑，g 变红。

为什么双旋？
因为 c 在 p 的内侧，单旋无法直接让 p 成为根，所以需要两次旋转将 c 提升到顶部，然后改变颜色。

双旋后 c 成为新子树的根，且为黑色，所以不会与上层冲突，调整结束。

四、旋转代码实现

旋转操作与 AVL 树完全一致，只是不需要更新平衡因子（红黑树用颜色控制）。我们给出左单旋和右单旋的实现。

4.1 左单旋


void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;

    Node* parentParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;

    if (parentParent == nullptr)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
            parentParent->_left = subR;
        else
            parentParent->_right = subR;
        subR->_parent = parentParent;
    }
}

4.2 右单旋

void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;

    Node* parentParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;

    if (parentParent == nullptr)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
            parentParent->_left = subL;
        else
            parentParent->_right = subL;
        subL->_parent = parentParent;
    }
}

五、插入的完整代码

根据上述三种情况，实现 Insert 函数：

bool Insert(const pair<K, V>& kv)
{
    // 1. 空树：直接创建黑色根结点
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    // 2. BST 插入（寻找位置）
    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);         // 新结点默认红色
    if (parent->_kv.first < kv.first)
        parent->_right = cur;
    else
        parent->_left = cur;
    cur->_parent = parent;

    // 3. 颜色调整（parent 为红色时需处理）
    while (parent && parent->_col == RED)
    {
        Node* grandfather = parent->_parent;
        // 情况 A：parent 是 grandfather 的左孩子
        if (parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;
            // 情况1：叔叔存在且红色 -> 变色
            if (uncle && uncle->_col == RED)
            {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                // 继续向上调整
                cur = grandfather;
                parent = cur->_parent;
            }
            else  // 叔叔不存在或黑色
            {
                // 情况2：cur 是 parent 的左孩子 -> 右单旋
                if (cur == parent->_left)
                {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                // 情况3：cur 是 parent 的右孩子 -> 左右双旋
                else
                {
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;  // 调整结束
            }
        }
        else  // 情况 B：parent 是 grandfather 的右孩子（对称）
        {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED)
            {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_right)
                {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }

    // 确保根结点为黑色（可能被情况1的变色染红）
    _root->_col = BLACK;
    return true;
}

注意：旋转函数 RotateL、RotateR 内部已经处理了父指针和根节点更新，调用时传入需要旋转的结点。

六、查找与验证

6.1 查找实现

查找与普通 BST 相同：

Node* Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first < key)
            cur = cur->_right;
        else if (cur->_kv.first > key)
            cur = cur->_left;
        else
            return cur;
    }
    return nullptr;
}

6.2 验证红黑树正确性

验证一棵树是否为红黑树不能只检查“最长路径 ≤ 2×最短路径”，因为这种条件满足时仍可能违反颜色规则。正确的方法是逐条检查四个规则：

  1. 根结点是否为黑色？

  2. 是否有连续的红色结点？

  3. 所有路径的黑色结点数是否相同？

验证思路：

  • 先遍历最左路径，计算出一条参考路径的黑色结点数 refNum。

  • 再递归检查每个结点：遇到红色结点时检查其父结点是否为红色；遇到黑色结点时计数器加一。

  • 递归到空结点时，比较当前累计的黑色结点数与 refNum 是否相等。

bool Check(Node* root, int blackNum, const int refNum)
{
    if (root == nullptr)
    {
        if (blackNum != refNum)
        {
            cout << "存在黑色结点数量不同的路径" << endl;
            return false;
        }
        return true;
    }

    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续红色结点: " << root->_kv.first << endl;
        return false;
    }

    if (root->_col == BLACK)
        ++blackNum;

    return Check(root->_left, blackNum, refNum) &&
           Check(root->_right, blackNum, refNum);
}

bool IsBalance()
{
    if (_root == nullptr)
        return true;
    if (_root->_col == RED)
        return false;

    // 计算最左路径的黑色结点数作为参考值
    int refNum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            ++refNum;
        cur = cur->_left;
    }
    return Check(_root, 0, refNum);
}

七、红黑树的删除简述

红黑树的删除比插入更复杂，但核心思想类似：先按 BST 规则删除结点，然后针对可能破坏的红黑树性质进行颜色调整和旋转。删除操作主要面临以下几个问题：

  • 如果删除的是红色结点，不影响黑色高度，通常不需要调整。

  • 如果删除的是黑色结点，会导致经过该结点的路径少了一个黑色，需要从兄弟子树“借”一个黑色或通过旋转重新染色。

  • 具体处理分为多种情况（兄弟结点为红/黑，兄弟的孩子为红/黑等），使用变色和双旋来恢复平衡。

由于篇幅所限，本文不展开删除的详细实现，有兴趣的读者可以参考《算法导论》或《STL源码剖析》。

八、总结

红黑树是一种优雅的平衡二叉搜索树，它通过颜色的约束实现了近似平衡，并保证了增删查改的 O(log⁡N)O(logN) 复杂度。相对于 AVL 树，红黑树在插入和删除时的旋转次数更少，因此在工程实践中应用更广泛。

本文重点介绍了红黑树的核心规则、插入操作的三种调整情景以及旋转与变色的配合，并给出了完整的 C++ 实现代码。希望读者能通过动手编码和画图模拟，进一步加深对红黑树的理解。

红黑树不仅是一种数据结构，更是一种设计哲学的体现：用简单的颜色标记和局部调整，换取全局的平衡。掌握它，你将能更深刻地理解 STL 容器底层的工作原理，也能在需要手写平衡树时多一个可靠的选择。

参考资料

  1. Cormen, T. H. et al. Introduction to Algorithms (3rd ed.). MIT Press.

  2. 侯捷. STL 源码剖析. 华中科技大学出版社.

  3. 本文插图参考自原教学文档。

# 算法 # 数据结构 # c++
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

AtomGit 首发开源｜光轮智能发布全球首个十万小时级全模态人类行为开源数据集 EgoSuite-Open100K

avatar AtomGit开源社区
cover

AtomCode 全新上线万亿代码模型 LongCat-2.0。限时 7 天免费体验！

avatar AtomGit开源社区
cover

构筑赋能金融行业应用 Agent｜20 强决战北京，一场金融 Agent 的硬核答卷

avatar AtomGit开源社区