一、红黑树的概念
红黑树是自平衡二叉搜索树，通过节点颜色（红 / 黑）和严格的规则约束，保证任意根到叶子的路径长度差不超过 2 倍，实现近似平衡，避免普通二叉搜索树退化为链表。
1.1 红黑树的规则（必须牢记）
- 每个节点非红即黑；
- 根节点必须是黑色；
- 红色节点的子节点必须全为黑色（禁止连续红节点）；
- 任意节点到其所有 NULL 叶子节点的路径，黑色节点数量相同（简称'黑高一致'）。
1.2 为什么最长路径不超过最短路径 2 倍？
- 最短路径：全黑节点路径，黑高为
bh； - 最长路径：黑红交替路径，长度为
2*bh； - 结论：任意路径长度
bh ≤ h ≤ 2*bh，保证了红黑树的近似平衡。
1.3 红黑树的效率优势
- 时间复杂度：增删查改均为
O(logN)（与 AVL 树同级）； - 性能优势：插入 / 删除时旋转次数更少（AVL 树要求严格平衡，红黑树仅'近似平衡'），实际工程中（如 STL map/set）更常用。
二、红黑树的实现
2.1 红黑树的结构定义
#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 {
using Node = RBTreeNode<K, V>;
public:
// 插入接口
bool Insert(const pair<K, V>& kv);
// 中序遍历（验证二叉搜索树特性）
void InOrder() { _InOrder(_root); cout << endl; }
// 查找接口
Node* Find(const K& key);
// 获取树的大小
int Size() { return _Size(_root); }
// 获取树的高度
int Height() { return _Height(_root); }
private:
// 私有递归函数
void _InOrder(Node* root);
int _Size(Node* root);
int _Height(Node* root);
// 旋转函数（核心操作）
void RotateL(Node* parent); // 左旋转
void RotateR(Node* parent); // 右旋转
// 验证辅助函数
bool _IsValidRBTree(Node* root, int blackCount, int& refBlackCount);
private:
Node* _root = nullptr;
};
2.2 核心操作：旋转函数
旋转是红黑树维护平衡的核心，分为左旋转和右旋转，需保证旋转后仍符合二叉搜索树规则。
// 左旋转：以 parent 为旋转点，右孩子上位
void RotateL(Node* parent) {
Node* subR = parent->_right; // 失衡节点的右孩子（新根）
Node* subRL = subR->_left; // 新根的左子树（需要转移）
Node* pParent = parent->_parent; // 失衡节点的父节点
// 1. 转移 subRL：挂到 parent 的右子树
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
// 2. 父节点降级：parent 作为 subR 的左孩子
subR->_left = parent;
parent->_parent = subR;
// 3. 链接新根到原父节点
if (pParent == nullptr) {
_root = subR;
subR->_parent = nullptr;
} else {
if (pParent->_left == parent) pParent->_left = subR;
else pParent->_right = subR;
subR->_parent = pParent;
}
}
// 右旋转：以 parent 为旋转点，左孩子上位
void RotateR(Node* parent) {
Node* subL = parent->_left; // 失衡节点的左孩子（新根）
Node* subLR = subL->_right; // 新根的右子树（需要转移）
Node* pParent = parent->_parent; // 失衡节点的父节点
// 1. 转移 subLR：挂到 parent 的左子树
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
// 2. 父节点降级：parent 作为 subL 的右孩子
subL->_right = parent;
parent->_parent = subL;
// 3. 链接新根到原父节点
if (pParent == nullptr) {
_root = subL;
subL->_parent = nullptr;
} else {
if (pParent->_left == parent) pParent->_left = subL;
else pParent->_right = subL;
subL->_parent = pParent;
}
}
2.3 核心操作：插入函数
- 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的 4 条规则。
- 如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树插入，新增黑色结点就破坏了规则 4，规则 4 是很难维护的。
- 非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束。
- 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则 3。进一步分析，c 是红色，p 为红，g 必为黑，这三个颜色都固定了，关键的变化看 u 的情况，需要根据 u 分为以下几种情况分别处理。
说明：下图中假设我们把新增结点标识为 c(cur)，c 的父亲标识为 p(parent)，p 的父亲标识为 g(grandfather), p 的兄弟标识为 u(uncle)。
2.2.2 情况 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 的左还是右，都是上面的变色处理方式。
2.2.3 情况 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 的父亲是黑色还是红色或者空都不违反规则。
2.2.4 情况 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 的父亲是黑色还是红色或者空都不违反规则。
2.2.5 插入核心问题总结
关键看 u(叔叔)，p(父亲) 和 g(爷爷) 是固定的，方向不一定固定分两种情况，if(情况 1)、else(情况 2)，但颜色一定是固定的。
u(叔叔)存在且为红，就可以和p(父亲)一起分担颜色，把u(叔叔)和p(父亲)变黑，g(爷爷)变红- 单旋情况下：
u(叔叔)不存在 /u(叔叔)存在且为黑，u(叔叔)没办法分担只能变色，让p(父亲)变黑为顶 - 双旋情况下：
u(叔叔)不存在 /u(叔叔)存在且为黑，u(叔叔)没办法分担只能变色，让c(新节点)变黑为顶
2.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;
}
}
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) {
// 分两种情况：1.叔叔在左边 2.叔叔在右边
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
// 叔叔在右边
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
// 叔叔存在且为红色（变色）
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上处理，最坏结果处理到根
cur = grandfather;
parent = cur->_parent;
} else {
// 叔叔不存在，或存在且为黑（旋转 + 变色）
if (cur == parent->_left) {
// c 在父亲左边，构成直线，只单旋一次
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// c 在父亲右边，构成折线，需要双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else {
// 叔叔在左边（类似上列代码）
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; // _root 节点必为 BLACK
return true;
}
2.4 查找红黑树
按二叉搜索树逻辑实现即可，搜索效率为 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.5 遍历打印红黑树
/*public*/
void InOrder() {
_InOrder(_root);
cout << endl;
}
/*private*/
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
2.6 红黑树高度及大小
/*public*/
int Size() {
return _Size(_root);
}
int Height() {
return _Height(_root);
}
/*private*/
int _Height(Node* root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int _Size(Node* root) {
if (root == nullptr) return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}