我有一种情况需要一个平衡的二叉搜索树。我使用过 AVL 树,但它需要大量旋转才能在插入时创建平衡高度。我观察到大多数输入已经有序。例如:8 9 10 11 12 13 2 14 15 16 17 4 18 19 20 等...当我们知道大多数输入已经有序时,是否有更好的创建 BBST 的策略?
最佳答案
运行 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.
关于algorithm - 当我们知道大多数插入都是有序的时候创建 BBST 的策略?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21840411/