二叉搜索树 -- 排序

Question

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

我们要命令它获得最大和最短的高度 - 我们将如何做到这一点？它是否需要最好和最差（lg2 （n+1））的情况？

排序是否是唯一的？

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

Answer 1

最大的高度很容易;把它们按顺序排列：

1
 
  2
   
    ...

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

        3
       / 
      2   5
     /   / 
    1   4   6
             
              7

所以...n为第一个，log_2（n）为第二个（四舍五入）。

Answer 2

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

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