1. 引言
平衡二叉树（Balanced Binary Tree）是二叉搜索树的一种优化形式，旨在提升查找效率。
在实际开发中，普通的二叉树结构在极端情况下（如插入有序数据）会导致退化为链表，查找效率从理想的 O(log n) 退化到 O(n)。为了解决这个问题，我们引入了平衡二叉树。
本文将重点介绍三种常见的平衡二叉树：
- AVL 树
- 红黑树（Red-Black Tree）
- 权重平衡树（Weight-Balanced Tree）
它们通过不同的平衡策略确保树的高度始终维持在 O(log n) 级别。
2. 二叉树与二叉搜索树
二叉树（Binary Tree） 是每个节点最多有两个子节点的树结构：左子节点和右子节点。
2.1. 二叉搜索树（Binary Search Tree, BST）
BST 是一种特殊的二叉树，其性质如下：
- 对于任意节点 x：
- 左子树中所有节点的值 < x 的值
- 右子树中所有节点的值 ≥ x 的值
例如：
这种结构使得查找效率大幅提升，但在极端情况下（如插入有序数据）会导致树高度为 O(n)，如下图所示：
总结：
- BST 的查找、插入、删除平均复杂度为
O(log n) - 最坏情况下退化为
O(n)，需要引入平衡机制
3. 平衡二叉树概述
平衡二叉树 是一种 BST，它通过一定的规则保持树的高度始终在 O(log n) 范围内。
特点：
- 插入或删除后会自动进行“再平衡”操作
- 查找、插入、删除操作的时间复杂度始终为
O(log n)
虽然平衡操作会带来一定的性能开销，但换来的是更稳定的查询性能，适用于对性能要求较高的场景。
4. AVL 树
AVL 树是最古老的自平衡二叉搜索树之一。
平衡定义：
一个节点被认为是平衡的，当且仅当其左右子树的高度差不超过 1。
公式表示如下：
|height(left) - height(right)| ≤ 1
示例：
平衡性证明（略）：
AVL 树的最小节点数与高度呈指数关系，最终可推导出树的高度为 O(log n)。
优点：
- 高度严格平衡，查找效率高
- 适合频繁查找、少量插入/删除的场景
缺点：
- 插入/删除时需要频繁调整，维护成本高
5. 红黑树（Red-Black Tree）
红黑树是一种更实用的平衡二叉搜索树结构，广泛用于 Java、C++ STL 等标准库中。
平衡特性（5条规则）：
- 每个节点是红色或黑色
- 根节点是黑色
- 所有叶子节点（NULL）是黑色
- 如果一个节点是红色，那么它的两个子节点必须是黑色
- 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点
示例：
平衡性证明（略）：
红黑树通过上述规则保证最长路径不超过最短路径的两倍，从而保证树的高度为 O(log n)。
优点：
- 插入/删除比 AVL 树更高效
- 更适合频繁插入/删除的场景
缺点：
- 查找效率略低于 AVL 树
6. 权重平衡树（Weight-Balanced Tree, WBT）
WBT 与 AVL、红黑树不同，它通过控制子树中叶子节点数量的比例来实现平衡。
平衡定义：
设节点 x 的左右子树分别为 x' 和 x''，若：
leaves(x'') / leaves(x') ≤ β ∈ (0, 1)
并且所有后代节点都满足该条件，则称该节点是平衡的。
等价于存在 α ∈ (0, 1)，使得：
leaves(x.left) ≥ α * leaves(x)
leaves(x.right) ≥ α * leaves(x)
示例：
其中每个节点内的数字表示该子树的叶子节点数。
平衡性证明（略）：
通过归纳法可以证明，WBT 的高度也为 O(log n)。
适用场景：
- 需要动态维护节点权重比例的场景
- 如某些数据库索引结构、持久化数据结构中
7. 总结
| 类型 | 平衡方式 | 插入/删除性能 | 查找性能 | 适用场景 |
|---|---|---|---|---|
| AVL 树 | 高度差 ≤ 1 | ❌较慢（频繁旋转） | ✅最快 | 查找频繁，插入/删除少 |
| 红黑树 | 黑高一致、红节点无连续 | ✅较快 | ✅较快 | 通用，如 Java TreeMap |
| 权重平衡树 | 子树叶子比例 | ✅较快 | ✅较快 | 权重敏感场景 |
一句话总结：
平衡二叉树通过不同的平衡策略保证树的高度始终为
O(log n)，从而确保查找、插入、删除操作的高效性。选择哪种结构取决于具体应用场景和性能需求。