平衡二叉树

---

平衡二叉树（Balanced Binary Tree）指的是一棵二叉树，它的任意一个节点的左右子树的高度差不超过 1。

1. 定义

设二叉树 T 的左子树高度为 hL，右子树高度为 hR。

对于 T 中的任意节点，都有： $$ |hL - hR| ≤ 1 $$

若满足上述条件，且左右子树本身也都是平衡二叉树，则 T 为平衡二叉树。

2. 特点

• 平衡性：避免树退化为链表，使得查找、插入、删除操作的时间复杂度接近 $O(\log n)$。
• 判定条件：只关心高度差，不要求二叉搜索树（BST）的有序性。

3. 判断是否平衡二叉树的步骤

1. 计算每个节点左右子树的高度

   • 高度 = 从该节点到叶子节点的最长路径上的节点数。
   • 空树高度 = 0。

2. 判断平衡性

   • 若某个节点的左右子树高度差大于 1，则这棵树不是平衡二叉树。

3. 递归检查

   • 不光要检查根节点，还要检查每个子树是否满足。

4. 示例

• 左偏非平衡

平衡树                 非平衡树（左偏）
      4                         4
     / \                       /
    2   6                     3
   / \ / \                   /
  1  3 5  7                 2

• 右偏非平衡

平衡树                 非平衡树（右偏）
      4                       1
     / \                       \
    2   6                       2
   / \ / \                       \
  1  3 5  7                       3
                                   \
                                    4

• 局部失衡

平衡树                 非平衡树（局部失衡）
      4                         4
     / \                       / \
    2   6                     2   6
   / \ / \                   / \    \
  1  3 5  7                 1   3    7
                                      \
                                       8