algorithm - Strategy to create BBST when we know that most of the inserts are in order? -

I have a situation where I need a balanced binary search tree. I have used the AVL tree, but it requires multiple rotation to make the height of the balance while inserting. I have noticed that most inputs are in the order of pre-order: 8 9 10 11 12 13 2 14 15 16 17 4 18 19 20 etc ... Is there a better strategy to make a BST, when we know that most of Input is already in sequence?

O (n + d) <<>

/ code>, where D is the number of reversal). Of course, you do not want to do this, if the array is not sorted at all, then in that case it takes O (n 2 ) , as opposed to the other Sorting algorithm which take o (n log n)

After running it, you can:

If you select an array element to become the root of BST, which element will you choose? The root of a balanced BST should be the middle element with the array array.

You will choose the middle element from the order array in each walk. Then you make a node in the tree started with this element. After choosing the element, what is left? Can you identify sub-problems within this problem?

Two arrays are left - one on the left and one on the right side of these two arrays are the sub-problems of the original problem, because both have been sorted. In addition, they are the sub-parts of the left and right child of the current node.