C++标准库set/multimap源码分析：从哈希表到红黑树的实现细节

1. 数据结构选择依据

• 哈希表：适用于$O(1)$平均时间复杂度的场景，但存在哈希冲突、无序存储、最坏情况$O(n)$等问题
• 红黑树：保证$O(\log n)$最坏时间复杂度，且天然有序（适合范围查询），满足关联容器核心需求
• 设计决策：
  • set/multimap需有序性 → 选择红黑树
  • unordered_set/unordered_map需快速访问 → 选择哈希表

2. 红黑树核心性质

红黑树通过以下约束保持平衡： $$ \begin{cases} \text{1. 节点为红或黑} \ \text{2. 根节点必黑} \ \text{3. 叶节点（NIL）必黑} \ \text{4. 红节点的子节点必黑} \ \text{5. 任意节点到叶子的路径含相同黑节点数} \end{cases} $$ 这些约束确保树高$h \leq 2\log_2(n+1)$，保证操作复杂度稳定在$O(\log n)$。

3. 关键操作实现细节

插入操作

// 伪代码示意（参考libstdc++实现）
void insert(Node* z) {
  // 标准BST插入（初始红色）
  Node* y = nullptr; 
  Node* x = root;
  while (x != NIL) {
    y = x;
    x = (z->key < x->key) ? x->left : x->right;
  }
  z->parent = y;
  // ... 插入节点

  // 红黑树修复（处理双红冲突）
  while (z->parent->color == RED) {
    if (uncle(z)->color == RED) {
      // 情况1：叔节点红 → 重新着色
      recolor(z);
    } else {
      // 情况2/3：叔节点黑 → 旋转+着色
      if (z == parent(z)->right) 
        left_rotate(parent(z));
      right_rotate(grandparent(z));
    }
  }
  root->color = BLACK; // 根始终黑
}

• 旋转操作：通过左旋/右旋调整结构
  • 左旋：$x$为轴，$y=x\rightarrow right$，$y$成为子树新根
  • 右旋：对称操作

删除操作

void erase(Node* z) {
  Node* y = z;
  Color orig_color = y->color;
  Node* x;

  if (z->left == NIL) {
    // ... 单子树处理
  } else if (z->right == NIL) {
    // ... 单子树处理
  } else {
    y = minimum(z->right); // 找后继
    orig_color = y->color;
    x = y->right;
    // ... 节点替换
  }

  if (orig_color == BLACK) 
    fix_deletion(x); // 修复黑高失衡
}

• 删除后修复需处理：
  • 兄弟节点为红 → 旋转后转兄弟黑
  • 兄弟节点为黑且侄子节点红 → 旋转+重新着色
  • 兄弟节点为黑且侄子节点黑 → 递归向上调整

4. 源码级优化技巧

• 节点结构：包含父指针、颜色标志、左右子节点

  struct Rb_node {
    Color color;
    Value data;
    Rb_node* parent;
    Rb_node* left;
    Rb_node* right;
  };
  

• NIL节点复用：所有叶节点共享静态NIL，减少内存占用
• 迭代器优化：
  • 支持$O(1)$的++/--操作（通过中序遍历指针）
  • 实现范围查询：lower_bound()利用树的有序性

5. 性能对比

6. 设计哲学

• 稳定性优先：红黑树的最坏情况保证符合C++标准对关联容器的要求
• 空间换时间：每个节点额外存储颜色和父指针（约$20%$~$30%$空间开销）
• 扩展性：相同红黑树实现可支撑map/set/multimap/multiset

注：实际源码（如libstdc++的stl_tree.h）包含更多边界处理，但核心逻辑遵循上述原则。红黑树的平衡性使其成为有序关联容器的黄金标准，在数据库索引、文件系统等领域有广泛应用。