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