C++如何实现一个红黑树_C++ STL中map和set的底层数据结构

在C++中，map 和 set 的底层数据结构是通过红黑树实现的。红黑树是一种自平衡的二叉搜索树，能够在插入、删除和查找操作中保持对数时间复杂度，从而保证高效的数据访问。

红黑树的基本性质

红黑树满足以下五条性质，确保树的高度始终保持在 log(n) 级别：

• 每个节点是红色或黑色。
• 根节点是黑色。
• 所有叶子（NULL 节点）被视为黑色。
• 如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质共同作用，使得红黑树在动态操作中能够自动调整结构，避免退化为链表。

C++中实现红黑树的关键组件

要手动实现一个红黑树，需要定义节点结构、基本操作（插入、删除、旋转）以及修复机制来维护红黑性质。

立即学习“C++免费学习笔记（深入）”；

1. 节点结构定义：

每个节点包含值、颜色、左右子节点指针和父节点指针。

enum Color { RED, BLACK };
<p>template<typename T>
struct RBNode {
T value;
Color color;
RBNode<em> left;
RBNode</em> right;
RBNode* parent;</p><pre class='brush:php;toolbar:false;'>RBNode(const T& val) : value(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}

};

2. 插入后的修复操作：

插入新节点后，默认设为红色。若破坏了红黑性质（如父节点也为红色），需通过变色和旋转来修复。

主要情况包括：

疯狂翻译师App

支持屏幕、图片、视频字幕、文档、漫画等多种翻译，准确率高，操作简单。

104

查看详情

• 叔节点为红色：变色并上移处理祖父节点。
• 叔节点为黑色，且当前节点为右孩子：左旋。
• 叔节点为黑色，且当前节点为左孩子：右旋并变色。

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 <map>
#include <set>
std::map<int, std::string> m;
m[1] = "one";
m[2] = "two";
<p>std::set<int> s;
s.insert(10);
s.insert(20);</p>

这些操作背后都会触发红黑树的插入逻辑，并自动完成平衡调整。

为什么选择红黑树而不是其他平衡树？

相比AVL树，红黑树牺牲了一定的平衡性（最大高度略高），但换来更少的旋转操作，更适合频繁插入删除的场景。

• 插入最多两次旋转。
• 删除最多三次旋转。
• 综合性能优秀，适用于通用容器设计。

基本上就这些。理解红黑树有助于深入掌握STL容器的行为特性，尤其是在分析性能瓶颈时更有底气。