1. 概述
本文将介绍平衡二叉搜索树（Balanced Binary Search Tree）的基本概念，并探讨树的高度（Height）问题。我们还会通过数学推导说明：在拥有 n 个节点的平衡二叉树中，其高度始终为 **O(log(n))**。
我们假设你已经具备二叉树和二叉搜索树（BST）的基础知识，因此不会对这些基础内容做过多解释。重点在于理解平衡树的性质，以及为何其高度对操作效率至关重要。
2. 树的高度
树的高度是指从根节点到最远叶子节点的最长路径长度（边数）。例如：
上图中每个节点标注了其高度值。根节点到最远叶子节点的路径长度为 4，因此这棵树的高度为 4。
✅ 计算方式
要计算树的高度，通常采用后序遍历的方式：
int height(TreeNode root) {
if (root == null) return -1; // 叶子节点的高度为 -1
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return 1 + Math.max(leftHeight, rightHeight);
}
⚠️ 为什么树的高度很重要？
BST 的许多操作（如查找、插入、删除）的时间复杂度为 **O(h)**，其中 h 是树的高度。理想情况下，h = O(log n)，但最坏情况下 h = O(n)（例如退化成链表），这会极大降低效率。
因此，我们引入“平衡”机制，确保树的高度始终保持在 log n 级别。
3. 平衡二叉树
一个二叉树是平衡的，当且仅当对于每个节点，其左右子树的高度差不超过 1。
如果某个节点的某个子节点不存在，则该子节点的高度视为 -1。
来看一个例子：
左边的树不平衡，因为某些节点的左右子树高度差超过 1。右边的树是平衡的，所有节点的子树高度差都不超过 1。
✅ 平衡 BST 的例子
常见的平衡 BST 实现包括：
- 红黑树（Red-Black Tree）
- AVL 树
- B 树
在 Java 中，TreeMap 和 TreeSet 的底层实现就是基于红黑树。
3.1 平衡 BST 的高度
**在有 n 个节点的平衡 BST 中，我们可以保证查找操作的时间复杂度为 O(log n)**。
因为平衡 BST 的高度 h = O(log n)，所以查找、插入、删除等操作的时间复杂度都控制在 O(log n) 级别。
4. 平衡树节点数的下界
为了证明 h = O(log n)，我们需要从另一个角度出发：给定高度 h，求出平衡 BST 所需的最小节点数 Ω_h。
我们通过数学归纳法来证明：
对于高度为 h 的平衡 BST，其最小节点数 Ω_h > 2^(h/2 - 1)
4.1 归纳基础
- 当 h = 1 时，最小节点数为 2（根 + 一个子节点），满足 2 > 2^(1/2 - 1) ≈ 0.707
- 当 h = 2 时，最小节点数为 4，也满足 4 > 2^(2/2 - 1) = 1
4.2 归纳步骤
假设对于所有 h < k 的情况，Ω_h > 2^(h/2 - 1) 成立。
对于 h = k 的情况，一棵高度为 h 的平衡 BST 至少包含：
- 一个根节点
- 一个高度为 h - 1 的子树
- 一个高度为 h - 2 的子树（否则不满足平衡条件）
所以有：
Ω_h = 1 + Ω_{h-1} + Ω_{h-2}
根据归纳假设：
Ω_{h-2} > 2^{(h-2)/2 - 1}
=> Ω_h > 2 * 2^{(h-2)/2 - 1} = 2^{h/2 - 1}
✅ 得证！
5. 使用大 O 表示法分析平衡树高度
我们已经知道：
Ω_h > 2^{h/2 - 1}
=> log(Ω_h) > h/2 - 1
=> h < 2 * log(Ω_h) + 2
又因为 Ω_h ≤ n（平衡树中节点数最少为 Ω_h），所以：
h < 2 * log(n) + 2
=> h = O(log n)
✅ 结论：平衡 BST 的高度始终为 O(log n)
6. 小结
本文重点讲解了：
- 平衡二叉树的定义
- 树的高度的计算方法
- 平衡 BST 的优势在于其高度始终为 O(log n)
- 通过数学归纳法证明了平衡树的最小节点数下界
- 最终推导出平衡树的高度为 O(log n)
理解这些内容对掌握高效数据结构（如红黑树、AVL 树）至关重要。在实际开发中，使用 Java 的 TreeMap 或 TreeSet 时，其底层的红黑树正是基于这些原理实现的。✅
⚠️ 踩坑提醒：在使用 BST 时，若插入顺序不当导致树不平衡，性能会急剧下降，务必使用平衡 BST 或自平衡结构。