recursion - Can you prove that average cost of n insertions to BST/AVL/Splay tree can't be lower than nlog(n)?

Question

I'm curious if you guys know an answer to this question that came to my mind.

We know that an average cost of BST insertion is O(log n) and worst case as well as average for AVL/Splay is O(log n).

Since we are inserting n times (basically we are building a tree) we will recieve the final cost being n*logn.

How can we prove that we can't get lower than that? It's easy to observe but kind of hard to prove.

Maybe we can use recursive equations and somehow limit them?

Thanks in advance.

Answer 1

As a hint, you can do an inorder traversal of any binary search tree in time O(n) to retrieve the elements of that BST in sorted order.

The algorithms for inserting into a red/black tree, AVL tree, splay tree, etc. are all comparison-based and work by comparing the newly-inserted element to a sequence of other elements in the tree. What would happen if you were able to do this in time o(n log n) (using little-o notation)?