【C++进阶篇】红黑树的实现（赋源码）

一. 红黑树简介

1.1 基本概念

红黑树是一种自平衡二叉查找树，通过为节点赋予红/黑颜色属性，并遵循五条核心规则（如根节点为黑、红色节点子节点必为黑、任意路径黑色节点数相同等），确保树的高度差不超过两倍，从而在插入、删除、查找操作中维持O(log n)的时间复杂度。其平衡性通过旋转（左旋/右旋）和颜色调整实现，而非严格保持子树高度差，因此平衡维护成本低于AVL树。

声明：上述树为标准的红黑树，可能有人会思考：叶子结点的孩子为空节点，它不是黑色的呀，这不是违反规则了吗？《算法导论》补充了每个叶子结点（NIL）都是黑色的规则。NIL也会被称为外部节点。

思考一下：红黑树如何保证最长路径的长度不超过最短路径的2倍？？？

1. 极端场景下：从根到NIL节点全是黑色的，该路径就是最短路径，假设最短路径长度为h。
2. 最优情况下：一个黑节点和一个红节点假设存在h个黑色节点，也存在h个红色节点，红黑成对出现，即最长路径为2h。
3. 理论上上述两种情景很少见，基本鉴于两者之间，假设任意一条从根到NIL节点路径的长度为x，那么 h <= x < 2h。
4. 即保证上述结论成立。

如图：

1.2 红黑树效率

假设N是红黑树中节点数量，h最短路径的长度，$2^h$ -1 <= N < $2^{2h}$ -1，由此推出 h = logN，最长路径是最短路径的两倍，即意味着红黑树增删查改最坏情况下，遍历最深的深度，即2 * logN，时间复杂度为O(logN)。

1.3 意义

• 红黑树的核心价值在于平衡性能与实现复杂度：

1. 高效动态操作：相比普通二叉搜索树，避免极端情况下退化为链表；相比AVL树，减少旋转频率，提升插入/删除效率。
2. 稳定最坏性能：即使频繁更新，仍能保证对数时间复杂度，适合实时系统。
3. 内存友好：仅需1位存储颜色信息，空间开销小于AVL树的高度位存储。

1.4 应用场景

• 编程语言基础库：C++的map/set、Java的TreeMap利用红黑树实现有序键值对的高效管理。
• 操作系统内核：Linux内核用红黑树管理进程调度队列、内存页分配及虚拟文件系统元数据，优化资源分配效率。
• 数据库与存储：MySQL的InnoDB引擎使用红黑树管理索引B+树的页节点，加速范围查询。
• 网络协议栈：在需要快速查找与动态更新的场景（如路由表）中，红黑树提供低延迟支持。

二. 红黑树实现

2.1 红黑树结构

//节点颜色
enum Colour
{RED,BLACK
};// 这⾥我们默认按key/value结构实现，三叉链
// 红黑树节点结构
template<class K, class V>
struct RBTreeNode
{// 这⾥更新控制平衡也要加⼊parent指针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){}
};//红黑树结构
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};

红黑树用三叉链的数据结构实现，红黑树节点中的数据使用pair类型的数据存放，使用pair类型的数据申请红黑树节点。

2.2 插入（难点）

• 过程：

1. 如果根节点是空节点，则直接将新插入的节点更新成根节点。
2. 如果不是，则按照二叉搜索树的规则，插入的key值比根节点大，则往左走；插入的key值比根节点小，则往右走，插入相同的值插入失败，即不允许插入相同的值。然后将插入的节点与父节点进行相连即可。
   **注意：**插入的节点的颜色必须是红色，黑色很难维护，违反规则4。
3. 插入后，进行具体分析，判断插入后的节点是否破坏上述四个规则。

通过上述分析，得出的伪代码如下：

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;//插入相同的key值,直接返回false。}}//将新插入的节点与父节点相连//插入黑色节点一定不满足，很难维护，所以咱们插入红色节点cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//将当前新插入的节点与parent节点进行相连。//处理不满足红黑树规则的情况,下面继续补充。

2.2.1 单纯变色的情况

下面都是parent都是grandfather的左孩子。

• 场景1（具体的图）：
  
• 场景1：c是p的左，p是g的左。
  当parent为红，grandfather为黑，且uncle存在且为红。上述图只是一种的情况，无论c是p的左还是右，p是g的左还是右，处理方式一致，如下：将parent和uncle变为黑，grandfather变为红。当parent为黑色即可更新结束；当parent为红色，然后继续向上跟新即可。
• 场景2：c是p的右，p是g的左。
  
  另外两种不再描述，读者自己想想，锻炼思考能力。
  下面以hb==1，表示存在1个黑色节点的红黑树。
  
  d/e/f为x/y/z/m中任意一种，情况处理一致，将a/b变成黑，c变成红，然后继续向上处理。
• 扩展处理：
  当hb == (1,2,3,4,5,6,7,8,9,…n)n为自然数，因为d/e/f的情况不需要处理，它本就不违反规则。只需处理插入在a/b任意一个位置，分析是否违反规则即可。

伪代码如下：

Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{//     g//   p   u//cNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}

当uncle存在且为红时，只需变色即可。

2.2.2 单旋+变色

• 场景1（uncle不存在）：
  
  上述情况单纯变色无法解决问题，以g为旋转点进行右旋，然后将c/g变为红色，p变为黑色。
• 场景2（uncle存在且为黑，且插入的新节点在p的左边）：
  

场景1：以g为旋转点进行右单旋，再把g变为红色，p变为黑色。

2.2.3 双旋+变色

• 场景3（uncle存在且为黑，插入的新节点位于parent的右）
  

现以parent为旋转点进行左单旋，在意grandfather为旋转点进行右单旋。旋转完成之后跳出循环即可。

• 伪代码如下：

if (cur == parent->_left)
{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;
}
else
{//uncle不存在，则c一定是新增节点，假设c不是新增节点，则c一定是黑色，违反规则3//     g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = RED;grandfather->_col = RED;
}break;

parent是grandfather右孩子的处理情况一致。本人就不再重复写了，直接上代码（如下）：

else//grandfather右孩子为parent
{//     g//   u   p//cNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle ->_col= parent->_col = BLACK;cur = grandfather;parent = cur->_parent;}else//uncle不存在，或者uncle存在且为黑{//uncle不存在，则c一定是新增节点，假设c不是新增节点，则c一定是黑色，违反规则3//     g黑                    g            p// u黑     p红              u    p       g  c//      c红                         c  uif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}

整合代码如下：

	while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){//     g//   p   u//cNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else//uncle不存在，或者uncle存在且为黑{//uncle不存在，则c一定是新增节点，假设c不是新增节点，则c一定是黑色，违反规则3//     g//        p//      c//uncle不存在，或者uncle存在且为黑下面都可以解决上述两个场景if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//uncle不存在，则c一定是新增节点，假设c不是新增节点，则c一定是黑色，违反规则3//     g//   p    u//     cRotateL(parent);RotateR(grandfather);cur->_col = RED;grandfather->_col = RED;}break;}}else//grandfather右孩子为parent{//     g//   u   p//cNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED){grandfather->_col = RED;uncle ->_col= parent->_col = BLACK;cur = grandfather;parent = cur->_parent;}else//uncle不存在，或者uncle存在且为黑{//uncle不存在，则c一定是新增节点，假设c不是新增节点，则c一定是黑色，违反规则3//     g黑                    g            p// u黑     p红              u    p       g  c//      c红                         c  uif (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;
}

2.3 查找

按照二叉搜索树的规则，插入，过程如下：

• 当前插入的key值比当前节点的key值小，则往左走；比它大，往右走
• 相等直接返回当前节点的指针，走至空返回false即可。
• 查询效率O(logN)。
  伪代码如下：

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

2.4 红黑树的验证

思路：以最左路径计算出此路径的黑色节点个数记为h1为参考值，依次递归求其它路径的黑色节点个数，比较各个路径黑色节点个数与h1的比值，发现任意一条路径不同直接返回false即可，所有路径遍历完都相等且任意一条路径的不存在连续的红色节点返回true即可。

• 伪代码如下：

bool Check(Node* root, int blackNum, 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);
}

2.5 AVL与RBTree对比

测试代码：

#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;#include"RBTree.h"
#include"AVLTree.h"// 测试代码
void TestRBTree1()
{RBTree<int, int> t;// 常规的测试用例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){/*if (e == 14){int x = 0;}*/t.Insert({ e, e });//cout << "Insert:" << e << "->";//cout << t.IsBalanceTree() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestRBTree2()
{const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();RBTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsBalance() << endl;cout << "RBTree Insert:" << end2 - begin2 << endl;cout << "RBTree Height:" << t.Height() << endl;cout << "RBTree Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*/// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "RBTree Find:" << end1 - begin1 << endl << endl;
}void TestAVLTree2()
{const int N = 10000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsBalanceTree() << endl;cout << "AVLTree Insert:" << end2 - begin2 << endl;cout << "AVLTree Height:" << t.Height() << endl;cout << "AVLTree Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*/// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "AVLTree Find:" << end1 - begin1 << endl;
}int main()
{TestRBTree2();TestAVLTree2();return 0;
}

运行结果：

1
RBTree Insert:1202
RBTree Height:6
RBTree Size:22
RBTree Find:220
1
AVLTree Insert:2633
AVLTree Height:26
AVLTree Size:6325673
AVLTree
Find:2447

结论：红黑树在插入/删除效率上优于AVL树，而AVL树在查找效率上略胜一筹。

三. 最后

本文阐述了红黑树是一种高效的自平衡二叉搜索树，通过颜色标记和旋转操作维持近似平衡，确保增删查改时间复杂度为O(log n)。其核心规则包括根节点黑、红节点子节点必黑、任意路径黑节点数相同，最长路径不超过最短两倍。相比AVL树，红黑树减少旋转次数，插入/删除效率更高，适合动态数据场景，广泛应用于C++ STL、Linux内核及数据库索引。实现时通过三叉链结构管理节点，插入需处理变色、单旋+变色、双旋+变色三种情况。验证时检查路径黑节点数与连续红色节点。测试表明，红黑树插入效率优于AVL树，而AVL树因严格平衡查找略快，两者均保障了稳定对数级性能。