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

A member of an increasing sequence (each next element is strictly greater than the previous one). You need to add the elements of a sequence to the tree so that it remained sbalansirovanny. What is the most efficient algorithm?
October 8th 19 at 03:55
3 answers
October 8th 19 at 03:57
Solution
The idea in this case, it just does not make sense to use a tree, it is more efficient dynamically growing array with a binary search on it.

Even if you first save the sequence to an array, it is possible to build a balanced binary tree in O(N), just beating an array recursively in the right order.
>better would be a dynamically growing array with a binary search on it
Controversial. Search sbalansirovannoe tree efficient binary search on the sorted array. And in my case the tree is created once, for subsequent searches. Even for a small gain in the efficiency of the search is willing to sacrifice the slow initialization.

What about a proper bypass of the array is clear. I thought that there might be some efficient algorithm to add an element, if we know that he is greater than all the previous ones, but I guess I was wrong. - Kristina_Bayer88 commented on October 8th 19 at 04:00
> Search sbalansirovannoe tree efficient binary search on the sorted array

why is that? here and there is O(log(n)). the asymptotics are the same.
but the sorted array is similar to a balanced tree, AVL or krasnochelie are not perfect and above average 1.3-1.4 times.

the second advantage of the array — the data locality. the deeper you are in the tree, the smaller your working set (and in the case of a tree the memory of adjacent elements can stand too far in the address space; then you can make a node pool and allocate memory for elements there) - mae_Kuh commented on October 8th 19 at 04:03
>What is the most efficient algorithm for adding an element to the tree
and
>Even for a small gain in the efficiency of the search is willing to sacrifice the slow initialization

I then see a contradiction. If speed search and the speed of initialization is not critical, what difference what algorithm you add? Get fast algorithm on a sample and not the Appendix. - davonte commented on October 8th 19 at 04:06
October 8th 19 at 03:59
Well, for example, you can use Cartesian treesif the keys are sorted, we are all in linear time can push. But, as noted above, the meaning of this a little bit — a binary search will save.
And Yes, if you have the elements of a sequence are integers, you can look in the direction of the vEB-tree. Actually, there is a more effective structure than this, but with respect to segment trees and search trees it is already runs faster. But it is better to check everything in practice, of course. - Kristina_Bayer88 commented on October 8th 19 at 04:02
October 8th 19 at 04:01
In any case you'll get O(N log N) so AVL.
How to show that in "any case" that happens? Had a feeling, but mathematically I do not know how to justify... - Kristina_Bayer88 commented on October 8th 19 at 04:04

Find more questions by tags Algorithms