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?

asked October 8th 19 at 03:55

3 answers

answered on

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.

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.

answered on 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. commented on October 8th 19 at 04:02

answered on 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... commented on October 8th 19 at 04:04

Find more questions by tags Algorithms

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

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

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