Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Comments on Search tree supporting efficient bulk sequential insert
Post
Search tree supporting efficient bulk sequential insert
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.
1 comment thread