treemap 和 treeset 底层采用红黑树而非 avl 树，因其在插入/删除开销与查询性能间取得更优平衡：红黑树调整成本低、内存占用小、实现简洁，更适配 java 集合高频增删的通用场景。
Java 集合中，TreeMap 和 TreeSet 底层都基于红黑树实现，而非 AVL 树。这不是偶然选择，而是由两种树在插入/删除开销与查询稳定性之间的实际权衡决定的。
平衡标准不同，直接影响维护成本
AVL 树要求每个节点左右子树高度差绝对值 ≤ 1，属于严格高度平衡；红黑树则通过颜色约束保证：任意路径上黑节点数相等，且最长路径不超过最短路径的两倍，属于近似平衡。
这意味着：
- AVL 树高度更低，最坏查找为 O(log n)，且常数更小，查询略快
- 但每次插入或删除后，AVL 树可能需向上回溯多层、多次旋转（最坏 O(log n) 次）来恢复平衡
- 红黑树允许局部“失衡”，插入最多 2 次旋转 + 若干着色，删除最多 3 次旋转，整体调整开销显著更低
Java 集合操作以增删为主，红黑树更适配
TreeMap/TreeSet 在实际使用中，并非只读结构。频繁的 put()、remove()、迭代中修改等场景很常见，尤其在中间件、缓存、配置管理等模块中。
例如：
- 一个按时间戳排序的事件队列，持续
put()新事件 +remove()过期事件 - 权限系统中动态增删角色映射，需反复调用
TreeSet.add()和.remove()
这些操作若落在 AVL 树上，旋转链过长会明显拖慢吞吐量；而红黑树用少量结构扰动换来了更平滑的响应延迟。
内存与实现复杂度也是现实考量
AVL 节点必须显式存储 height 字段（哪怕只占 4 字节），而红黑树只需 1 bit 表示颜色（通常复用已有字段的低位）。在海量节点场景下，内存放大效应不可忽视。
此外：
- 红黑树的插入修复逻辑虽分支多，但每种 case 的处理固定、可预测，JVM 易于优化
- AVL 的平衡因子更新和旋转触发条件更敏感，边界 case 更多，调试与验证成本更高
- OpenJDK 的 TreeMap 实现已高度成熟，兼顾了并发友好性（如
subMap的视图安全）与单线程性能
不是谁“更好”，而是谁“更合适”
AVL 树在数据库索引、静态词典等写入极少、查询极重的场景仍有价值；但 Java 集合的设计哲学是通用性与平均性能优先——它不假设你只读不写，也不预设数据完全静态。红黑树在查询够快、增删够稳、实现够简、内存够省四方面取得了最佳交集。
所以 JDK 没选 AVL，不是因为它不够强，而是因为红黑树更贴合集合变量的真实生命周期。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
