算法正确性求证：将有序数组转换为高度平衡BST

我们可以通过数学归纳法来严格证明这个递归方法能保证生成高度平衡的BST，核心逻辑围绕数组分割后的长度关系，以及平衡树高度的性质展开：

前置定义 #

• 高度平衡BST：任意节点的左右子树高度差不超过1
• 记T(k)为用该方法对长度为k的有序数组构建的BST

1. 基础情况验证 #

当数组长度k为0、1、2时，显然满足平衡：

• k=0：空树，无节点，自然平衡
• k=1：仅一个根节点，左右子树为空，高度差为0
• k=2：选索引1的元素为根，左子数组长度1（对应高度1的子树），右子数组长度0（对应高度0的子树），高度差为1，符合平衡要求

2. 归纳假设 #

假设对于所有长度小于n的有序数组，用该方法构建的T(k)都是高度平衡的BST。

3. 归纳步骤（证明长度为n的数组构建的T(n)是平衡的） #

对于长度为n的数组：

• 计算中间索引mid = n // 2，左子数组长度L = mid，右子数组长度R = n - mid - 1
• 先看L和R的差值：
  • 若n为偶数（n=2m）：mid=m，L=m，R=2m - m -1 = m-1，此时|L-R|=1
  • 若n为奇数（n=2m+1）：mid=m，L=m，R=2m+1 -m -1 = m，此时|L-R|=0

根据归纳假设，T(L)和T(R)都是高度平衡的。设h(L)为T(L)的高度，h(R)为T(R)的高度：

• 当n为奇数时，L=R=m，此时h(L)=h(R)，左右子树高度差为0，满足平衡
• 当n为偶数时，L=m、R=m-1。对于平衡树来说，长度差1的两个数组，它们的高度差最多为1（比如长度4的平衡树高度是3，长度3的平衡树高度是2，差1；长度5和4的平衡树高度都是3，差0）。因此|h(L)-h(R)| ≤1

而T(n)的高度为max(h(L), h(R)) + 1，其左右子树高度差≤1，同时T(L)和T(R)本身都是平衡的，因此T(n)的所有节点都满足高度平衡的要求。

结合代码的直观解释 #

你的代码每次选择数组中间元素作为根，分割出的左右子数组长度差最多为1。递归构建的左右子树本身都是平衡的，且它们的高度差不会超过1，因此根节点的左右子树高度差符合要求。递归传递下去，所有节点都会满足高度平衡的条件。

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