sorting - 二叉搜索树——排序

Question

如果我们有一个搜索树的 V 值，其中值是 V= {1,2,3,4,5,6,7}从右到左插入

我们要命令它尽可能地获得最大和最短的高度——我们将如何做到这一点？是否需要最好和最坏的 (lg2 (n+1)) 情况？

并且订单是唯一的吗？

谢谢 - 我有点理解，但不确定我应该采取什么步骤。

Answer 1

通过插入排序序列中的值来创建最高的此类树

1 2 3 4 5 6 7

或者

7 6 5 4 3 2 1

最短树是通过递归算法对值进行排序得到的，该算法找到中值，然后递归处理左右子树：

4 2 1 3 6 5 7

这会产生一个对数高度的树：

     4
   /   \
  2      6
 / \    / \
1   3  5   7

这里的中位数是 4，所以这是第一个。

4

现在您有一个左侧 (1, 2, 3) 和右侧 (5, 6, 7) 的分区。要排序左边，从它的中位数 2 开始。现在它的子树有 1 和 3。这些是 1 个元素集，因此这是您的基本情况。

4 2 1 3

现在处理你的右子树（5、6、7），从 6 开始。

4 2 1 3 6 5 7

Answer 2

最大高度容易；把它们按顺序排列：

1
 \
  2
   \
    ...

以最小的高度，将它们排序，以中间为根，将两侧各一个分支。冲洗并重复。

        3
       / \
      2   5
     /   / \
    1   4   6
             \
              7

所以... n 代表第一个，log_2(n) 代表第二个（四舍五入）。