Difference between the time complexity required to build Binary search tree and AVL tree?

Question

While I was learning Binary search tree(Balanced and unbalanced), I come up with questions which I need to resolve:

1. If I construct a Binary search tree(Not necessary to be balanced) , using n elements then what is the total time complexity for tree construction ?

2. If an AVL tree is constructed from n elements then what is the time complexity to contruct that AVL tree ?

Should it be more than nlog(n) ? because we need lots of rotation for AVL tree construction .

I know that insertion and deletion operation in AVL tree will be of log(n) order(same is true if binary search tree constructed with random elements has log(n) height).

But I need to know about overall tree construction cost and how it varies as I need to use balanced search tree for sorting purpose .

Answer 1

Let us start with constructing an AVL tree. To create a tree you have to insert n elements in it. To insert the element in a balanced tree you need log(n). Therefore you end up with O(n*log(n)).

Coming back to a regular BST. It is counter-intuitive, but it depends how do you construct this tree. If you do not know all the elements of BST in advance (online algorithm) then you have to insert each of n elements one after another. If you are extremely unlucky, the complexity of insert is O(n) and thus it deteriorates to O(n^2).

Notice that this situation is highly unlikely, but still possible.

But you can still achieve O(nlog(n)) if you know all the elements in advance. You can sort them O(nlog(n)) and then insert the elements in the following order. Take the middle element and insert it as a root, then recursively do the same for both parts that are left. You will end up creating balanced BST, inserting n elements using log(n).

Answer 2

1. It can be proven that the expected height of a BST satisifies E[Xn] <= 3 log n + O(1), so the expected time is O(n log n). The worst case is still O(n^2), e.g. if the input is sorted.
2. O(n log n) because the amount of rotations for every added element is O(1).