博主的舍友面试遇到老师提问这个问题，我简单思考后询问AI，发现和我的答案不同，看后觉得很有意思，便整理成文章以供学习，希望能帮助到大家。
一、什么是平衡二叉树？
1.1 二叉搜索树的问题
普通的二叉搜索树（BST）在极端情况下会退化成链表。例如按递增顺序插入 1, 2, 3, 4, 5：
1
\
2
\
3
\
4
\
5
此时树的高度为 4（边数），查找操作的时间复杂度从理想的 退化到 。
1.2 平衡二叉树的定义
平衡二叉树是一种特殊的二叉搜索树，它通过平衡约束保证树的高度始终维持在 级别。最常见的平衡二叉树包括：
- AVL树：任何节点的左右子树高度差不超过 1
- 红黑树：通过颜色标记保证黑高平衡
本文以 AVL树 为例进行讨论。
1.3 树的高度定义（重要！）
在讨论高度之前，必须明确定义。树的高度有两种常见定义：
| 定义 | 空树高度 | 单节点高度 | 满二叉树（3个节点）高度 |
|---|---|---|---|
| 边数定义 | -1 | 0 | 1 |
| 节点数定义（层数） | 0 | 1 | 2 |
本文采用 边数定义（算法导论等教材的标准）：
- 空树的高度为 -1
- 只有一个根节点的树高度为 0
- 树的高度 = 根节点到最远叶子节点的边数
如果面试或考试中遇到，建议先和对方确认定义。两种定义可以相互转换：节点数高度 = 边数高度 + 1。
二、节点数与高度的关系
2.1 给定高度 ，求节点数的范围
最小节点数（最“瘦”的 AVL 树）
高度为 的 AVL 树，要满足平衡条件，节点数不能太少。递推关系如下：
初始条件：
逐项计算得到：
| -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 4 | 7 | 12 | 20 | 33 | 54 |
最大节点数（满二叉树）
当树是完美平衡时，节点数最多：
验证：
- （单节点）： ✅
- （根+一层）： ✅
注意：如果采用节点数定义（层数），公式变为 ，其中 。
节点数范围
因此，给定高度 ，节点数 满足：
2.2 给定节点数 ，求高度的范围
最小高度（树尽量填满）
当树尽可能接近完全二叉树时，高度最小。有两种等价的写法：
或者：
验证： 时，，正确。
常见疑惑：向上取整减1 和 向下取整+1 一样吗？
答案：不一样。 和 通常不相等。但在最小高度公式中，，这是一个特例，不是通用规律。
最大高度（树尽量瘦）
当树尽量“瘦高”但仍满足 AVL 条件时，高度最大。最大高度是满足 的最大 ：
小 的完整对照表（边数定义）
| 说明 | |||
|---|---|---|---|
| 0 | -1 | -1 | 空树 |
| 1 | 0 | 0 | 单节点 |
| 2 | 1 | 1 | 两个节点只能形成一层 |
| 3 | 1 | 1 | 高度2需要至少4个节点，所以3个节点最高只能到高度1 |
| 4 | 2 | 2 | 刚好达到高度2的最小节点数 |
| 5 | 2 | 2 | 高度3需要至少7个节点 |
| 6 | 2 | 2 | 高度3需要至少7个节点 |
| 7 | 2 | 3 | 刚好达到高度3的最小节点数 |
| 8 | 3 | 3 | 高度4需要至少12个节点 |
| 9 | 3 | 3 | 高度4需要至少12个节点 |
| 10 | 3 | 3 | 高度4需要至少12个节点 |
| 11 | 3 | 3 | 高度4需要至少12个节点 |
| 12 | 3 | 4 | 刚好达到高度4的最小节点数 |
如果你采用节点数定义（层数），只需将所有高度值加1即可。
三、近似公式与 1.44 的来源
3.1 渐近近似
对于较大的 ，AVL 树的高度范围可以近似为：
- 最小高度：
- 最大高度：
也就是说，AVL 树的高度最多比完全二叉树高出约 44%。
3.2 为什么是 1.44？
这个系数来自 AVL 树最小节点数的递推与斐波那契数列的关系。
第一步：递推近似
忽略递推中的 ：
这与斐波那契数列的形式相同。
第二步：斐波那契数列与黄金分割比
斐波那契数列的定义是：
斐波那契数列的通解是比内公式：
其中 ，是黄金分割比。
当 较大时，第二项趋近于 0，所以：
因此，对于 AVL 树：
第三步：反解高度
由近似公式：
两边取自然对数：
忽略常数项（当 很大时， 远大于常数），得到：
补充说明：为什么上面是 ，这里变成了 ？
因为严格推导得到的是 。常数 在渐近分析中不影响系数，因此通常简写为 。我们最终关心的是 与 的比例关系，常数项可以忽略。
第四步：换成以 2 为底的对数
我们的目标是找到 与 的比例关系。因此设：
其中 就是我们要计算的系数。
将 代入：
由于 ，代入得：
两边同时除以 （ 时 ）：
因此：
代入数值：
第五步：结论
3.3 补充：斐波那契数列与黄金分割比的关系
为什么斐波那契数列会涉及 ？
从递推 出发，假设比值趋于常数 ，即 ，代入得：
两边除以 ：
当 很大时，，所以：
这正是黄金分割比满足的方程，因此 。所以任何形如 的递推，其解都会涉及 。
四、为什么 AVL 树的形状不唯一？
4.1 平衡条件的松弛性
AVL 树只要求左右子树高度差 ≤ 1，并没有要求形状唯一。因此，给定相同的节点集合，可以构造出多种不同的 AVL 树。
例如，节点集 {1, 2, 3} 可以构造：
- 形状 A：2 为根，1 和 3 分左右 → 完美平衡
- 形状 B：1 为根，2 为右孩子，3 为 2 的右孩子 → 平衡因子为 (0, 1, 0)，仍满足 AVL 条件
4.2 什么时候形状唯一？
只有当约束条件非常强时才会唯一，例如：
- 完全二叉树：给定 ，形状唯一
- 二叉搜索树 + 固定插入顺序：形状唯一（但顺序变则形状变）
平衡二叉树不属于这种情况。
五、常见疑惑解答
5.1 向上取整减1 和 向下取整+1 一样吗？
不一样。 和 通常不相等。例如 时，前者为 1，后者为 2。
但在最小高度公式中，，这是一个特例，不是通用规律。
5.2 节点数 时，公式 怎么处理？
这个公式是 给定高度求最大节点数，不是给定节点数求高度。当 时：
正确，单节点树最多有 1 个节点。
5.3 如果我采用节点数定义（层数），公式怎么变？
| 公式 | 边数定义（本文采用） | 节点数定义（层数） |
|---|---|---|
| 最大节点数 | ||
| 最小高度 | ||
| 关系 | – |
5.4 最小高度能写成 吗？
可以，但前提是采用节点数定义（层数）。如果你采用边数定义，最小高度就是 ，不需要加 1。
建议在文章开头明确你使用的定义，避免混淆。
六、总结
| 问题 | 结论 |
|---|---|
| AVL 树的高度范围 | （边数定义） |
| 为什么是 1.44 | 来自斐波那契递推与黄金分割比 ： |
| 形状是否唯一 | 否，平衡条件允许多种合法结构 |
| 两种高度定义如何转换 | 节点数高度 = 边数高度 + 1 |
七、参考资料
- AVL 树递推公式：
- 黄金分割比：
- 斐波那契比内公式：
