深入剖析 C++ 红黑树实现与 set/map 容器封装（附完整可运行代码）
·
红黑树作为一种自平衡二叉搜索树，是 C++ STL 中set、map、multiset、multimap等关联容器的底层核心结构。它通过严格的着色规则和旋转操作，确保树的高度始终维持在O(log n)级别，从而让插入、删除、查找等操作的时间复杂度稳定在O(log n)，兼顾了二叉搜索树的高效查找和平衡树的稳定性能。
本文将从红黑树的核心原理出发，一步步实现完整的红黑树，并基于它封装符合 STL 风格的set和map容器，所有代码均附带详细注释，覆盖每一个关键细节，帮助你彻底理解红黑树的工作机制。
一、红黑树的核心原理：5 条关键性质
红黑树的 “自平衡” 依赖于 5 条不可打破的性质，正是这些性质保证了树的高度平衡：
- 颜色约束：每个节点要么是红色（
RED），要么是黑色（BLACK）； - 根节点约束：根节点必须是黑色；
- 叶子节点约束：所有逻辑叶子节点（
nullptr）视为黑色； - 红色节点约束：若一个节点是红色，其两个子节点必须是黑色（不允许连续红节点）；
- 黑高约束：从任意节点到其所有后代叶子节点的路径中，黑色节点的数量相等（称为 “黑高” 相等）。
为什么新节点默认红色？新节点设为红色，不会破坏 “黑高约束”（黑色节点数量不变），仅可能违反 “连续红节点” 约束，后续只需通过简单的变色或旋转修复；若设为黑色，会直接破坏 “黑高约束”，修复成本更高。
二、红黑树完整实现（附逐行注释）
红黑树的实现分为三个核心模块：节点结构、迭代器、树的核心操作（插入、旋转、平衡调整）。
1. 基础准备：头文件与颜色枚举
首先定义必要的头文件和节点颜色枚举，避免命名污染。
#pragma once
#include <iostream>
#include <utility> // 用于std::pair（红黑树insert返回值需要）
using namespace std;
// 红黑树节点颜色枚举（用enum class避免全局命名污染）
enum class Colour {
RED, // 红色节点：新节点默认红色
BLACK // 黑色节点：根节点、叶子节点必须为黑色
};
2. 红黑树节点结构
节点是红黑树的基本单元，需要存储数据、颜色，以及指向父节点、左子节点、右子节点的指针（父节点指针是平衡调整的关键，用于追溯上层节点）。
// 红黑树节点模板类
// T：节点存储的数据类型（如int、pair<K,V>）
template <class T>
struct RBTreeNode {
T _data; // 节点存储的实际数据
RBTreeNode<T>* _left; // 左子节点指针
RBTreeNode<T>* _right; // 右子节点指针
RBTreeNode<T>* _parent; // 父节点指针（平衡调整需追溯父节点）
Colour _col; // 节点颜色
// 构造函数：初始化节点，默认红色（减少平衡调整成本）
RBTreeNode(const T& data)
: _data(data)
, _left(nullptr) // 初始无左子节点
, _right(nullptr) // 初始无右子节点
, _parent(nullptr) // 初始无父节点（根节点除外）
, _col(Colour::RED) // 新节点默认红色
{}
};
3. 红黑树迭代器：实现有序访问
迭代器是容器的 “访问接口”，红黑树迭代器需要支持中序遍历（保证访问顺序为 “左→根→右” 的有序性），核心是operator++（找下一个节点）和operator--（找前一个节点）
// 红黑树迭代器模板类
// T：节点数据类型；Ref：数据的引用类型（T&/const T&）；Ptr：数据的指针类型（T*/const T*）
template <class T, class Ref, class Ptr>
struct TreeIterator {
typedef RBTreeNode<T> Node; // 节点类型别名，简化代码
typedef TreeIterator<T, Ref, Ptr> Self; // 迭代器自身类型别名
Node* _node; // 迭代器指向的当前节点
// 构造函数：通过节点指针初始化迭代器
TreeIterator(Node* node) : _node(node) {}
// 1. 解引用运算符：返回当前节点数据的引用
Ref operator*() const { // const修饰：迭代器本身不修改时也能调用
return _node->_data;
}
// 2. 箭头运算符：返回当前节点数据的指针（用于访问结构体/类成员）
Ptr operator->() const { // const修饰：同解引用
return &_node->_data;
}
// 3. 不等于运算符：比较两个迭代器是否指向不同节点
bool operator!=(const Self& self) const {
return _node != self._node; // 直接比较节点指针
}
// 4. 等于运算符：比较两个迭代器是否指向同一节点
bool operator==(const Self& self) const {
return _node == self._node; // 直接比较节点指针
}
// 5. 前置自增运算符：找中序遍历的下一个节点（核心逻辑）
Self& operator++() {
if (_node->_right != nullptr) { // 情况1：当前节点有右子树
// 下一个节点是右子树的最左节点（中序遍历：右子树先访问左节点）
Node* cur = _node->_right;
while (cur->_left != nullptr) { // 循环找到最左节点
cur = cur->_left;
}
_node = cur; // 迭代器指向最左节点
} else { // 情况2：当前节点无右子树
// 向上追溯，找到第一个以当前节点为“左子树”的祖先（中序遍历的下一个节点）
Node* cur = _node;
Node* parent = cur->_parent;
// 只要当前节点是父节点的右子树，就继续向上追溯
while (parent != nullptr && cur == parent->_right) {
cur = parent; // 当前节点上移到父节点
parent = parent->_parent; // 父节点上移到祖父节点
}
_node = parent; // 祖先即为下一个节点（无祖先则为end()）
}
return *this; // 返回更新后的迭代器
}
// 6. 前置自减运算符：找中序遍历的前一个节点（与自增对称）
Self& operator--() {
if (_node->_left != nullptr) { // 情况1：当前节点有左子树
// 前一个节点是左子树的最右节点（中序反向：左子树先访问右节点）
Node* max = _node->_left;
while (max->_right != nullptr) { // 循环找到最右节点
max = max->_right;
}
_node = max; // 迭代器指向最右节点
} else { // 情况2：当前节点无左子树
// 向上追溯，找到第一个以当前节点为“右子树”的祖先
Node* cur = _node;
Node* parent = cur->_parent;
// 只要当前节点是父节点的左子树，就继续向上追溯
while (parent != nullptr && cur == parent->_left) {
cur = parent; // 当前节点上移到父节点
parent = parent->_parent; // 父节点上移到祖父节点
}
_node = parent; // 祖先即为前一个节点（无祖先则为begin()前）
}
return *this; // 返回更新后的迭代器
}
};
4. 红黑树核心类：插入、旋转与平衡调整
红黑树的核心逻辑集中在插入操作和插入后的平衡调整，平衡调整依赖左旋转和右旋转两种操作，用于修复 “连续红节点” 等违反性质的问题。
// 红黑树模板类
// K：键类型（用于比较排序）；T：节点数据类型；KeyOfT：从T中提取K的仿函数
template <class K, class T, class KeyOfT>
class RBTree {
typedef RBTreeNode<T> Node; // 节点类型别名，简化代码
public:
// -------------------------- 迭代器接口（供外部访问） --------------------------
typedef TreeIterator<T, T&, T*> Iterator; // 普通迭代器：可修改数据
typedef TreeIterator<T, const T&, const T*> ConstIterator; // const迭代器：只读
// 普通迭代器begin：指向中序遍历的第一个节点（最左节点）
Iterator begin() {
Node* cur = _root;
// 循环找到最左节点（中序遍历的起点）
while (cur != nullptr && cur->_left != nullptr) {
cur = cur->_left;
}
return Iterator(cur); // 用最左节点初始化迭代器
}
// 普通迭代器end：指向逻辑尾节点（nullptr，代表遍历结束）
Iterator end() {
return Iterator(nullptr);
}
// const迭代器begin：同普通begin，返回只读迭代器
ConstIterator begin() const {
Node* cur = _root;
while (cur != nullptr && cur->_left != nullptr) {
cur = cur->_left;
}
return ConstIterator(cur);
}
// const迭代器end：同普通end，返回只读迭代器
ConstIterator end() const {
return ConstIterator(nullptr);
}
// -------------------------- 插入操作（核心功能） --------------------------
// 插入数据，返回pair<迭代器, bool>：
// - 迭代器：指向插入的节点（或已存在的节点）
// - bool：true=插入成功，false=键已存在（插入失败）
pair<Iterator, bool> insert(const T& data) {
// 情况1：树为空（插入根节点）
if (_root == nullptr) {
_root = new Node(data); // 创建根节点
_root->_col = Colour::BLACK; // 根节点必须为黑色（性质2）
return { Iterator(_root), true }; // 插入成功
}
// 情况2：树非空，先按二叉搜索树规则找插入位置
KeyOfT kot; // 仿函数：从data中提取键K（用于比较）
Node* parent = nullptr; // 记录父节点（后续插入新节点需挂在父节点下）
Node* cur = _root; // 遍历指针（从根节点开始）
while (cur != nullptr) {
K curKey = kot(cur->_data); // 提取当前节点的键
K dataKey = kot(data); // 提取待插入数据的键
if (curKey > dataKey) { // 待插入键更小：向左子树找
parent = cur;
cur = cur->_left;
} else if (curKey < dataKey) { // 待插入键更大：向右子树找
parent = cur;
cur = cur->_right;
} else { // 键已存在（红黑树不允许重复键）：插入失败
return { Iterator(cur), false };
}
}
// 此时cur为nullptr，parent为插入位置的父节点，创建新节点并插入
cur = new Node(data); // 新节点默认红色
Node* newNode = cur; // 记录新节点（用于返回迭代器）
cur->_parent = parent; // 设置新节点的父节点
// 确定新节点是父节点的左子节点还是右子节点
K parentKey = kot(parent->_data);
K dataKey = kot(data);
if (parentKey > dataKey) {
parent->_left = cur; // 新节点为左子节点
} else {
parent->_right = cur; // 新节点为右子节点
}
// -------------------------- 插入后平衡调整（关键步骤） --------------------------
// 只有父节点为红色时才需要调整：
// - 父节点为黑色：插入红色节点不破坏任何性质（黑高不变，无连续红节点）
// - 父节点为红色：违反“红色节点子节点必为黑色”（性质4），需调整
while (parent != nullptr && parent->_col == Colour::RED) {
// 父节点为红色 → 祖父节点一定存在且为黑色（性质4：红色节点父节点必为黑色）
Node* grandfather = parent->_parent; // 祖父节点（平衡调整的核心节点）
// 分两种大场景：父节点是祖父的左子节点 / 右子节点（逻辑对称）
if (grandfather->_left == parent) { // 场景1：父节点是祖父的左子节点
Node* uncle = grandfather->_right; // 叔叔节点（祖父的右子节点）
// 子场景1.1：叔叔节点存在且为红色（仅需变色，无需旋转）
if (uncle != nullptr && uncle->_col == Colour::RED) {
// 变色规则：父、叔变黑（消除连续红），祖父变红（维持黑高）
parent->_col = Colour::BLACK;
uncle->_col = Colour::BLACK;
grandfather->_col = Colour::RED;
// 祖父变红后，可能与曾祖父形成连续红 → 向上继续调整
cur = grandfather; // 当前节点更新为祖父
parent = cur->_parent; // 父节点更新为曾祖父
} else { // 子场景1.2：叔叔节点不存在或为黑色（需旋转+变色）
// 子场景1.2.1：新节点是父节点的左子节点（LL型：右旋祖父）
if (cur == parent->_left) {
RotateR(grandfather); // 右旋祖父（下方实现）
// 变色：父节点变黑（替代祖父的黑高），祖父变红
parent->_col = Colour::BLACK;
grandfather->_col = Colour::RED;
} else { // 子场景1.2.2：新节点是父节点的右子节点（LR型：先左旋父，再右旋祖父）
RotateL(parent); // 先左旋父节点（将LR转为LL型）
RotateR(grandfather); // 再右旋祖父节点
// 变色：新节点变黑（替代祖父的黑高），祖父变红
cur->_col = Colour::BLACK;
grandfather->_col = Colour::RED;
}
break; // 旋转+变色后，当前子树已平衡，退出调整循环
}
} else { // 场景2：父节点是祖父的右子节点（与场景1对称）
Node* uncle = grandfather->_left; // 叔叔节点（祖父的左子节点）
// 子场景2.1：叔叔节点存在且为红色（仅需变色）
if (uncle != nullptr && uncle->_col == Colour::RED) {
parent->_col = Colour::BLACK;
uncle->_col = Colour::BLACK;
grandfather->_col = Colour::RED;
// 向上继续调整
cur = grandfather;
parent = cur->_parent;
} else { // 子场景2.2：叔叔节点不存在或为黑色（需旋转+变色）
// 子场景2.2.1：新节点是父节点的右子节点（RR型：左旋祖父）
if (cur == parent->_right) {
RotateL(grandfather); // 左旋祖父节点
// 变色：父节点变黑，祖父变红
parent->_col = Colour::BLACK;
grandfather->_col = Colour::RED;
} else { // 子场景2.2.2：新节点是父节点的左子节点（RL型：先右旋父，再左旋祖父）
RotateR(parent); // 先右旋父节点（将RL转为RR型）
RotateL(grandfather); // 再左旋祖父节点
// 变色：新节点变黑，祖父变红
cur->_col = Colour::BLACK;
grandfather->_col = Colour::RED;
}
break; // 子树平衡，退出循环
}
}
}
// 最终确保根节点为黑色（调整过程中可能将根节点改为红色）
_root->_col = Colour::BLACK;
return { Iterator(newNode), true }; // 插入成功
}
// -------------------------- 查找操作 --------------------------
// 根据键K查找节点，返回节点指针（nullptr表示未找到）
Node* Find(const K& key) const {
KeyOfT kot; // 仿函数：从节点数据中提取键
Node* cur = _root; // 从根节点开始查找
while (cur != nullptr) {
K curKey = kot(cur->_data); // 提取当前节点的键
if (curKey < key) { // 当前键更小：向右子树找
cur = cur->_right;
} else if (curKey > key) { // 当前键更大：向左子树找
cur = cur->_left;
} else { // 找到匹配键：返回节点指针
return cur;
}
}
return nullptr; // 遍历结束未找到
}
private:
// -------------------------- 旋转操作（平衡调整的核心辅助函数） --------------------------
// 右旋转：以parent为旋转中心，将左子树（subL）提升为新的父节点（解决LL型失衡）
void RotateR(Node* parent) {
Node* subL = parent->_left; // 左子树的根节点（旋转后成为新的父节点）
Node* subLR = subL->_right; // 左子树的右子树（旋转后成为parent的左子树）
// 步骤1：将subLR挂到parent的左子树
parent->_left = subLR;
if (subLR != nullptr) { // 若subLR非空，更新其父亲为parent
subLR->_parent = parent;
}
// 步骤2：记录parent的父节点（grandparent），用于后续挂接
Node* parentParent = parent->_parent;
// 步骤3：将parent挂到subL的右子树
subL->_right = parent;
parent->_parent = subL; // 更新parent的父亲为subL
// 步骤4：将subL挂到原parent的父节点（grandparent）下
if (parentParent == nullptr) { // 原parent是根节点
_root = subL; // subL成为新的根节点
subL->_parent = nullptr;
} else { // 原parent不是根节点，判断挂到grandparent的左/右
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent; // 更新subL的父亲为grandparent
}
}
// 左旋转：以parent为旋转中心，将右子树（subR）提升为新的父节点（解决RR型失衡）
void RotateL(Node* parent) {
Node* subR = parent->_right; // 右子树的根节点（旋转后成为新的父节点）
Node* subRL = subR->_left; // 右子树的左子树（旋转后成为parent的右子树）
// 步骤1：将subRL挂到parent的右子树
parent->_right = subRL;
if (subRL != nullptr) { // 若subRL非空，更新其父亲为parent
subRL->_parent = parent;
}
// 步骤2：记录parent的父节点（grandparent）
Node* parentParent = parent->_parent;
// 步骤3：将parent挂到subR的左子树
subR->_left = parent;
parent->_parent = subR; // 更新parent的父亲为subR
// 步骤4：将subR挂到原parent的父节点（grandparent）下
if (parentParent == nullptr) { // 原parent是根节点
_root = subR; // subR成为新的根节点
subR->_parent = nullptr;
} else { // 原parent不是根节点，判断挂到grandparent的左/右
if (parentParent->_left == parent) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent; // 更新subR的父亲为grandparent
}
}
private:
Node* _root = nullptr; // 红黑树的根节点（初始为空）
};
三、基于红黑树封装 set 容器
set是一种有序、不可重复的关联容器，元素本身就是键，且元素不可修改（修改会破坏有序性）。基于红黑树封装set非常简单，只需复用红黑树的逻辑，通过仿函数提取键（元素本身）即可。
#pragma once
#include "RBTree.h" // 包含红黑树头文件
namespace bobo { // 自定义命名空间，避免与STL冲突
template <class K>
class set {
// 仿函数：从set的元素中提取键（set的元素本身就是键）
struct SetKeyOfT {
const K& operator()(const K& key) const { // const修饰：不修改元素
return key; // 直接返回元素（键=元素）
}
};
public:
// 迭代器类型定义：复用红黑树的const迭代器（set元素不可修改）
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
// -------------------------- 迭代器接口 --------------------------
iterator begin() const { // set迭代器默认只读，故begin()返回const_iterator
return _t.begin();
}
iterator end() const {
return _t.end();
}
// -------------------------- 插入操作 --------------------------
// 插入元素，返回pair<iterator, bool>（同红黑树）
pair<iterator, bool> insert(const K& key) {
// 红黑树存储const K，确保元素不可修改
return _t.insert(key);
}
private:
// 底层依赖红黑树：键类型K，数据类型const K（元素不可修改），仿函数SetKeyOfT
RBTree<K, const K, SetKeyOfT> _t;
};
} // namespace bobo
四、基于红黑树封装 map 容器
map是一种有序、键不可重复的关联容器，存储键值对（pair<K, V>），通过键（K）排序，键不可修改，值（V）可修改。核心是通过仿函数提取键（pair的first成员），并实现operator[]方便访问
#pragma once
#include "RBTree.h" // 包含红黑树头文件
namespace bobo { // 自定义命名空间，避免与STL冲突
template <class K, class V>
class map {
// 仿函数：从map的键值对中提取键（pair的first成员）
struct MapKeyOfT {
const K& operator()(const pair<const K, V>& kv) const { // const修饰：不修改键值对
return kv.first; // 返回键（pair的first）
}
};
public:
// 迭代器类型定义：复用红黑树的迭代器（值可修改）
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
// -------------------------- 迭代器接口 --------------------------
iterator begin() {
return _t.begin();
}
iterator end() {
return _t.end();
}
const_iterator begin() const {
return _t.begin();
}
const_iterator end() const {
return _t.end();
}
// -------------------------- 插入操作 --------------------------
// 插入键值对，返回pair<iterator, bool>（同红黑树）
pair<iterator, bool> insert(const pair<K, V>& kv) {
// 红黑树存储pair<const K, V>，确保键不可修改
return _t.insert(kv);
}
// -------------------------- operator[]（map核心接口） --------------------------
// 支持map[key] = value语法：插入默认值（若键不存在），返回值的引用
V& operator[](const K& key) {
// 插入键值对（key, V()）：V()是V的默认构造值（如int默认0，string默认空）
pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
// 返回值的引用：ret.first是迭代器，指向键值对，->second是值
return ret.first->second;
}
private:
// 底层依赖红黑树：键类型K，数据类型pair<const K, V>（键不可修改），仿函数MapKeyOfT
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
} // namespace bobo
五、测试代码：验证红黑树与 set/map 功能
编写测试代码，验证红黑树、set、map 的核心功能（插入、遍历、查找、operator[]等）。
#include <iostream>
#include "set.h"
#include "map.h"
using namespace std;
using namespace bobo; // 使用自定义命名空间
// 测试set
void testSet() {
cout << "=== 测试set ===" << endl;
set<int> s;
// 插入元素
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(2);
s.insert(2); // 重复插入，预期失败
// 遍历set（中序有序）
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " "; // 预期输出：1 2 3 4
}
cout << endl << endl;
}
// 测试map
void testMap() {
cout << "=== 测试map ===" << endl;
map<string, int> m;
// 插入键值对
m.insert(make_pair("Alice", 25));
m.insert({"Bob", 30}); // C++11列表初始化
m["Charlie"] = 28; // 使用operator[]插入
m["Alice"] = 26; // 使用operator[]修改值
// 遍历map（按键有序）
for (auto it = m.begin(); it != m.end(); ++it) {
// it指向pair<const string, int>，->first是键，->second是值
cout << it->first << ": " << it->second << endl;
}
// 查找键
auto it = m.find("Bob"); // 若find未实现，可通过遍历查找
if (it != m.end()) {
cout << "找到Bob：" << it->second << endl; // 预期输出30
}
cout << endl;
}
int main() {
testSet();
testMap();
return 0;
}
测试输出预期：
=== 测试set ===
1 2 3 4
=== 测试map ===
Alice: 26
Bob: 30
Charlie: 28
找到Bob：30
六、总结
本文从红黑树的核心性质出发，实现了完整的红黑树，并基于它封装了set和map容器，核心要点总结如下：
- 红黑树平衡的关键：通过 “变色”（修复叔叔红的情况）和 “旋转”（修复叔叔黑的情况），维持 5 条性质，确保树高
O(log n)； - 迭代器的核心：中序遍历的有序性通过
operator++和operator--实现，分 “有子树” 和 “无子树” 两种情况追溯节点； - set/map 的复用思想：通过仿函数提取键，复用红黑树的插入、遍历逻辑，仅对外暴露符合自身特性的接口（如 set 的只读迭代器、map 的
operator[]）。
掌握红黑树的实现，不仅能理解 STL 关联容器的底层逻辑，更能提升对 “自平衡数据结构” 的设计思路，为复杂场景下的性能优化打下基础。
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)