二叉搜索树是二叉树的特例，平衡二叉树则是二叉搜索树的特例。
# 什么是平衡二叉树
⚡ 30 秒速记
- 高度平衡二叉树要求每个结点的左右子树高度差绝对值不超过 1，不是只检查根结点
- 高度是从叶子向父结点汇总的信息，使用后序遍历可同时计算高度并判断平衡
- 空树通常视为平衡且高度为 0；叶子高度取 1，定义统一后差值判断才不会偏一
平衡二叉树，也叫 AVL Tree，是任意结点左右子树高度差的绝对值都不超过 1 的二叉搜索树。 关键在“任意结点”，不能只看根结点是否平衡；只要某个内部结点超过这个范围，整棵树就不满足定义。它同时保留二叉搜索树的排序约束，并额外限制树的高度差。
在上一节的末尾，我们已经通过一道真题和平衡二叉树打过交道。正如题目中所说，平衡二叉树（又称 AVL Tree）指的是任意结点的左右子树高度差绝对值都不大于1的二叉搜索树。
💬 面试官追问
-
搜索页面展示一棵每个结点左右高度差都不超过
1的普通二叉树，候选人直接称它为AVL Tree，你会用什么结构性反例追问？仅满足左右子树高度差不超过
1，只能说明它具备高度平衡性质，还不能据此认定为AVL Tree。按照题目采用的定义，AVL Tree还必须是二叉搜索树；只要构造一个左孩子键值大于根结点的平衡结构，就能反驳该判断。 -
后台树结构校验接口需要判断十万级结点是否平衡，同事准备对每个结点分别调用一次求高度函数，你会怎样改写核心逻辑？
应使用一次后序遍历，让每个结点在获得左右子树高度后立即判断高度差，并向父结点返回当前高度。发现差值绝对值大于
1时可返回失衡哨兵并提前结束；这样避免对子树反复求高，但递归实现仍需关注极深异常输入的栈风险。 -
配置中心原先存放二叉搜索树，现在产品允许批量导入任意二叉树，但验收仍写着“通过平衡校验即为
AVL Tree”，你会如何拆分约束？需要把校验拆成搜索次序与高度平衡两部分：前者验证结点键值满足二叉搜索树约束，后者验证任意结点左右子树高度差绝对值不超过
1。批量导入放宽了结构来源，却没有自动保留搜索性质；只通过高度检查时，结果不能标记为AVL Tree。 -
线上健康检查把一棵明显倾斜的树判为平衡树，日志显示叶子高度有时记为
0、有时记为1，你会怎样排查判定逻辑？先统一空树与叶子结点的高度约定，并确认父结点高度始终由左右子树最大高度加一得到。只要整套计算前后一致，采用哪种常见起点通常不会改变高度差；若结果仍错误，应检查是否漏验深层结点，或把差值判断误写成仅检查根结点。
-
数据库索引方案评审中，一方认为完全二叉树与平衡二叉搜索树可以互换，另一方只关心最后一层从左填充，你会怎样澄清两类结构的取舍？
完全二叉树强调结点按层连续、最后一层从左填充，因此适合用数组和父子下标关系表达；平衡二叉搜索树强调搜索次序及每个结点的高度差约束。完全二叉树通常具有高度平衡外形，但未必满足搜索次序；
AVL Tree也不要求最后一层连续，二者不能按名称互换。
