是否存在高度最优但不满足AVL条件的二叉搜索树(BST)？

答案是不能构造出符合要求的反例，所有n个结点的最小高度二叉搜索树（BST），天然满足AVL树的定义要求。

• 先明确两个核心定义
  1. 最小高度BST：n个结点的BST的最小高度固定为 ⌈log₂(n+1)⌉ - 1，要达到这个高度，要求二叉树的每一层除最下层外全部被填满，最下层结点尽可能靠左排布，不能出现上层提前空缺的情况。
  2. AVL树：本身是BST，且任意结点的左右子树高度差的绝对值不超过1。
• 反证推导：假设存在一棵最小高度BST不满足AVL树要求，那么树中至少存在一个结点，其左右子树高度差≥2。此时我们可以通过调整该结点下属的结点排布，让该结点的子树高度至少降低1，调整后的整棵树高度会低于原来的高度，说明原来的树并没有达到最小高度，和前提矛盾。
• 实例验证：以n=4为例，最小高度为2，所有可能的最小高度BST的根结点左右子树高度差都是1，其余叶子结点高度差为0，全部符合AVL树要求；如果强行构造某结点左右高度差为2，整棵树高度会变成3，不符合最小高度的要求。

内容的提问来源于stack exchange，提问作者Nico