algorithmdata-structuresbinary-search-treetime-complexityavl-tree

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


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 .


Solution

    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).