关联容器底层：红黑树的特性与平衡机制

红黑树5条性质：

1. 每个节点红色或黑色
2. 根节点黑色
3. 叶节点(NIL)黑色
4. 红色节点的两个子节点都是黑色(不能有连续红色)
5. 任意节点到其所有叶节点的路径上黑色节点数量相同

插入修复：插入节点标红，若父节点为红需修复——检查叔叔节点颜色：红色→变色+上溢；黑色→旋转(LL/RR/LR/RL)。最多2次旋转，O(log n)。

删除修复：删除黑色节点破坏性质5，通过双黑节点处理——兄弟为红则转为黑，兄弟为黑则看侄子颜色决定旋转/变色。O(log n)，最多3次旋转。

为什么选红黑树而非AVL树： | 特性 | 红黑树 | AVL树 | |------|--------|-------| | 平衡度 | 近似平衡(最长路径≤2×最短路径) | 严格平衡(高度差≤1) | | 插入旋转 | 最多2次 | 最多O(log n)次 | | 删除旋转 | 最多3次 | 可能O(log n)次 | | 查找速度 | 略慢(最大高度2log(n+1)) | 更快(log n) | | 适用场景 | 插入删除频繁 | 查找远多于修改 |

STL map/set选择红黑树因为通用容器插入/删除/查找都需要较好的折中性能。C++11以后unordered_map用于哈希表场景。