c - 输入值创建二叉搜索树

Question

在二叉搜索树上，如果我输入“2,1,3,4,5”，树会是这样的

              2
              /\
              1 3
                 \
                  4
                   \
                    5

但是输入像“5,2,1,3,7,6,8”。

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

所以我的问题是，如何产生输入以便获得上面的平衡树结构。 (我不想使用 AVL 树)。我们是否有技巧以正确的方式对数字进行排序或重新排列并将它们作为输入生成。我正在寻找输入，以便树可以创建高达 10 的高度。

Answer 1

保证平衡树的一种非常简单的方法是对输入进行排序，然后递归地插入值，如下所示:

1. 插入整个数组的中间。
2. 使用此过程递归地插入数组的左半部分和右半部分。

例如，对于删除了 5 的值 1 - 8，您会将值排序为

1 2 3 5 6 7 8

然后您将插入 5，然后递归地将此过程应用于两半。在 1 2 3 上，您将插入 2，然后递归地插入 1 和 3。这给出了到目前为止的顺序

 5 2 1 3

现在，您递归地处理另一半，6 7 8，它插入 7，然后递归地插入 6 和 8。总的来说，这产生了顺序

5 2 1 3 7 6 8

这正是您之前在帖子中提出的顺序。

这个过程在 O(n lg n) 时间内运行。我不确定这是最佳答案，所以如果有人想发布更好的答案，我很乐意看到。