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)，从而确保查找、插入、删除操作的高效性。选择哪种结构取决于具体应用场景和性能需求。