我正在尝试解决以下问题：“给定一个带有唯一整数元素的排序（递增顺序）数组，编写一个算法来创建一个具有最小高度的BST . ”
给定的答案将根节点作为数组的中间位置 . 虽然这样做对我来说很直观，但我试图严格证明，最好将根节点作为数组的中间位置 .
书中给出的理由是：“要创建一个最小高度的树，我们需要尽可能地将左子树中的节点数与右子树中的节点数相匹配 . 这意味着我们需要根节点是数组的中间，因为这意味着一半的元素将小于根，一半将更大 . “
我想问一下：
-
为什么任何最小高度的树都是左子树中节点数尽可能与右子树中节点数相等的树？ （或者，您是否有任何其他方法可以证明最好将根节点作为数组的中间位置？）
-
是一棵树的最小高度和我得到的印象相同的树，（Visualizing a balanced tree）但是我很困惑，因为这本书明确指出了"BST with minimal height"而且从来没有"balanced BST" .
谢谢 .
资料来源：破解编码面试
2 回答
我喜欢考虑它的方式，如果使用树旋转（Zig-zig和Zig-zag旋转） balancer 树，您最终将达到左右子树相差最多高度为1的状态 . balancer 的树在右侧和左侧必须具有相同数量的子项并非总是如此;但是，如果你有那个不变量（每边的孩子数相同），你可以到达一个使用树旋转 balancer 的树）
余额是任意定义的 . AVL树以这样的方式定义它，即树的子树没有高度相差不止一个的子节点 . 其他树木以不同的方式定义 balancer ，因此它们不同 . 它们本质上是相关的，但并不完全相同 . 话虽这么说，最小高度的树将始终在任何定义下 balancer ，因为存在 balancer 以维持BST的O（log（n））查找时间 .
如果我遗漏了任何错误或说错了，请随时编辑/更正我 . 希望这可以帮助
可能存在这样的情况：在 balancer 的最小高度树中，左侧和右侧可以具有不同数量的节点计数 . BST最坏情况遍历是O（n），如果它被排序，并且在最小高度树中，最坏情况的复杂度是O（log n） .
在这里，您可以清楚地看到左节点数和右节点不相等，尽管它是最小高度树 .
最小高度树是 balancer 的，有关详细信息，您可以查看AVL树，也称为高度 balancer 树 . 在使BST成为高度 balancer 树时，您必须执行旋转（LR，RR，LL，RL） .