Software Development

For holding ordered sets of keys, there are well-known data structures (the red-black tree, for example) that support O(log(n)) lookup and insertion algorithms. Of course this means that there trivially exist algorithms for inserting a sequence of k keys in O(k log(n + k)). But if the keys to insert are given in sequential order, and it is known that they will form a contiguous sequence in the final set (i.e., they are all greater or all lesser than all the keys already in the structure, or they are all between two consecutive keys already in the structure), is there a data structure that can insert them more efficiently, say in O(k + log(n)) time, while still supporting O(log(n)) lookup?

Intuitively, it seems like after inserting the first key, we already know a lot about where in the tree the remaining keys need to go. And perhaps whatever rebalancing operations are needed can be batched so that the entire operation only has to walk up or down the tree a constant number of times—that's how I came to O(k + log(n)) as a target. But I haven't yet found a way to realize these intuitions.

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

Communities

Comments on Search tree supporting efficient bulk sequential insert

Search tree supporting efficient bulk sequential insert

1 comment thread