红黑树：不只是“又一个二叉树”

说到数据结构里的“狠角色”，红黑树绝对榜上有名。

它不是那种“看起来简单、背地里全是套路”的 AVL 树，

也不是那种“随便插随便删、歪了就歪了”的普通二叉查找树，

它是那种“我既要高效，又要平衡，还得讲规则”的狠角色！

红黑树是什么？

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，

它的核心目标就是：

在频繁插入和删除的情况下，还能保持相对平衡，从而保证查找、插入、删除操作的时间复杂度稳定在 O(log n)。

为什么要有红黑树？

我们都知道二叉查找树（BST）支持插入、删除、查找操作，理想情况下时间复杂度是 O(log n)，效率很高。

但问题来了

BST 在频繁插入、删除之后，很容易变得“歪脖子”，甚至退化成链表，时间复杂度直接掉到 O(n)……

这就相当于你辛辛苦苦排了个队，结果后面的人一个接一个往前挤，最后你排了一天队还没上车。

所以，我们需要一种树，在动态更新时也能保持高效稳定的性能。

那为什么不直接用 AVL 树呢？

AVL 是“强迫症患者”，每次插入删除都可能引发多次旋转，代价太高；
而红黑树是“实用主义者”，它不要求完全平衡，只要能保证查找效率不崩就行。

一句话总结：

红黑树是在“速度”、“稳定性”和“实现成本”之间找到的一个折中王者！

什么是“平衡二叉查找树”？

简单来说，平衡二叉查找树就是一棵左右看起来比较对称、高度不太高的二叉树。

它的目标不是为了追求“数学上的美感”，而是为了让各种操作（插入、删除、查找）尽可能快。

比如 AVL 树就严格规定：任何节点的左右子树高度差不能超过1。

但红黑树没这么严格，它允许左右子树的高度差稍微大一点，只要别离谱就行。

所以你会发现：

红黑树的平衡是一种“近似平衡”，它更注重实际性能而非理论上的极致。

红黑树的五大规则（面试高频考点）

红黑树之所以叫红黑树，是因为每个节点都有颜色属性：红色 or 黑色。
但它并不是随便涂色的，必须满足以下五个条件：

1. 每个节点要么是红的，要么是黑的；
2. 根节点是黑色；
3. 所有叶子节点（NIL）都是黑色；
4. 如果一个节点是红色，那么它的两个子节点必须都是黑色（不能连续出现红色节点）；
5. 从任一节点出发，到其所有叶子节点的路径中，黑色节点的数量必须相同。

这些规则看起来有点复杂？其实它们的核心目的只有一个：

控制整棵树的高度，防止退化成链表。

红黑树 VS AVL 树：谁更强？

一句话总结：

AVL 树适合读多写少的场景，红黑树更适合写多读少、需要稳定性能的场景。

红黑树为什么综合性能好？

这就要提到它背后的原理了——红黑树等价于 2-3 树。

你可以把红黑树看作是 2-3 树的一种“可视化表达”。

2-3 树中的 3 节点会吸收不平衡性，减少旋转次数，让再平衡更快结束。

所以在综合条件下，红黑树在插入和删除操作上比 AVL 树更胜一筹。

这也解释了为什么 Java 中的 HashMap 和 TreeMap 会选择红黑树作为底层结构。

继续追根溯源，红黑树的性能优势，本质上是用空间换时间。

红黑树的实现

红黑树的节点定义

//结点的颜色
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)
	{}
};

红黑树的结构

为了简化后续关联式容器（如 map、set）的实现，在红黑树的设计中通常会引入一个头结点（header node）。

• 该头结点本身并不存储实际的数据元素，仅作为一个辅助节点，用于更方便地管理红黑树的结构和遍历操作。
• 由于红黑树的根节点必须为黑色，而头结点并不属于树的实际结构，因此也将其颜色设置为黑色，以与根节点进行区分。

头结点中三个主要指针的作用如下：

• _pParent域：指向红黑树的实际根节点；
• _pLeft域：指向红黑树中最小值节点（即最左侧节点）；
• _pRight域：指向红黑树中最大值节点（即最右侧节点）；

结点颜色定义

为了标识红黑树中每个节点的颜色属性，首先定义一个枚举类型 Colour：

enum Colour {
    RED,
    BLACK
};

结点结构定义

红黑树的每个节点包含以下几个部分：

• 存储键值对（key-value）；
• 左右子节点指针；
• 父节点指针（便于旋转操作）；
• 颜色属性；

template<class K, class V>
struct RBTreeNode {
    std::pair<K, V> _kv;              // 键值对
    RBTreeNode<K, V>* _left;          // 左孩子
    RBTreeNode<K, V>* _right;         // 右孩子
    RBTreeNode<K, V>* _parent;        // 父节点
    Colour _col;                      // 节点颜色
    RBTreeNode(const std::pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

红黑树类框架

红黑树类封装了核心的数据结构和操作接口：

template<class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    // 插入等具体操作将在后续实现


private:
    Node* _root = nullptr;  // 树根指针，初始化为空
};

旋转操作

红黑树插入或删除后可能破坏平衡性，需要通过旋转操作来调整。主要包括 左单旋 和 右单旋。

左单旋（Left Rotate）

作用：以某个节点 parent 为中心，将其右子节点 subR 提升为父节点。

实现步骤：

1. 保存 parent 的右子节点 subR 和 subR 的左子节点 subRL；
2. 将 subRL 接到 parent 的右子位置；
3. 将 parent 接到 subR 的左子位置；
4. 判断是否为整棵树的根节点，更新 _root 或连接到上层父节点。

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    // 更新 parent 和 subRL 的关系
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;
    Node* parentParent = parent->_parent;
    // 更新 subR 和 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;
    }
}

右单旋（Right Rotate）

作用：以某个节点 parent 为中心，将其左子节点 subL 提升为父节点。

实现步骤：

1. 保存 parent 的左子节点 subL 和 subL 的右子节点 subLR；
2. 将 subLR 接到 parent 的左子位置；
3. 将 parent 接到 subL 的右子位置；
4. 判断是否为整棵树的根节点，更新 _root 或连接到上层父节点。

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    // 更新 parent 和 subLR 的关系
    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;
    Node* parentParent = parent->_parent;
    // 更新 subL 和 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;
    }
}

红黑树的插入

插入节点的颜色选择：红色 or 黑色？

新插入的节点默认设置为 红色，原因如下：

• 如果插入的是 黑色节点，会导致从根到该路径的所有叶子节点的“黑节点数目”增加，从而破坏红黑树的第五条性质（所有路径的黑节点数量相同），调整起来非常复杂；
• 如果插入的是 红色节点，虽然可能导致两个连续的红色节点（违反第四条性质），但相对更容易通过变色或旋转进行修复。

因此，新插入节点初始颜色应设为红色，这样可以在保证大多数情况下不破坏红黑树性质的前提下，仅需处理少数特殊情况。

红黑树插入的基本步骤

红黑树是在二叉搜索树的基础上增加了颜色和平衡限制条件，其插入操作可分为两个阶段：

1 按照二叉搜索树规则插入新节点

• 如果当前树为空，则直接将新节点作为根节点；
• 否则，根据键值大小关系查找插入位置；
• 找到合适位置后创建新节点，并与父节点建立连接。

bool Insert(const std::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;

2 检查并修复红黑树性质

由于新插入节点是红色，若其父节点也为红色，则违反了“不能有两个连续红色节点”的规则。此时需要根据不同的情况对树进行调整。

我们定义以下变量用于描述当前状态：

• cur
• ：当前节点；
• parent
• ：当前节点的父节点；
• grandfather(g)
• ：祖父节点；
• uncle(u)
• ：叔父节点（祖父的另一个子节点）；

1) p 为 g 的 左

注：此处看到的树，有可能是一颗完整的树，也可能是一颗子树。

    // 开始检查是否破坏红黑树性质
    while (parent && parent->_col == RED) {
        grandfather = parent->_parent;
        // 情况一：父节点是祖父的左孩子
        if (parent == grandfather->_left) {
            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 和 情况3：叔父不存在 或 存在但为黑色
                // 需要进行旋转 + 变色（见下文）
                // ...
            }
        }
        else { // 父节点是祖父的右孩子
            // 对称处理逻辑
            // ...
        }
    }
    // 最终确保根节点为黑色
    _root->_col = BLACK;
    return true;
}

else//情况二： u不存在 或 存在为黑
{
   //     g
  //   p    u
 //  c
//单旋+变色
  if (cur == parent->_left)
    {
	  RotateR(grandfather);
	  parent->_col = BLACK;
	  grandfather->_col = RED;
	}
else
	{
//      g
//   p    u
//    c
// 双旋+变色
		RotateL(parent);
		RotateR(grandfather);
		cur->_col = BLACK;
		grandfather->_col = RED;


	 }


break;

(2) p 为 g 的 右

else //parent == grandfather->_right
{   //情况一：
//   g
// u   p
	Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)// u存在 且 为红
	{
		parent->_col = uncle->_col = BLACK;
		grandfather->_col = RED;


        //继续往上调整
		cur = grandfather;
		parent = cur->_parent;
	}
else//情况二：u不存在 或 存在为黑
	{
//...
	}
}


 	_root->_col = BLACK;//根始终为黑


return true;

else//情况二：u不存在 或 存在为黑
{
//   g
   // u   p
  //        c
 // 单旋+变色
if (cur == parent->_right)
	{
		RotateL(grandfather);
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
else
	{
//   g
// u   p
//    c
// 双旋+变色
		RotateR(parent);
		RotateL(grandfather);
		cur->_col = BLACK;
		grandfather->_col = RED;
	}
break;

红黑树的验证逻辑

为了确保构建的红黑树满足其所有性质，我们需要从两个方面进行验证：

1. 是否是一棵合法的二叉搜索树；
2. 是否满足红黑树的所有平衡约束条件。

验证内容一：是否为合法的二叉搜索树

可以通过中序遍历判断输出序列是否为严格递增有序序列。该验证可以单独封装实现，此处略去具体实现，重点在于红黑树特性的验证。

验证内容二：红黑树性质检查

红黑树需满足以下五条性质：

1. 每个节点要么是红色，要么是黑色；
2. 根节点必须是黑色；
3. 每个叶子节点（NIL）是黑色；
4. 不能有两个连续的红色节点（即红色节点的子节点不能是红色）；
5. 从任一节点出发到其所有叶子节点的路径中，黑色节点数量相同。

我们主要通过递归方式来验证后三条规则。

红黑树验证函数实现

bool IsBalance() {
    if (_root == nullptr) {
        // 空树是合法的红黑树
        return true;
    }
    // 性质2：根节点必须为黑色
    if (_root->_col == RED) {
        cout << "根节点不是黑色，违反红黑树性质" << endl;
        return false;
    }
    // 找到最左路径的黑节点数作为参考值（性质5）
    int refBlackCount = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == BLACK)
            ++refBlackCount;
        cur = cur->_left;
    }
    // 从根节点开始递归验证整棵树
    return Check(_root, 0, refBlackCount);
}

辅助验证函数：Check

bool Check(Node* node, int blackNum, const int& refBlackCount) {
    if (node == nullptr) {
        // 到达空节点（即叶子的子节点），检查黑节点数量是否一致
        if (blackNum != refBlackCount) {
            cout << "存在黑节点数量不一致的路径" << endl;
            return false;
        }
        return true;
    }
    // 性质4：不允许连续的红色节点
    if (node->_col == RED && node->_parent && node->_parent->_col == RED) {
        cout << "发现连续的红色节点：" << node->_kv.first << endl;
        return false;
    }
    // 统计黑色节点数量
    if (node->_col == BLACK) {
        ++blackNum;
    }
    // 递归检查左右子树
    return Check(node->_left, blackNum, refBlackCount) &&
           Check(node->_right, blackNum, refBlackCount);
}

实现的代码

#pragma once
#include <iostream>
#include <utility>
using namespace std;
// 节点颜色枚举
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:
    // 插入新节点
    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;
                // 情况1：叔父存在且为红色
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    // 情况2 & 3：叔父不存在或为黑色
                    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);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK; // 根节点始终为黑色
        return true;
    }
    // 查找指定键值的节点
    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;
    }
    // 获取树的高度
    int Height() {
        return _Height(_root);
    }
    // 中序遍历输出
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
    // 获取节点总数
    int Size() {
        return _Size(_root);
    }
    // 验证红黑树性质
    bool IsBalance() {
        if (_root == nullptr) return true;
        if (_root->_col != BLACK) return false;
        // 找一条路径作为参考黑节点数量
        int refNum = 0;
        Node* cur = _root;
        while (cur) {
            if (cur->_col == BLACK) ++refNum;
            cur = cur->_left;
        }
        return Check(_root, 0, refNum);
    }
private:
    // 辅助函数：递归验证红黑树性质
    bool Check(Node* node, int blackNum, const int refNum) {
        if (node == nullptr) {
            if (blackNum != refNum) {
                cout << "存在黑色节点数量不一致的路径" << endl;
                return false;
            }
            return true;
        }
        if (node->_col == RED && node->_parent && node->_parent->_col == RED) {
            cout << node->_kv.first << " 存在连续红色节点" << endl;
            return false;
        }
        if (node->_col == BLACK) ++blackNum;
        return Check(node->_left, blackNum, refNum) &&
               Check(node->_right, blackNum, refNum);
    }
    // 辅助函数：获取节点个数
    int _Size(Node* root) {
        return root ? _Size(root->_left) + _Size(root->_right) + 1 : 0;
    }
    // 辅助函数：中序遍历
    void _InOrder(Node* root) {
        if (!root) return;
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << " ";
        _InOrder(root->_right);
    }
    // 辅助函数：计算树的高度
    int _Height(Node* root) {
        return root ? max(_Height(root->_left), _Height(root->_right)) + 1 : 0;
    }
    // 左旋
    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;
        }
    }
    // 右旋
    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;
        }
    }
private:
    Node* _root = nullptr;
};

测试用例示例

void RBTreetest1() {
    RBTree<int, int> t;
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for (auto e : a) {
        t.Insert({e, e});
    }
    cout << "中序遍历结果：" << endl;
    t.InOrder();
    cout << "红黑树是否合法：" << t.IsBalance() << endl;
    cout << "树的高度：" << t.Height() << endl;
    cout << "节点总数：" << t.Size() << endl;
}

往期推荐

【大厂标准】Linux C/C++ 后端进阶学习路线→「链接」

C++ Qt学习路线一条龙！（桌面开发&嵌入式开发）→「链接」

哈希Hash算法：原理、应用→「链接」

点击下方关注【Linux教程】，获取编程学习路线、项目教程、简历模板、大厂面试题、大厂面经、编程交流圈子等等。