红黑树在 C++ 标准库中是 std::map、std::set 等关联容器的底层实现（GCC libstdc++ 和 Clang libc++ 均采用红黑树），它是一种自平衡二叉搜索树，通过节点着色（红/黑）和局部旋转+变色操作，在 O(log n) 时间内保证插入、删除、查找的最坏性能。
红黑树的核心性质
理解实现前必须牢记五条不变性（即“红黑性质”）：
- 每个节点非红即黑
- 根节点是黑色
- 所有叶子（NIL 节点，通常用空指针或哨兵节点表示）是黑色
- 红色节点的两个子节点必须都是黑色（即不能有两个连续的红节点）
- 从任一节点到其每个叶子的所有路径上，包含相同数目的黑色节点（黑高一致）
关键操作：插入与修复
插入新节点默认为红色（避免直接破坏性质5），但可能违反性质4（出现红-红父子）。此时需根据父节点、叔节点颜色及位置关系分情况处理：
- 情况1：叔节点为红 → 父、叔染黑，祖父染红，再以祖父为当前节点向上修复
- 情况2：叔节点为黑，且当前节点是内侧插入（如父为左，当前为右） → 先对父节点左旋，转为外侧情形
- 情况3：叔节点为黑，且为外侧插入（如父为左，当前为左） → 父染黑，祖父染红，再对祖父右旋
三种情况均能在至多两次旋转 + 若干变色后恢复红黑性质。实际编码中常将“内侧→外侧”合并为统一的旋转预处理步骤。
立即学习“C++免费学习笔记（深入）”；
节点设计与内存管理
典型节点结构包含：key、value（对 map）、color（bool 或 enum）、left、right、parent 指针。STL 实现中常用 带父指针的三叉链表，便于回溯修复；部分精简实现会省略 parent，改用栈记录路径（但增加常数开销）。
为避免频繁 new/delete，现代实现（如 libstdc++）使用 std::allocator + 内存池管理节点，构造/析构由容器控制，不暴露裸指针给用户。
与标准库容器的对应关系
std::map 是红黑树的键值对映射，按 K 排序；std::set 是仅存 key 的集合；std::multimap 和 std::multiset 允许重复 key，插入时不检查等价性，仅依赖 lower_bound 定位插入位置。
所有操作时间复杂度均为 O(log n)，迭代器稳定（插入删除不使原有迭代器失效，除非指向被删节点），遍历结果严格升序（基于 operator 或自定义比较器）。
不复杂但容易忽略：红黑树不是唯一选择——C++20 后部分场景可用 std::unordered_map（哈希表，平均 O(1)）替代，但牺牲有序性和最坏 O(n) 查找；而红黑树提供确定性对数级性能和天然有序遍历能力，这是关联容器设计的根本权衡。
