1. 红黑树基础介绍
红黑树是二叉搜索树的一种，通过颜色标记（红或黑）和特定规则维持平衡，确保操作时间复杂度稳定。核心特性包括：
- 每个节点有颜色属性（红色或黑色）。
- 根节点必须为黑色。
- 红节点的子节点必须为黑色（即无连续红节点）。
- 从任一节点到其子孙叶子的所有路径中，黑色节点数目相同（称为黑色高度）。
- 新插入的节点通常为红色，然后通过旋转和重新着色调整平衡。
这些规则保证树的高度近似对数级，使得查找、插入和删除操作的时间复杂度为 $O(\log n)$。例如，树的高度 $h$ 满足 $h \leq 2\log(n+1)$，其中 $n$ 是节点数。
2. 红黑树在C++中的应用：封装map和set
在STL中，std::map和std::set通常基于红黑树实现：
std::set：存储唯一键的集合，支持高效查找和排序。它使用红黑树存储键值（无额外值）。std::map：存储键值对（key-value pairs），键唯一，支持基于键的快速访问。它扩展红黑树来关联键和值。
封装的核心思想是：红黑树作为底层数据结构，提供平衡性和高效操作；map和set通过模板类封装，添加特定接口（如 insert()、find()）。优势包括：
- 性能稳定：所有操作（插入、删除、查找）平均和最坏情况均为 $O(\log n)$。
- 有序性：树结构自然支持排序，迭代器按顺序遍历元素。
- 内存效率：节点存储最小信息（键、值指针、颜色等）。
与其他结构（如哈希表）相比，红黑树更适合需要排序和范围查询的场景，但可能稍慢于哈希表的平均 $O(1)$ 查找。
3. 封装实现详解
下面通过简化代码展示如何使用红黑树封装 map 和 set。我们定义一个通用红黑树模板，然后特化用于 set 和 map。
3.1 红黑树节点和基础结构
首先，定义红黑树节点类。节点存储键、可选值（用于 map）、颜色和指针。
enum Color { RED, BLACK };
template <typename Key, typename Value = void> // Value默认为void，用于set
class RBTreeNode {
public:
Key key;
Value value; // 仅当Value非void时有效
RBTreeNode* left;
RBTreeNode* right;
RBTreeNode* parent;
Color color;
RBTreeNode(Key k, Value v = Value(), Color c = RED)
: key(k), value(v), left(nullptr), (), (), (c) {}
};
