【C++】《C++红黑树从0到1：插入、旋转、迭代器，并模拟实现set与map》

一. 红⿊树的概念

红⿊树是⼀棵二叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会比其他路径长出2倍，因⽽是接近平衡的。

1.红黑树的规则：

说明：《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是⿊⾊的规则。他这⾥所指的叶⼦结点不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道⼀下这个概念即可。

简单图示一下：

2.补充问题

1.为什么它的根节点是黑色的，不是红色的？

答：其实不是必须，是规定成黑色更省事。

红黑树本身没有规定根必须是黑的，它只规定了每条路径上的黑色节点数量要一样。这个规则足够保证树的大致平衡。问题出在实现上。如果根是红的，插入删除的时候，你总得额外想一下：“哎，这个根是不是红的？要不要给它改成黑的？”改来改去很烦。

所以干脆一开始就把根定成黑的，省得每次都要处理这个特殊情况。代码写起来少一个分支，脑子少想一件事。说白了，不是技术上的必须，是设计上的方便。规则统一了，实现就简单了。

2.思考⼀下，红⿊树如何确保最长路径不超过最短路径的2倍的？

• 由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就是全是黑色结点的路径，假设最短路径长度为bh(black height)。
• 由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀黑⼀红间隔组成，那么最长路径的长度为2*bh。
• 综合红黑树的4点规则⽽言，理论上的全黑最短路径和⼀黑⼀红的最长路径并不是在每棵红黑树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2*bh。

3.红⿊树的效率：

假设N是红⿊树树中结点数量，h最短路径的⻓度，那么 2^h −1, 由此推出h 1 <= N < 2^2h-1由此推出h ≈ logN ，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 2 ∗ logN ，那么时间复杂度还是O(logN)

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

二.红黑树的实现

红黑树本身不关心你存的是什么，它只管把 T当作一个整体存到节点里。至于 T 是什么，由上层容器来决定：

• set 给红黑树传的是 Key，所以红黑树里存的就是键值本身

• map 给红黑树传的是 pair<const Key, V>，所以红黑树里存的就是键值对，其中 Key 带 const 是防止键被修改

所以红黑树就像个通用的架子，set 和 map 只是往这个架子上放了不同类型的东西。

1.定义红黑树的节点结构

// 颜色枚举
enum Colour
{
RED,
BLACK
};

// 红黑树节点结构体
template<class T>
struct RBTreeNode
{
// ———- 三叉链 ———-
RBTreeNode<T>* _left; // 左孩子
RBTreeNode<T>* _right; // 右孩子
RBTreeNode<T>* _parent; // 父节点（方便向上回溯）

//数据域
T _data; // 存储的数据，可能是 Key 或 pair<const Key, V>

//颜色标记色，红或黑
Colour _col;

//构造函数
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED) // 新节点默认红色
{}
};

2.定义红黑树结构

定义红黑树结构（KV）

红黑树作为一个底层容器，需要同时支持 set 和 map 两种上层容器。但问题是，set 存的是 Key，map 存的是 pair<const Key, V>，两者在插入时比较数据的方式不同。如果红黑树写死了比较方式，就只能适配一种容器，没法通用。

改造之前的代码：

// 红黑树类模板
// K：键的类型（用于比较查找）
// T：节点存储的数据类型（set传Key，map传pair<const K, V>）
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;

public:
// 构造函数：初始时树为空，根节点置空
RBTree() : _root(nullptr) {}

// 插入节点：将数据插入到红黑树中，并保持红黑树的性质
bool Insert(const T& data);

// … 其他接口（查找、删除、中序遍历等）

private:
Node* _root; // 根节点指针

在红黑树的插入节点接口中要先通过比较节点中数据的大小来查找适合插入的位置，但是红黑树并不知道数据 data 到底是 key 还是 pair，没有办法确定。假设数据 data 是 key，那么直接取 key 来作比较；如果数据 data 是 pair，则需要取 first 来作比较。

那如何解决呢？STL源码给出了这样的结果：通过传给模板参数 KeyOfValue 的是 set 的仿函数还是 map 的仿函数来应对不同类型数据的比较：

接着看改造之后的代码：

红黑树只负责存数据和维护平衡，但它不知道上层传进来的是什么类型的数据。比较的时候，如果是 set，直接比较 Key 就行；如果是 map，需要取 pair 的 first 来比较。

为了让红黑树能统一处理这两种情况，给它增加了一个模板参数 KeyOfT，它是一个仿函数类，由 set 和 map 各自实现并传进来：

• set 传的是 SetKeyOfT，从 T 中取出 Key
• map 传的是 MapKeyOfT，从 T 中取出 pair.first

有了这个仿函数，红黑树在插入时就不用关心 T 到底是什么类型了，只需要调用 KeyOfT 从数据中取出键值来比较即可。

新的红黑树的定义：

• K：键值key的类型。
• T：数据的类型，如果是 map，则为 pair<const K, V>；如果是 set，则为 K。
• KeyOfT：通过 T 的类型来获取 key 值的一个仿函数类。

// 红黑树类模板（改造后）
template<class K, class T, class KeyOfT>
class RBTree
{
// 给红黑树节点类型起别名
typedef RBTreeNode<T> Node;

public:
// 构造函数：树初始为空，根节点指向 nullptr
RBTree() : _root(nullptr) {}

// 插入节点
// 参数 data 是要插入的数据（可能是 Key 或 pair）
// 返回值：当前是 bool（true/false），后续会改成 pair<iterator, bool>
// 以便和 STL 接口保持一致
bool Insert(const T& data);

// …..其他接口迭代器、查找、删除、operator[] 等）

private:
Node* _root; // 根节点指针，整棵树的入口
};

图示声明：

我们通过 T 的类型和对应的取 T 类型对象的值的仿函数，就可以进行不同类型数据的比较了：

3.红黑树的插入

红黑树插⼊⼀个值的⼤概过程：

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊，插⼊后我们只需要观察是否符合红⿊树的4条规则。
2. 如果是空树插⼊，新增结点是⿊⾊结点。如果是⾮空树插⼊，新增结点必须红⾊结点，因为⾮空树插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的。
3. ⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束
4. ⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是红⾊，p为红，g必为⿊，这三个颜⾊都固定了，关键的变化看u的情况，需要根据u分为以下⼏种情况分别处理。

说明：下图中假设我们把新增结点标识为c (cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为
g(grandfather)，p的兄弟标识为u（uncle）。

情况1：变⾊

c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红。在把g当做新的c，继续往上更新。
分析：因为p和u都是红⾊，g是⿊⾊，把p和u变⿊，左边⼦树路径各增加⼀个⿊⾊结点，g再变红，相当于保持g所在⼦树的⿊⾊结点的数量不变，同时解决了c和p连续红⾊结点的问题，需要继续往上更新是因为，g是红⾊，如果g的⽗亲还是红⾊，那么就还需要继续处理；如果g的⽗亲是⿊⾊，则处理结束了；如果g就是整棵树的根，再把g变回⿊⾊。
情况1只变⾊，不旋转。所以⽆论c是p的左还是右，p是g的左还是右，都是上⾯的变⾊处理⽅式。

图0：

•  跟AVL树类似，图0我们展⽰了⼀种具体情况，但是实际中需要这样处理的有很多种情况。
•  图1将以上类似的处理进⾏了抽象表达，d/e/f代表每条路径拥有hb个⿊⾊结点的⼦树，a/b代表每条路径拥有hb-1个⿊⾊结点的根为红的⼦树，hb>=0。
•  图2/图3/图4，分别展⽰了hb == 0/hb == 1/hb == 2的具体情况组合分析，当hb等于2时，这⾥组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理⽅式⼀样的，变⾊再继续往上处理即可，所以我们只需要看抽象图即可。

图1：

图2：

图3：

图4：

情况2：单旋+变⾊

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。

分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊。

如果p是g的左，c是p的左，那么以g为旋转点进⾏右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的右，那么以g为旋转点进⾏左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

情况3：双旋+变⾊

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。

分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊。

如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变
⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

红⿊树的插⼊代码实现：

// 红黑树插入
// 旋转代码跟 AVL 树一样，只是不需要更新平衡因子
// 核心国成：插入新节点 —> 检测是否违反规则 —> 变色/旋转修复

bool Insert(const pair<K, V>& kv)
{
//第1步：树为空，直接插入根节点 if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK; // 根节点必须是黑色
return true;
}

// 第2步：查找插入位置
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; // 键已存在，插入失败
}
}

//第3步：插入新节点
cur = new Node(kv);
cur->_col = RED; // 新节点默认红色（不影响黑色路径）

// 连接父节点
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;

//第4步：调整平衡
// 父节点是红色才需要调整（违反不能连续红规则）
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;

//情况一：父节点是祖父的左孩子
// g(黑)
// / \\
// p(红) u(?)

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)
{
// 子情况2：左左 → 右单旋
// g
// / \\
// p u
// /
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 子情况3：左右 → 左右双旋
// g
// / \\
// p u
// \\
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; // 旋转后树已平衡，退出循环
}
}

//情况二：父节点是祖父的右孩子（对称
// g(黑)
// / \\
// u(?) p(红)

else
{
Node* uncle = grandfather->_left;

// 子情况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->_right)
{
// 子情况2：右右 → 左单旋
// g
// / \\
// u p
// \\
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 子情况3：右左 → 右左双旋
// g
// / \\
// u p
// /
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; // 旋转后树已平衡，退出循环
}
}
}

// 第5步：保证根节点是黑色
_root->_col = BLACK;
return true;
}

4.红⿊树的查找：

按⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)

// 查找函数：根据键值 key 在红黑树中查找对应的节点
// 返回值：找到返回节点指针，找不到返回 nullptr

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; // 遍历完还没找到，返回空指针
}

5.红⿊树的验证：

这⾥获取最⻓路径和最短路径，检查最⻓路径不超过最短路径的2倍是不可⾏的，因为就算满⾜这个条件，红⿊树也可能颜⾊不满⾜规则，当前暂时没出问题，后续继续插⼊还是会出问题的。所以我们还是去检查4点规则，满⾜这4点规则，⼀定能保证最⻓路径不超过最短路径的2倍。

这段代码用于验证一棵树是否满足红黑树的性质，主要检查三条：

根节点是黑色的；

没有连续的红色节点；

所有路径上的黑色节点数量相同。

IsBalance —-  入口函数

bool IsBalance()
{
// 空树也算红黑树
if (_root == nullptr)
return true;

// 规则1：根节点必须是黑色
if (_root->_col == RED)
return false;

//计算参考值 refNum
// 取最左路径上的黑色节点数量作为基准值
// 所有路径的黑色节点数量都必须等于这个值
int refNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refNum; // 统计最左路径上的黑色节点数
}
cur = cur->_left; // 一直往左走
}

// 递归检查每条路径
return Check(_root, 0, refNum);
}

通俗理解：先算出标准答案（最左路径有多少个黑色节点），然后拿着这个标准去检查每一条路径是否一致。

Check —- 递归检查函数

bool Check(Node* root, int blackNum, const int refNum)
{
//1. 走到空节点
// 说明一条路径走完了，检查黑色节点数量是否达标
if (root == nullptr)
{
if (refNum != blackNum)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}

//2. 检查连续红色节点
// 当前节点是红色，父节点也是红色 —> 违规
// 检查孩子不方便（两个孩子不一定存在），反过来检查父亲更方便
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续的红色节点" << endl;
return false;
}

//3. 统计黑色节点
// 当前节点是黑色，路径上的黑色节点数 +1
if (root->_col == BLACK)
{
blackNum++;
}

//4. 递归检查左右子树
// 两条路径都必须满足条件
return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);
}

6.红黑树的删除

红⿊树的删除比较复杂，掌握红黑树的差距已经足够了，本节不做讲解，有兴趣的话可参考：《算法导论》或者《STL源码剖析》中讲解。

下面的代码这是一棵手写的红黑树，专门给 set 和 map 当底层框架用的，因为为了模拟实现map和set(里面的命名我做了大致修改方便后续学习）。

#pragma once
// 颜色枚举：标记节点是红色还是黑色
// 红黑树靠颜色来维持平衡，红色节点不能连续出现
enum Colour
{
RED,
BLACK
};

// 红黑树节点
// 三叉链结构：左孩子 + 右孩子 + 父节点（方便向上回溯）
// 存数据 + 颜色标记
// 新节点默认红色，插入时调整成本更低
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left; // 左孩子
RBTreeNode<T>* _right; // 右孩子
RBTreeNode<T>* _parent; // 父节点（向上回溯用）

T _data; // 数据域（set存Key，map存pair）
Colour _col; // 颜色标记

RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED) // 新节点默认红色
{}
};

// 红黑树迭代器
// 支持 *、->、++、–、==、!=
// 遍历顺序是中序遍历（左->根->右），得到有序序列

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node; // 指向当前节点

__RBTreeIterator(Node* node = nullptr) // 带默认值，方便构造end()
: _node(node)
{}

// ========== 解引用操作 ==========
Ref operator*()
{
return _node->_data; // 返回节点数据的引用
}

Ptr operator->()
{
return &_node->_data; // 返回节点数据的指针
}

//比较操作
bool operator!=(const Self& s) const
{
return _node != s._node;
}

bool operator==(const Self& s) const
{
return _node == s._node;
}

// 前置++：中序后继（下一个节点）
// 如果有右子树，找右子树的最左节点
// 如果没有右子树，向上找第一个不是父节点右孩子的祖先
Self& operator++()
{
if (_node->_right)
{
// 有右子树 -> 右子树的最左节点
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
// 没右子树 -> 往上找
// 直到当前节点不是父节点的右孩子时停
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}

// 前置–：中序前驱（上一个节点）
// 如果有左子树，找左子树的最右节点
// 如果没有左子树，向上找第一个不是父节点左孩子的祖先
Self& operator–()
{
if (_node->_left)
{
// 有左子树 -> 左子树的最右节点
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
// 没左子树 -> 往上找
// 直到当前节点不是父节点的左孩子时停
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};

// 红黑树本体
// K：键的类型，用于比较查找
// T：存的数据类型（set传Key，map传pair<const Key, V>）
// KeyOfT：仿函数类，从T中取出键值K来比较
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;

public:
typedef __RBTreeIterator<T, T&, T*> iterator;

// begin：返回最左节点（最小值）
// 从根一直往左走到底
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}

// end：返回nullptr（结束标志）
iterator end()
{
return iterator(nullptr);
}

// 插入函数 —— 核心
// 步骤：
// 1. 树为空 –> 直接插，根节点染黑
// 2. 按BST规则找插入位置
// 3. 插入新节点，默认红色
// 4. 父节点为红色 –> 需要调整（变色/旋转）
// 5. 最后根节点强制黑色
// 返回值：pair<iterator, bool>（迭代器指向插入节点，bool表示是否成功）
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot; // 仿函数对象，用来取出键值

//树为空
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}

// 找插入位置
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false); // 键已存在，插入失败
}
}

// 插入新节点
cur = new Node(data);
Node* newnode = cur; // 保存新节点指针，用于返回
cur->_col = RED; // 新节点默认红色

if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;

// 调整平衡（核心难点）
// 父节点是红色 –> 违反不能连续红规则，需要处理
// 处理方式：看叔叔的颜色
// 叔叔是红色 –> 变色，继续往上
// 叔叔是黑色或不存在 –> 旋转 + 变色，结束
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater); // 爷爷必须存在
assert(grandfater->_col == BLACK); // 爷爷必须是黑色

// 情况A：父节点是爷爷的左孩子
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;

// 情况1：叔叔存在且为红色 → 变色，继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
// 情况2+3：叔叔不存在或为黑色 –> 旋转 + 变色
else
{
// 情况2：左左（cur是parent的左孩子）–> 右单旋
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
// 情况3：左右（cur是parent的右孩子）–> 左右双旋
else
{
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break; // 调整完成，退出循环
}
}
//情况B：父节点是爷爷的右孩子（对称）
else
{
Node* uncle = grandfater->_left;

// 情况1：叔叔存在且为红色 –> 变色，继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
// 情况2+3：叔叔不存在或为黑色 –> 旋转 + 变色
else
{
// 情况2：右右（cur是parent的右孩子）→ 左单旋
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
// 情况3：右左（cur是parent的左孩子）–> 右左双旋
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break; // 调整完成，退出循环
}
}
}

//最后保证根节点是黑色
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}

// 中序遍历：左–>根–>右，得到有序序列
// 用来验证树是否满足二叉搜索树性质

void InOrder()
{
_InOrder(_root);
cout << endl;
}

// 验证红黑树是否合法
// 检查三项：
// 1. 根节点是黑色
// 2. 没有连续的红色节点
// 3. 所有路径上的黑色节点数量相同
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}

// 规则1：根必须是黑色
if (_root->_col == RED)
{
cout << "根节点不是黑色" << endl;
return false;
}

// benchmark：最左路径上的黑色节点数量（作为标准值）
int benchmark = 0;
return PrevCheck(_root, 0, benchmark);
}

private:

// PrevCheck：递归检查每条路径
// 参数：
// root 当前节点
// blackNum 当前路径已累计的黑色节点数
// benchmark 基准值（所有路径必须相等）
// 返回值：true表示该路径合法，false表示不合法

bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
//走到空，说明一条路径走完了
if (root == nullptr)
{
// 第一次走到空，设置基准值
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}
// 检查当前路径的黑节点数是否等于基准值
if (blackNum != benchmark)
{
cout << "某条路径黑色节点的数量不相等" << endl;
return false;
}
return true;
}

//统计黑色节点
if (root->_col == BLACK)
{
++blackNum;
}

// 规则2：不能有连续红色节点
// 检查父亲比检查孩子更方便（孩子可能不存在）
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}

// 递归检查左右子树
return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}

// 中序遍历递归实现
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}

// 左单旋
// 适用场景：右右型（parent->_bf == 2，subR->_bf == 1）
// 旋转后：parent和subR的平衡因子都为0
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

// subRL 交给 parent 做右子树
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}

Node* ppNode = parent->_parent;

// parent 成为 subR 的左子树
subR->_left = parent;
parent->_parent = subR;

// subR 顶替 parent 的位置
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}

// 右单旋
// 适用场景：左左型（parent->_bf == -2，subL->_bf == -1）
// 旋转后：parent和subL的平衡因子都为0
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

// subLR 交给 parent 做左子树
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}

Node* ppNode = parent->_parent;

// parent 成为 subL 的右子树
subL->_right = parent;
parent->_parent = subL;

// subL 顶替 parent 的位置
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}

private:
Node* _root = nullptr; // 根节点指针
};

代码具体干了这几件事：
存数据：节点里有一个 _data，可以存 Key（给 set 用），也可以存 pair<const Key, V>（给 map 用）

插入时自动调平衡：插完数据后自动变色、旋转，保证树始终平衡，查找效率稳定在 O(logN)

遍历：提供了迭代器，支持 begin() / end()，可以用范围 for 遍历

验证：自带 IsBalance()，检查有没有连续红节点、每条路径黑节点数是否一致

三.红黑树的迭代器

迭代器设计说明：

迭代器的好处在于可以方便地遍历容器，让用户无需关心底层的具体数据结构。map 和 set 的迭代器本质上就是对红黑树迭代器的封装。

如果要在红黑树中增加迭代器支持，需要解决以下两个核心问题：

1.begin() 与 end() 的定位

STL 规定，begin() 与 end() 构成一个前闭后开的区间 [begin, end)。

对红黑树进行中序遍历可以得到一个有序序列。在 SGI-STL 的源码实现中，红黑树设有哨兵头节点（header）：

• begin() 指向红黑树中的最小节点（即最左侧节点）
• end() 指向头节点（header）

问题来了，end() 应该放在哪里？

begin() 放在最左侧节点很容易理解，但 end() 的位置需要思考：它应该放在最大节点（最右侧节点）的下一个位置，问题在于这个下一个位置具体在哪里？

理论上，可以在红黑树中增设一个头节点（header）作为哨兵，让 end() 指向它，这样就能合法表示末尾之后的位置。

不过我们这里只是为了理解底层原理，做模拟实现时没必要搞得那么复杂。为了保持代码简洁，我们不设置 header 节点，直接让 end() 返回 nullptr 即可。

这样虽然和 STL 源码的实现有细微差别，但核心逻辑是相通的，不影响对迭代器机制的理解。

// 红黑树迭代器接口
// begin() 返回指向最小节点的迭代器
// end() 返回指向 nullptr 的迭代器（结束标志）

template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node; // 节点类型别名

public:
typedef _RBTreeIterator<T, T&, T*> iterator; // 迭代器类型别名

// begin()：返回指向树中最小节点的迭代器
// 最小节点就是最左侧的节点（一直往左走到底）
// 时间复杂度：O(logN)
iterator begin()
{
Node* left = _root;
while (left && left->_left) // 一直往左走，直到没有左孩子
{
left = left->_left;
}
return iterator(left); // 用最左节点构造迭代器

// 由于迭代器构造函数支持隐式类型转换（单参构造），
// 也可以直接写：return left; 编译器会自动将 Node* 转换为 iterator
}

// end()：返回一个代表末尾之后位置的迭代器
// 我们的实现中直接用 nullptr 表示结束
// 和 STL 源码中用哨兵头节点不同，但功能等价

iterator end()
{
return iterator(nullptr); // nullptr 作为结束标志
// 也可以简写为：return nullptr;
}

private:
Node* _root = nullptr; // 根节点
};

2.operator++()与operator–()  

咱是按照中序遍历（左子树 –> 根 –> 右子树） 来走，分为以下几种情况： 

1.当迭代器 it 指向的节点有右子树时（即 _node->_right 不为空），执行 ++it 操作时，下一个要访问的节点是右子树中序遍历的第一个节点。右子树的中序遍历顺序为：左子树 –> 根 –> 右子树，所以第一个被访问的节点就是右子树中的最左节点，也就是右子树中值最小的节点。

2.当迭代器 it 指向的节点没有右子树时（_node->_right == nullptr），说明以 it 为根的子树已经遍历完了。此时需要向上回溯，找到第一个满足以下条件的祖先节点：当前节点不是其父节点的右孩子（即当前节点是父节点的左孩子）。这个祖先节点，就是下一个要访问的位置

则 it++ 要访问的节点是：it 指向节点的父亲的父亲（即节点 13）。

it 指向节点 11，而节点 11 的右子树为空；同时 it 是父节点 8 的右孩子。 此时，it++ 要访问的节点是：it 所指向节点的父亲的父亲，也就是节点 13。

3.当 it 指向的节点没有右子树，且该节点是父节点的左孩子时，说明以该节点为根的子树已经访问完了，而父节点还没有被访问。因此下一个访问的就是它的父节点。则 it++ 要访问的节点是：it 指向节点的父亲节点（即节点 17）。

it 指向节点 15的右子树为空，且 it 是它父节点 17 的左孩子 则 it++ 要访问的节点是：it 指向节点的父节点（即节点 17）

注意：当 it 访问到最后一个节点（即树中的最大节点）时，该节点没有右子树，因此会触发向上回溯的逻辑。此时不断向上找父节点，一路回溯到根节点。由于根节点也没有父节点，最终会走到 nullptr，迭代器变成 end()。而我们的 end() 底层就是用 nullptr 表示的，所以当 it 访问完最后一个节点后再执行 ++，它就自动等于 end() 了。

如果 cur 走到最后一个节点 27 时： 经过 while 循环，cur 会走到根，此时 cur 父亲为空，结束循环，返回空，也即是 end ()

// 红黑树迭代器
// 模拟实现 STL 的迭代器，支持中序遍历（有序遍历）

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
// 类型别名
typedef RBTreeNode<T> Node; // 节点类型
typedef __RBTreeIterator<T, Ref, Ptr> Self; // 迭代器自身类型

Node* _node; // 节点指针，指向当前迭代器位置

//构造函数
// 用节点指针构造迭代器（支持隐式类型转换）
__RBTreeIterator(Node* node = nullptr) // 带默认值，方便构造 end()
: _node(node)
{}

// 解引用操作
// operator* ：返回节点数据的引用
Ref operator*()
{
return _node->_data;
}

// operator->：返回节点数据的指针
Ptr operator->()
{
return &_node->_data;
}

// 比较操作
// 比较两个迭代器是否相等（比较节点指针即可）
bool operator!=(const Self& s) const
{
return _node != s._node;
}

bool operator==(const Self& s) const
{
return _node == s._node;
}

// operator++：前置++，指向中序遍历的下一个节点
// 中序遍历顺序：左子树 –> 根 –> 右子树

Self& operator++()
{
// 情况1：当前节点有右子树
// 下一个节点 = 右子树中的最左节点（最小值）
if (_node->_right != nullptr)
{
Node* left = _node->_right;
while (left->_left) // 一直往左走
{
left = left->_left;
}
_node = left; // 找到右子树的最左节点
}

// 情况2：当前节点没有右子树
// 需要向上回溯，直到当前节点是其父节点的左孩子
else
{
Node* parent = _node->_parent;
Node* cur = _node;

// 不断向上走，直到 cur 是 parent 的左孩子
// 或者 parent 为空（说明走到了根，++ 后变成 end()）
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent; // 如果 parent 为空，_node 为 nullptr → end()
}

return *this; // 返回自身的引用（支持链式操作）
}

// operator–：前置–，指向中序遍历的上一个节点
// 中序逆序遍历顺序：右子树 –> 根 –> 左子树（对称）

Self& operator–()
{
// 情况1：当前节点有左子树
// 上一个节点 = 左子树中的最右节点（最大值）
if (_node->_left != nullptr)
{
Node* right = _node->_left;
while (right->_right) // 一直往右走
{
right = right->_right;
}
_node = right; // 找到左子树的最右节点
}

//情况2：当前节点没有左子树
// 需要向上回溯，直到当前节点是其父节点的右孩子
else
{
Node* parent = _node->_parent;
Node* cur = _node;

while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}

return *this;
}
};

四.map和set的插入

map 和 set 的插入操作，底层都是调用红黑树的插入接口。所以想要理解它们，得先搞清楚红黑树的插入是怎么做的。

红黑树的插入逻辑是这样的：先根据键值去树里找，看这个键存不存在。

• 如果已经存在，插入失败，返回一个 pair：<指向该键所在节点的迭代器, false>
• 如果不存在，就插入新节点，然后返回：<指向新节点的迭代器, true>

这里的 T 是红黑树存的数据类型：

• 对于 set，T 就是 K（直接存键）
• 对于 map，T 是 pair<const K, V>（存键值对）

// 红黑树插入函数
// 返回值：pair<iterator, bool>
// first：指向插入节点（或已存在节点）的迭代器
// second：true 表示插入成功，false 表示键已存在

pair<iterator, bool> Insert(const T& data)
{
// 情况1：树为空
if (_root == nullptr)
{
_root = new Node(data); // 创建根节点
_root->_col = BLACK; // 根节点必须为黑色

return make_pair(iterator(_root), true);
}

// 情况2：树不为空，找插入位置
Node* parent = nullptr;
Node* cur = _root;

while (cur) // cur 为空时，说明找到插入位置了
{
// 用仿函数取出键值进行比较
if (KeyOfT()(data) > KeyOfT()(cur->_data)) // 插入键 > 当前键 –> 往右走
{
parent = cur;
cur = cur->_right;
}
else if (KeyOfT()(data) < KeyOfT()(cur->_data)) // 插入键 < 当前键 –> 往左走
{
parent = cur;
cur = cur->_left;
}
else // 键已存在，不允许重复插入
{
return make_pair(iterator(cur), false);
}
}

// 情况3：插入新节点
cur = new Node(data); // 创建新节点
Node* newnode = cur; // 保存新节点位置（用于返回）
cur->_col = RED; // 新节点默认红色

// 连接父节点
if (KeyOfT()(cur->_data) > KeyOfT()(parent->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent; // 设置父指针

// 情况4：调整平衡
// 父节点是红色时才需要处理（违反不能连续红规则）
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater);
assert(grandfater->_col == BLACK);

// 情况A：父节点是爷爷的左孩子
// g(黑)
// / \\
// p(红) u(?)
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;

// 子情况1：叔叔存在且为红色 –> 变色，继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
// 子情况2+3：叔叔不存在或为黑色 –> 旋转 + 变色
else
{
// 子情况2：左左 –> 右单旋
// g
// / \\
// p u
// /
// c
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
// 子情况3：左右 –> 左右双旋
// g
// / \\
// p u
// \\
// c
else
{
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break; // 调整完成，退出循环
}
}

// 情况B：父节点是爷爷的右孩子（对称）
// g(黑)
// / \\
// u(?) p(红)
else
{
Node* uncle = grandfater->_left;

// 子情况1：叔叔存在且为红色 –> 变色，继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
// 子情况2+3：叔叔不存在或为黑色 –> 旋转 + 变色
else
{
// 子情况2：右右 –> 左单旋
// g
// / \\
// u p
// \\
// c
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
// 子情况3：右左 –> 右左双旋
// g
// / \\
// u p
// /
// c
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break; // 调整完成，退出循环
}
}
}

// 情况5：最后保证根节点是黑色
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}

五.map 的模拟实现

map的底层结构就是红黑树，因此在 map 中直接封装一棵红黑树，然后将其接口包装下就行。

namespace hjq
{

template<class K, class V>
class map
{

// 仿函数 MapKeyOfT
// 作用：从 pair<K, V> 中取出键值 K
// 红黑树在比较时不知道存的是 Key 还是 pair，通过这个仿函数告诉它怎么取键

struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first; // 返回 pair 中的 key
}
};

public:

// 迭代器类型别名
// 注意：这里的 iterator 是红黑树的迭代器，map 直接复用
// typename 的作用：
// 编译到这里时，红黑树模板可能还没有实例化，编译器不认识
// RBTree<K, pair<K, V>, MapKeyOfT>::iterator 是类型还是静态成员？
// 加上 typename 告诉编译器：这是个类型，等实例化后再去查找

typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;

// begin()：返回指向第一个元素的迭代器
// 直接复用红黑树的 begin()

iterator begin()
{
return _t.begin();
}

// end()：返回指向末尾的迭代器
// 直接复用红黑树的 end()

iterator end()
{
return _t.end();
}

// insert：插入键值对
// 直接调用红黑树的 Insert 接口
// 返回值：pair<iterator, bool>
// first：指向插入节点（或已存在节点）的迭代器
// second：true 表示插入成功，false 表示键已存在

pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}

// operator[]：通过键访问对应的值
// 功能：
// 1. key 存在 –> 返回对应 value 的引用
// 2. key 不存在 –> 插入 <key, V()>（V() 是默认值），再返回 value 的引用
//
// 实现原理：
// 1. 用 make_pair(key, V()) 构造一个键值对（V() 是缺省值）
// 2. 调用 insert 尝试插入
// 3. 不管插入成功还是失败，都通过迭代器取出 value 返回

V& operator[](const K& key)
{
// make_pair(key, V()) 用 key 和 V 类型的默认值构造 pair
// V() 是缺省值，比如 int 是 0，string 是 ""
pair<iterator, bool> ret = insert(make_pair(key, V()));

// ret.first 是指向该键值对的迭代器
// ret.first->second 取出 value，返回引用
return ret.first->second;
}

private:

// 红黑树底层容器
// 模板参数：
// K：键的类型
// pair<K, V>：存储的数据类型
// MapKeyOfT：仿函数，从 pair 中取出键

RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}

六.set 的模拟实现

set 的底层为红黑树，只需在 set 内部封装一棵红黑树，就可以将该容器实现出来（参考 map）。

namespace hjq
{

template<class K>
class set
{

// 仿函数 SetKeyOfT
// 作用：从 K 中取出键值 K
// 对于 set 来说，数据本身 K 就是键，所以直接返回 key 本身

struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key; // set 中 key 就是数据本身
}
};

public:

// 迭代器类型别名
// 注意：typename 的作用是告诉编译器 iterator 是一个类型
// 因为编译到这里时，RBTree<K, K, SetKeyOfT> 可能还没有实例化
// 编译器不知道 ::iterator 是类型还是静态成员变量
// 加上 typename 让编译器等实例化后再去查找

typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

// begin()：返回指向第一个元素的迭代器
// 直接复用红黑树的 begin()
iterator begin()
{
return _t.begin();
}

// end()：返回指向末尾的迭代器
// 直接复用红黑树的 end()

iterator end()
{
return _t.end();
}

// insert：插入元素
// 直接调用红黑树的 Insert 接口
// 返回值：pair<iterator, bool>
// first：指向插入节点（或已存在节点）的迭代器
// second：true 表示插入成功，false 表示键已存在

pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key); // 底层调用红黑树的插入
}

// inorder：中序遍历
// 用于打印 set 中的所有元素（有序）

void inorder()
{
_t.InOrder();
}

private:

// 红黑树底层容器
// 模板参数：
// K：键的类型
// K：存储的数据类型（set 中数据和键是同一个类型）
// SetKeyOfT：仿函数，从数据中取出键（直接返回自身）
RBTree<K, K, SetKeyOfT> _t;
};
}