algorithm - 当我们知道大多数插入都是有序的时候创建 BBST 的策略？

Question

我有一种情况需要一个平衡的二叉搜索树。我使用过 AVL 树，但它需要大量旋转才能在插入时创建平衡高度。我观察到大多数输入已经有序。例如:8 9 10 11 12 13 2 14 15 16 17 4 18 19 20 等...当我们知道大多数输入已经有序时，是否有更好的创建 BBST 的策略？

Answer 1

运行 insertion sort ，它在已经排序或接近排序的数组上具有良好的性能(它具有性能 O(n + d) ，其中 d 是反转的次数)。当然，如果数组根本没有排序，你就不会想要这样做，在这种情况下，它需要 O(n<sup>2</sup>)。 ，与其他采用 O(n log n) 的排序算法相反.

运行后，您可以 construct the BST in O(n) :

If you would have to choose an array element to be the root of a balanced BST, which element would you pick? The root of a balanced BST should be the middle element from the sorted array.

You would pick the middle element from the sorted array in each iteration. You then create a node in the tree initialized with this element. After the element is chosen, what is left? Could you identify the sub-problems within the problem?

There are two arrays left — The one on its left and the one on its right. These two arrays are the sub-problems of the original problem, since both of them are sorted. Furthermore, they are subtrees of the current node’s left and right child.