C++如何实现一个红黑树_C++ STL中map和set的底层数据结构
在C++中，map 和 set 的底层数据结构是通过红黑树实现的。红黑树是一种自平衡的二叉搜索树，能够在插入、删除和查找操作中保持对数时间复杂度，从而保证高效的数据访问。
红黑树的基本性质
红黑树满足以下五条性质，确保树的高度始终保持在 log(n) 级别：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 所有叶子（NULL 节点）被视为黑色。
- 如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质共同作用，使得红黑树在动态操作中能够自动调整结构，避免退化为链表。
C++中实现红黑树的关键组件
要手动实现一个红黑树，需要定义节点结构、基本操作（插入、删除、旋转）以及修复机制来维护红黑性质。
1. 节点结构定义：
每个节点包含值、颜色、左右子节点指针和父节点指针。
enum Color { RED, BLACK };
template
struct RBNode {
T value;
Color color;
RBNode left;
RBNode right;
RBNode* parent;
RBNode(const T& val) : value(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};
2. 插入后的修复操作：
插入新节点后，默认设为红色。若破坏了红黑性质（如父节点也为红色），需通过变色和旋转来修复。
主要情况包括：
- 叔节点为红色：变色并上移处理祖父节点。
- 叔节点为黑色，且当前节点为右孩子：左旋。
- 叔节点为黑色，且当前节点为左孩子：右旋并变色。
3. 左旋与右旋：
旋转是调整树结构的核心手段。
void rotateLeft(RBNode*& root, RBNode* x) {
RBNode* y = x->right;
x->right = y->left;
if (y->left != nullptr)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == nullptr)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
右旋类似，方向相反。
STL中的map和set如何使用红黑树
C++ STL 中的 std::map 和 std::set 通常基于红黑树实现（具体由编译器决定，但主流实现如GCC的libstdc++确实如此）。
- map 存储键值对（key-value），按键有序排列，查找、插入、删除平均时间复杂度为 O(log n)。
- set 存储唯一元素，同样有序，底层也是红黑树。
它们不支持随机访问，但提供有序遍历。由于红黑树的平衡性，性能稳定，适合频繁增删查的场景。
例如：
#include
这些操作背后都会触发红黑树的插入逻辑，并自动完成平衡调整。
为什么选择红黑树而不是其他平衡树？
相比AVL树，红黑树牺牲了一定的平衡性（最大高度略高），但换来更少的旋转操作，更适合频繁插入删除的场景。
- 插入最多两次旋转。
- 删除最多三次旋转。
- 综合性能优秀，适用于通用容器设计。
基本上就这些。理解红黑树有助于深入掌握STL容器的行为特性，尤其是在分析性能瓶颈时更有底气。
