红黑树如何通过旋转确保 TreeMap 插入操作维持 $O(log n)$ 平衡？

本文共计844个文字，预计阅读时间需要4分钟。

红黑树的平衡代价本质上是可控的局部调整，不是每次插入都旋转，也不是全树重平衡。TreeMap底层用红黑树实现，其所能稳定维护的时间复杂度为O(log+n)。关键在于：

为什么插入默认设为红色？

这是降低平衡代价的第一步设计选择：

• 若插入黑色节点，会直接破坏“从根到所有叶子路径黑节点数相等”（性质5），导致整条路径黑高+1，后续需全局重调，代价太高；
• 插入红色节点只可能违反“无连续红节点”（性质4），问题局限在父子三代内（z/p/g/u），修复范围小、可预测；
• 即使触发修复，也仅影响祖父层及以上的局部子树，其余分支完全不动。

真正耗时的操作：旋转与变色的组合策略

TreeMap 插入后是否需要调整，取决于父节点颜色。只有当父节点为红色时才启动修复，分三类典型情形：

• 叔节点为红（Case 1）：仅变色（p/u→黑，g→红），不旋转；若 g 是根，最后再涂黑。操作为 O(1)，但可能递归向上继续检查 —— 实际中平均递归深度
• 叔节点为黑，且新节点是内侧子孙（LR / RL 型）：先单旋父节点，再单旋祖父节点，共两次旋转 + 一次变色（新根变黑、原根变红）；
• 叔节点为黑，且新节点是外侧子孙（LL / RR 型）：仅一次旋转（右旋或左旋祖父）+ 一次变色（p→黑，g→红），结构立即收敛。

TreeMap 的实际开销远低于理论最坏情况

Java 的 TreeMap 实现做了多项优化，进一步压缩平衡代价：

• 使用非递归循环完成修复，避免方法调用栈开销；
• 所有旋转均在指针层面完成（修改 left/right 引用），无内存分配；
• 变色仅改一个字段（color 字段），现代 JVM 对该字段访问极快；
• 统计表明：随机插入下，约 75% 的插入无需任何调整；约 20% 仅需变色；仅约 5% 触发单次旋转；双旋概率低于 0.5%。

和 AVL 树对比：代价换来的实用性

AVL 树要求左右子树高度差 ≤ 1，每次插入平均引发 0.25 次旋转，但最坏需从叶子回溯到根做多次平衡；而红黑树允许更宽松的高度比（最长路径 ≤ 2×最短路径），因此：

• 插入时平均旋转次数更低（≈ 0.15 次）；
• 删除时调整更少，更适合读写混合场景；
• TreeMap 在业务系统中频繁增删 key（如会话管理、定时任务索引）时，整体吞吐更稳。