二叉搜索树是二叉树的特例，平衡二叉树则是二叉搜索树的特例。

什么是平衡二叉树

⚡ 30 秒速记

• 高度平衡 = 每个结点左右子树高度差 ≤ 1，是「每个」，不是只看根
• AVL 树 = 平衡 + BST；LeetCode 110 只判平衡，不要求是 BST
• 高度从下往上汇总 → 用后序遍历，一边算高度一边判断
• 空树高度记 0，叶子记 1，统一口径才不会差一

平衡二叉树就是每个结点的左右子树高度最多差 1，严格说带上 BST 性质的才叫 AVL 树。 重点在「每个结点」：根左右各有三层看着挺平衡，但下面某个结点一边三层一边空，整棵树就不算平衡。刷题时要分清两个概念，LeetCode 110 只判断高度条件，不检查大小顺序；真正讲 AVL 的时候，是在 BST 之上再加平衡约束，目的是把树高压在 O(log n)。

在上一节的末尾，我们已经通过一道真题和平衡二叉树打过交道。正如题目中所说，平衡二叉树（又称 AVL Tree）指的是任意结点的左右子树高度差绝对值都不大于1的二叉搜索树。

💬 面试官追问

• 根结点左右子树高度一样，这棵树一定平衡吗？

  不一定。比如左右各是一条长 3 的链，根是平衡的，但链上的结点一边高 2 一边是 0，已经不平衡了。

• 平衡二叉树和完全二叉树什么关系？

  完全二叉树一定是平衡的，反过来不成立。平衡只限制高度差，最后一层可以不从左往右连续。

• AVL 和红黑树都是平衡树，差在哪？

  AVL 要求高度差 ≤ 1，更严格，查找更快，但插删时旋转更多。红黑树只保证最长路径不超过最短的两倍，插删调整少，所以 Java 的 TreeMap、C++ 的 std::map 都用红黑树。

• n 个结点的 AVL 树最高有多高？

  约 1.44 log2(n)，还是 O(log n)。这就是它敢承诺查找最坏也是对数级的依据。

为什么要有平衡二叉树

⚡ 30 秒速记

• 同一组数可以建出很多种 BST，形状决定效率
• 平衡时每比一次排除一半 → O(log n)；退化成链 → O(n)
• 例子：[1..5] 平衡树找 1 要 3 次，右斜链要 5 次
• 有序或近乎有序的插入最容易退化，真实数据里很常见
• 平衡的代价：结点多存高度/颜色，插删时要旋转

平衡二叉树就是为了防止 BST 长歪，长歪了二分的优势就没了。 BST 快是因为每比较一次就能扔掉一半，但这有前提，就是两边差不多大。同样是 1 到 5，平衡的树找 1 比 3 次，一条往右斜的链要比 5 次，数据量上去差距就是 log n 和 n 的差别。偏偏现实里顺序插入很常见，比如按自增 id 插。所以平衡树多做一点旋转，换来最坏情况也稳在 O(log n)。

平衡二叉树的出现，是为了降低二叉搜索树的查找时间复杂度。

大家知道，对于同样一个遍历序列，二叉搜索树的造型可以有很多种。拿 [1,2,3,4,5]这个中序遍历序列来说，基于它可以构造出的二叉搜索树就包括以下两种造型：