平衡二叉树：AVL与红黑树终极对比
一、为什么需要平衡二叉树
普通二叉搜索树 BST 有致命缺陷：插入有序数据会退化成单链，从 O (logn) 退化到 O (n)，查找效率暴跌。
举例：插入 1,2,3,4,5BST 会变成一条斜链表，失去二分优势。解决方案：平衡二叉树，强制左右子树高度差不能过大，维持 O (logn) 稳定效率。
二、AVL 平衡二叉树核心特性
1. 定义
AVL 树是严格平衡二叉搜索树任意节点左右子树高度差绝对值 ≤ 1这个高度差称为平衡因子。
2. 平衡因子规则
平衡因子 = 左子树高度 - 右子树高度只能取值：-1、0、1
3. 失衡四种旋转修复
插入节点导致失衡，通过旋转恢复平衡：
- LL 型：右单旋
- RR 型：左单旋
- LR 型：先左后右双旋
- RL 型：先右后左双旋
4. AVL 优缺点
优点：高度严格平衡，查询最快缺点：插入删除旋转次数多、维护代价大，工程很少直接用
三、红黑树核心概念（面试重中之重）
1. 是什么
红黑树是弱平衡二叉搜索树不追求严格平衡，用颜色规则约束，近似平衡。C++map/set、JavaTreeMap、Linux 内核 底层都是红黑树。
2. 红黑树五大铁律（必背）
- 每个节点红色 或 黑色
- 根节点必须是黑色
- 叶子节点（空节点）都是黑色
- 红色节点的两个子节点必须都是黑色（不能红红相连）
- 从任意节点到其所有叶子节点，经过的黑色节点数量相同
3. 核心特点
- 最长路径 ≤ 最短路径的 2 倍
- 近似平衡，不用频繁旋转
- 插入删除只有变色 + 少量旋转，维护成本低
- 查找、插入、删除稳定维持O(logn)
四、红黑树 vs AVL 树 面试对比
表格
| 对比项 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡程度 | 严格平衡 | 弱平衡 |
| 平衡约束 | 高度差≤1 | 颜色五条规则 |
| 维护代价 | 旋转多、开销大 | 变色 + 少量旋转、开销小 |
| 查询性能 | 略快 | 稍慢一点 |
| 插入删除 | 慢 | 更快 |
| 工程应用 | 几乎不用 | map/set、内核、数据库广泛用 |
面试一句话总结：查询多用 AVL，频繁增删用红黑树；工程实际全用红黑树。
五、为什么 STL map/set 选用红黑树
- 增删操作远多于查询，红黑树维护成本更低
- 不用严格高度平衡，减少旋转次数
- 性能稳定、实现成熟、适合底层容器封装
六、面试高频问答整理
BST 为什么会退化？有序插入变成单链表，效率从 O (logn) 降到 O (n)。
AVL 和红黑树区别？AVL 严格平衡、查询快、维护贵；红黑树弱平衡、增删快、工程主流。
红黑树为什么不用高度平衡？用颜色规则间接约束路径长度，减少旋转，提升增删效率。
红黑树五条规则必须熟记，面试常手写口述。
七、今日总结
- 普通 BST 会退化，引出平衡二叉树
- AVL 严格平衡，靠平衡因子 + 旋转维护
- 红黑树弱平衡，靠 5 条颜色规则约束
- 红黑树是 C++ map/set 底层，面试必问
- 记住 AVL 与红黑树选型与优缺点对比