适合初学者首次了解红黑树概念，C++STL容器set

红黑树的基本概念

红黑树是一种自平衡的二叉搜索树，通过约束节点颜色和结构调整规则，确保最坏情况下操作时间复杂度为 O(log n)。其核心特性如下：

红黑树的五大规则

1. 根节点为黑色。
2. 所有叶子节点（NIL节点）为黑色：NIL节点是假想的空节点，通常省略图示。
3. 红色节点的子节点必须为黑色：禁止连续红色节点，避免路径过长。
4. 任意节点到后代叶子节点的路径包含相同数量的黑色节点：保证黑高一致，维持平衡。
5. 新插入节点默认为红色：减少破坏规则的概率，便于后续调整。

维持平衡的操作

• 变色：通过切换节点颜色（红↔黑）局部修复冲突。
• 旋转：
  • 左旋：将右子节点提升为父节点，原父节点成为其左子树。
  • 右旋：将左子节点提升为父节点，原父节点成为其右子树。

---

set 容器的特性与用法

基本特性

• 自动排序：基于红黑树实现，元素按升序排列（默认）。
• 唯一性：不允许重复元素，插入重复值时自动忽略。

常用操作

#include <set>
set<int> s;

• 插入元素

  s.insert(10);  // 插入值为10的元素
  

• 查找元素

  //方式一：
  auto it = s.find(10);
  if (it != s.end()) {  // 判断是否找到
      cout << *it << endl;
  }
  
  //方式二：迭代器
  set<int>: : iterator it;
  for (it = s.begin(); it != s.end(); it++)
  	cout << *it << " "；
  

  find()函数返回的是元素地址

        找到了：find() 返回有效迭代器(地址)，不等于 end()

        没找到：find() 返回 end()

• 删除元素

  s.erase(10);       // 删除值为10的元素
  s.erase(it);       // 通过迭代器删除
  

  也可以删除一个区间

  //删除一个区间
  auto s.start=(你要删除的区间首地址)
  auto s.end=(尾地址)
  s.erase(s.start,s,end);

• 遍历集合

  for (auto it = s.begin(); it != s.end(); ++it) {
      cout << *it << " ";
  }
  

---

unordered_set 的对比

核心差异

• 无序性：基于哈希表实现，元素无序存储。
• 性能：
  • 插入、删除、查找的平均时间复杂度为 O(1)（最坏情况 O(n)）。
  • 比 set 更快，但牺牲了顺序性。

适用场景

• 需要快速去重且不关心顺序时（如统计词频）。
• 算法竞赛中优先选择 unordered_set 以优化速度。

#include <unordered_set>
unordered_set<int> us;
// 操作接口与set基本一致