While I was learning Binary search tree(Balanced and unbalanced), I come up with questions which I need to resolve:
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 ?
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 .