我正在尝试解决以下问题：“给定一个具有唯一整数元素的排序（递增顺序）数组，编写一个算法来创建一个高度最小的 BST。”
给定的答案将根节点作为数组的中间。虽然这样做对我来说很直观，但我试图严格地证明，让根节点位于数组的中间总是最好的。
书中给出的理由是：“要创建最小高度的树，我们需要将左子树中的节点数与右子树中的节点数尽可能匹配。这意味着我们想要根节点成为数组的中间，因为这意味着一半的元素会小于根，而一半的元素会更大。”
我想问：
为什么任何最小高度的树都是左子树中的节点数与右子树中的节点数尽可能相等的树？（或者，你有没有其他方法可以证明最好让根节点位于数组的中间？）
最小高度的树是否与平衡的树相同？从上一个关于 SO 的问题中，这就是我得到的印象，（可视化平衡树）但我很困惑，因为这本书特别指出“具有最小高度的 BST”，而从未“平衡 BST”。
谢谢。
资料来源：破解编码采访
我喜欢这样想，如果你使用树旋转（之字形和之字形旋转）平衡一棵树，你最终会达到左右子树最多相差一个高度的状态。平衡树的左右子节点数并不总是相同。但是，如果你有那个不变量（每边的孩子数相同），你可以到达一棵使用树旋转平衡的树）
余额是任意定义的。AVL 树以这样的方式定义它，即树的任何子树都没有高度相差超过 1 的子树。其他树以不同的方式定义平衡，因此它们的区别不同。它们本质上是相关的，但并不完全相同。话虽如此，在任何定义下都将始终平衡最小高度的树，因为存在平衡以维持 BST 的 O(log(n)) 查找时间。
如果我遗漏了什么或说错了什么，请随时编辑/纠正我。希望这可以帮助
为什么任何最小高度的树都是左子树中的节点数与右子树中的节点数尽可能相等的树？
可能存在这样一种情况，在最小高度的树中，当然是平衡的，左侧和右侧的节点数可能不同。BST 最坏情况遍历是 O(n)，如果它被排序并且在最小高度树中，最坏情况的复杂度是 O(log n)。
*
/ \
* *
/
*
在这里您可以清楚地看到左节点数和右节点数不相等，尽管它是最小高度树。
最小高度的树是否与平衡的树相同？从之前关于 SO 的问题中，这就是我得到的印象，（可视化平衡树）但我很困惑，因为这本书特别指出“具有最小高度的 BST”，而从未“平衡 BST”。
最小高度树是平衡的，有关更多详细信息，您可以查看 AVL 树，也称为高度平衡树。在使 BST 成为高度平衡树时，您必须执行旋转（LR、RR、LL、RL）。