What is the most efficient algorithm for adding an element to a tree?

Question

Algorithms

There is an incoming increasing sequence (each next element is strictly greater than the previous one). It is necessary to add sequence elements to the tree in such a way that it remains balanced. What is the most efficient algorithm?

Answer 1

In theory, in this case, it simply does not make sense to use a tree; a dynamically growing array with a binary search on it will be more efficient.
Also, if you first save the sequence into an array, then you can then build a balanced binary tree from it in O (N), simply by going around the array recursively in the correct order.

Answer 2

Well, for example, you can use Cartesian trees , if the keys are sorted, then we can stuff them all in linear time. But, as noted above, there is little sense in this - a binary search will save everyone.

Answer 3

Either way you get O(N log N) so AVL.